|
|
| 1번째 줄: |
1번째 줄: |
| == 자료구조 ==
| |
|
| |
|
| > data structure는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.
| | === 복잡도 === |
|
| |
|
| 
| |
|
| |
|
| === 💡 빅오 표기법 === | | ==== 시간 복잡도 ==== |
|
| |
|
| * '''불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적'''으로 사용
| | 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 말한다 |
| * 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
| |
| * Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있다.
| |
| - '''시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수'''를 나타낸다.
| |
| - '''공간복잡도는 알고리즘이 실행될때 사용하는 메모리의 양'''을 나타낸다.요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다.
| |
| * Big-O의 복잡도를 나타내는 표
| |
|
| |
|
| 
| | 어떠한 알고리즘의 로직이 얼만큼 걸리는지 시간을 나타내는데 쓰이며, 보통 빅오 표기법으로 나타낸다 |
|
| |
|
| === 💡 시간 복잡도 ===
| | 빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다 |
|
| |
|
| * 알고리즘의 성능을 설명하는 것
| | 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 없앤다 |
| * 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것
| |
|
| |
|
| '''시간복잡도에서 가장 큰 영향을 미치는 n의 단위'''
| | n^2 + 3 -> n^2 |
|
| |
|
| <syntaxhighlight>
| | 시간 복잡도의 속도는 다음과 같다 |
| 1 O(1) --> 상수
| |
| 2n + 20 O(n) --> n이 가장 큰영향을 미친다.
| |
| 3n^2 O(n^2) --> n^2이 가장 큰영향을 미친다.
| |
| </syntaxhighlight>
| |
|
| |
|
| '''시간복잡도의 문제해결 단계'''
| | O(n^2) > O(n) > O(logn) > O(1) |
|
| |
|
| <syntaxhighlight>
| |
| O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
| |
| O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
| |
| O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
| |
| O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
| |
| O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
| |
| O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
| |
| </syntaxhighlight>
| |
|
| |
|
| === 💡 공간 복잡도 === | | ==== 공간 복잡도 ==== |
|
| |
|
| * 공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
| | 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다 |
| * `총 공간 요구 = 고정 공간 요구 + 가변 공간 요구`
| |
| * '''고정 공간'''은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)
| |
| * '''가변 공간'''은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간
| |
|
| |
|
| <syntaxhighlight>bash
| | 정적 변수, 재귀 함수 등 동적으로 공간을 필요로 하는 경우도 포함한다 |
| int a[1004];// a 배열은 1004 x 4 바이트의 크기를 가지게 된다.
| |
| </syntaxhighlight>
| |
|
| |
|
| === 💡 자료구조의 시간 복잡도 === | | === 선형 자료구조 === |
|
| |
|
| 
| | 자료 구조의 요소가 순차적으로 나열되어 있는 구조이다 |
|
| |
|
| == 선형 자료 구조 == | | ==== 연결 리스트 ==== |
|
| |
|
| > 요소가 일렬로 나열되어 있는 자료 구조
| | 시간 복잡도 |
|
| |
|
| === 💡 Array vs Linked List ===
| | * 삽입, 삭제 : O(1) |
| | * 탐색 : O(n) |
|
| |
|
| ==== 💡 Array ====
| | 데이터와 노드에 대한 주소를 담고 있는 노드 단위로 요소를 가지고 있다 |
|
| |
|
| * 가장 기본적인 자료구조
| | 주소를 어떻게 가지고 있는지에 따라 연결 리스트의 종류가 결정된다 |
|
| |
|
| * 논리적 저장 순서와 물리적 저장 순서가 일치
| | 싱글 연결 리스트 : 다음 노드의 주소만 가지고 있는 연결 리스트 |
|
| |
|
| * 인덱스(index)로 해당 원소(element)에 접근할 수 있다.
| | 이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있는 연결 리스트 |
|
| |
|
| → 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-'''O(1)'''에 해당 원소로 '''접근'''할 수 있다.
| | 원형 이중 연결 리스트 : 이중 연결리스트이면서 마지막 노드가 첫 번째 노드의 주소를 가지고 있는 연결 리스트 |
|
| |
|
| → 즉 '''random access''' 가 가능하다는 장점
| | ==== 배열 ==== |
|
| |
|
| '''BUT'''
| | 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다 |
|
| |
|
| * '''삭제''' 또는 '''삽입'''의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤 (O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에 시간이 더 걸린다.
| | 정적 배열 기준 시간 복잡도 |
|
| |
|
| * 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생긴다. | | * 삽입, 삭제 : O(n) |
| | * 탐색 : O(1) |
|
| |
|
| * 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 '''O(n)'''가 된다.
| | 보통 데이터 추가와 삭제를 많이 하는 것은 연결 리스트를 사용하고, 탐색을 많이 하는 것은 배열을 쓴다 |
|
| |
|
| * 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 '''O(n)'''이 된다.
| | ==== 벡터 ==== |
|
| |
|
| * 삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 '''O(n)'''의 시간을 요구하게 된다.
| | 동적으로 요소를 할당할 수 있는 동적 배열이다 |
|
| |
|
| ==== 💡 '''Linked List''' ====
| | 컴파일 시점에 배열의 크기를 지정할 수 없다면 벡터를 사용해야 한다 |
|
| |
|
| * 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
| | 시간 복잡도 |
|
| |
|
| 
| | * 탐색, 맨 뒤 요소 삭제, 삽입 : O(1) |
| | * 맨 뒤나 앞이 아닌 요소 삽입, 삭제 : O(n) |
|
| |
|
| * prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것
| | ==== 스택 ==== |
| * 단순 연결 리스트 : next 포인터만 가진다.
| |
| * 원형 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다.
| |
| * 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
| |
|
| |
|
| ---
| | LIFO 성질을 가진다 |
|
| |
|
| * 배열의 문제점을 해결하기 위한 자료구조가 linked list
| | 시간복잡도 |
|
| |
|
| * 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. | | * 삽입, 삭제 : O(1) |
| | * 탐색 : O(n) |
|
| |
|
| * 따라서 이 부분만 다른 값으로 바꿔주면 '''삭제와 삽입'''을 '''O(1)''' 만에 해결할 수 있는 것이다.
| | ==== 큐 ==== |
|
| |
|
| '''BUT'''
| | FIFO 성질을 가진다 |
|
| |
|
| * 하지만 Linked List 역시 한 가지 문제가 있다.
| | 시간복잡도 |
|
| |
|
| * 원하는 위치에 삽입을 하고자 하면 '''원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인'''해봐야 한다는 것이다. '''Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문'''이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. | | * 삽입, 삭제 : O(1) |
| | | * 탐색 : O(n) |
| * 이 과정 때문에, '''어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서(탐색) O(n)의 시간이 추가적으로 발생'''하게 된다.
| |
| | |
| * 결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다.
| |
| | |
| → 그렇다고 해서 아주 쓸모없는 자료구조는 아니기에, 우리가 학습하는 것이다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.
| |
| 
| |
| | |
| '''<배열과 연결 리스트 비교>'''
| |
| | |
| <aside>
| |
| | |
| '''배열''' '''→''' '''탐색 O(1) | 삽입, 삭제 O(n)'''
| |
| '''연결 리스트 →''' '''탐색 O(n) | 삽입, 삭제 O(1)'''
| |
| | |
| </aside>
| |
| | |
| _배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다._
| |
| | |
| _연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다._
| |
| | |
| _탐색은 배열이 빠르고 연결 리스트는 느리다. 배열의 경우 그저 상자 위에 있는 요소를 탐색하면 되는 반면에, 연결 리스트는 상자를 열어야 하고 주어진 선을 기반으로 순차적으로 열어야 한다._
| |
| | |
| _하지만 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느리다. 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문이다._
| |
| | |
| _따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다._
| |
| | |
| === 💡Vector ===
| |
| | |
| * 동적으로 요소를 할당할 수 있는 동적 배열
| |
| * 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.
| |
| * 또한, 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
| |
| * 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간이 걸린다.
| |
| | |
| === 💡 Stack and Queue ===
| |
| | |
| 
| |
| | |
| ==== 💡 Stack ====
| |
| | |
| * 선형 자료구조의 일종으로 `Last In First Out (LIFO)` . 즉, 나중에 들어간 원소가 먼저 나온다.
| |
| * 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다.
| |
| * 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.
| |
| * 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조이다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.
| |
| | |
| ==== 💡 Queue ====
| |
| | |
| * 선형 자료구조의 일종으로 `First In First Out (FIFO)`. 즉, 먼저 들어간 놈이 먼저 나온다.
| |
| * Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다.
| |
| * 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 `Priority queue`등을 사용할 수 있다.
| |
| * 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료 구조이며, 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.
| |
| | |
| > [참고자료](https://blog.chulgil.me/algorithm/) > [참고자료](https://madplay.github.io/post/time-complexity-space-complexity) > [참고자료](https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list) > [참고자료](https://osy0907.tistory.com/82?category=911997)
| |
복잡도
시간 복잡도
문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 말한다
어떠한 알고리즘의 로직이 얼만큼 걸리는지 시간을 나타내는데 쓰이며, 보통 빅오 표기법으로 나타낸다
빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다
가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 없앤다
n^2 + 3 -> n^2
시간 복잡도의 속도는 다음과 같다
O(n^2) > O(n) > O(logn) > O(1)
공간 복잡도
프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다
정적 변수, 재귀 함수 등 동적으로 공간을 필요로 하는 경우도 포함한다
선형 자료구조
자료 구조의 요소가 순차적으로 나열되어 있는 구조이다
연결 리스트
시간 복잡도
데이터와 노드에 대한 주소를 담고 있는 노드 단위로 요소를 가지고 있다
주소를 어떻게 가지고 있는지에 따라 연결 리스트의 종류가 결정된다
싱글 연결 리스트 : 다음 노드의 주소만 가지고 있는 연결 리스트
이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있는 연결 리스트
원형 이중 연결 리스트 : 이중 연결리스트이면서 마지막 노드가 첫 번째 노드의 주소를 가지고 있는 연결 리스트
배열
같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다
정적 배열 기준 시간 복잡도
보통 데이터 추가와 삭제를 많이 하는 것은 연결 리스트를 사용하고, 탐색을 많이 하는 것은 배열을 쓴다
벡터
동적으로 요소를 할당할 수 있는 동적 배열이다
컴파일 시점에 배열의 크기를 지정할 수 없다면 벡터를 사용해야 한다
시간 복잡도
- 탐색, 맨 뒤 요소 삭제, 삽입 : O(1)
- 맨 뒤나 앞이 아닌 요소 삽입, 삭제 : O(n)
스택
LIFO 성질을 가진다
시간복잡도
큐
FIFO 성질을 가진다
시간복잡도
