# 자료구조와 복잡도

## 복잡도
복잡도는 알고리즘의 효율성을 측정하는 방법입니다. 알고리즘이 실행되는 데 필요한 시간과 공간을 나타냅니다. 이를 통해 알고리즘의 성능을 평가하고 효율적인 알고리즘을 선택할 수 있습니다.

### 시간 복잡도
시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 분석하는 방법입니다. 즉, '문제를 해결하는데 걸리는 시간과 입력의 함수 관계'를 가르킵니다. 알고리즘의 실행 시간은 입력 데이터의 크기에 따라 어떻게 증가하는지를 나타냅니다.

- 빅오표기법 :빅오 표기법(Big O notation)은 알고리즘의 성능을 나타내는 표기법 중 하나입니다. 빅오 표기법은 알고리즘의 최악의 경우를 나타내며, 알고리즘이 처리해야 할 데이터의 양이 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타냅니다. 빅오 표기법은 O(n)과 같은 형태로 나타내며, 여기서 n은 알고리즘이 처리해야 할 데이터의 양을 의미합니다. O(1)은 알고리즘의 실행 시간이 데이터의 양에 관계없이 일정하다는 것을 의미하고, O(n)은 데이터의 양에 비례하여 실행 시간이 증가함을 나타냅니다. O(n^2), O(n^3) 등은 데이터의 양의 제곱, 세제곱에 비례하여 실행 시간이 증가함을 나타내며, O(log n), O(n log n) 등은 로그 시간 복잡도를 가집니다. 빅오 표기법을 이해하고 사용하는 것은 알고리즘의 성능을 분석하고, 주어진 문제에 가장 효율적인 알고리즘을 선택하는 데 매우 중요합니다.

[사용예시]
1. **선형 검색**: 선형 검색 알고리즘은 리스트의 각 요소를 하나씩 확인하여 원하는 값을 찾습니다. 이 경우 최악의 시나리오는 리스트의 모든 요소를 확인해야 하는 경우입니다. 따라서 선형 검색의 시간 복잡도는 O(n)입니다.
2. **이진 검색**: 정렬된 리스트에서 이진 검색을 사용하면 원하는 값을 훨씬 빠르게 찾을 수 있습니다. 이진 검색은 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 반으로 줄입니다. 이 과정을 원하는 값을 찾을 때까지 반복하므로, 이진 검색의 시간 복잡도는 O(log n)입니다.
3. **배열의 접근**: 배열에 저장된 값을 인덱스를 사용하여 접근하는 경우, 해당 값에 접근하는 데 필요한 시간은 배열의 크기와 무관합니다. 따라서 배열의 접근 시간 복잡도는 O(1)입니다.
4. **버블 정렬**: 버블 정렬은 인접한 두 요소를 비교하고 필요한 경우 위치를 바꾸는 과정을 반복하여 리스트를 정렬합니다. 이 경우 리스트의 모든 요소를 비교해야 하므로, 버블 정렬의 시간 복잡도는 O(n^2)입니다.

### 공간 복잡도
공간 복잡도는 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 나타냅니다. 쉽게 말해, 알고리즘이 작동하는 데 얼마나 많은 메모리를 필요로 하는지를 측정하는 것입니다.
공간 복잡도를 측정하는 데는 두 가지 주요 요소가 있습니다:

1. **고정 공간(Static Space)**: 알고리즘이 실행되기 위해 필요한 공간으로, 변수, 상수, 프로그램 크기 등을 포함합니다.

2. **가변 공간(Dynamic Space)**: 알고리즘 실행 도중 필요한 공간으로, 동적으로 할당되는 공간(예: 재귀 스택 공간, 동적 메모리 할당 등)을 포함합니다.

공간 복잡도는 고정 공간과 가변 공간의 합으로 계산됩니다. 공간 복잡도를 나타낼 때도 빅오 표기법을 사용합니다. 예를 들어, 공간 복잡도가 O(1)이라는 것은 알고리즘이 실행되는 동안 필요한 메모리 공간이 상수 시간인 것을 의미합니다. 반면에 공간 복잡도가 O(n)이라는 것은 알고리즘이 처리해야 할 데이터의 양에 비례하여 필요한 메모리 공간이 증가하는 것을 의미합니다.

시간 복잡도와 마찬가지로, 공간 복잡도도 알고리즘의 효율성을 판단하는 중요한 요소입니다. 특히 메모리가 제한적인 임베디드 시스템이나 모바일 디바이스 등에서는 공간 복잡도를 최소화하는 것이 중요합니다.

### 자료 구조에서의 시간 복잡도
자료 구조에서의 시간 복잡도는 해당 자료 구조를 활용하는 연산(삽입, 삭제, 검색 등)을 수행하는 데 필요한 시간을 나타냅니다. 각 자료 구조마다 연산을 수행하는 방식이 다르기 때문에, 시간 복잡도 역시 자료 구조에 따라 달라집니다.

1. **배열**: 배열에서는 인덱스를 통해 특정 요소에 접근하는 데 O(1)의 시간이 걸립니다. 하지만 중간에 요소를 삽입하거나 삭제하는 경우, 배열의 나머지 요소들을 이동시켜야 하므로 O(n)의 시간이 소요됩니다.

2. **연결 리스트**: 연결 리스트에서는 특정 요소에 접근하려면 리스트를 처음부터 순회해야 하므로 O(n)의 시간이 걸립니다. 하지만 리스트의 시작 또는 끝에 요소를 삽입하거나 삭제하는 경우는 O(1)의 시간이 걸립니다.

3. **스택과 큐**: 스택과 큐에서는 삽입과 삭제 연산이 O(1)의 시간에 이루어집니다. 하지만 특정 요소를 찾는 데는 O(n)의 시간이 걸립니다.

4. **해시 테이블**: 해시 테이블에서는 키를 통해 특정 요소에 접근하거나 삽입, 삭제하는 데 평균적으로 O(1)의 시간이 걸립니다. 하지만 최악의 경우(모든 키가 동일한 해시 값을 가지는 경우 등)에는 O(n)의 시간이 걸릴 수 있습니다.

5. **이진 탐색 트리**: 이진 탐색 트리에서는 검색, 삽입, 삭제 연산이 평균적으로 O(log n)의 시간에 이루어집니다. 하지만 트리가 한쪽으로 치우친 경우 최악의 시간 복잡도는 O(n)이 됩니다.

- 자료 구조의 평균 시간 복잡도

| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|----------|------|------|------|------|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
| 레드 블랙 트리 | O(log n) | O(log n) | O(log n) | O(log n) |

- 자료 구조 최악의 시간 복잡도

| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|----------|------|------|------|------|
| 배열 | O(1) | O(n) | O(n) | O(n) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
| 레드 블랙 트리 | O(log n) | O(log n) | O(log n) | O(log n) |

## 선형 자료 구조
선형 자료 구조는 데이터가 일렬로 나열되는 구조를 가지며, 배열, 연결 리스트, 스택, 큐 등이 이에 해당합니다.

### 연결 리스트
연결 리스트는 데이터를 노드로 구성하고, 노드들이 포인터로 연결되어 있는 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결 리스트는 데이터의 삽입과 삭제가 유연하며, 메모리 공간을 효율적으로 사용할 수 있는 장점이 있습니다.

연결 리스트의 주요 특징은 다음과 같습니다:

1. **동적 크기**: 연결 리스트는 노드를 동적으로 추가하거나 제거함으로써 크기를 조절할 수 있습니다. 이는 배열과 같은 고정 크기 자료 구조와 대조적입니다.
2. **데이터의 삽입과 삭제 용이**: 연결 리스트에서는 노드를 삽입하거나 삭제하는 것이 쉽습니다. 특정 위치에 노드를 삽입하거나 삭제하려면 해당 위치의 이전 노드만 수정하면 됩니다.

그러나 연결 리스트도 몇 가지 단점이 있습니다:

1. **접근 시간**: 배열과 달리 연결 리스트는 인덱스를 통한 빠른 접근이 불가능합니다. 특정 위치의 노드에 접근하려면 처음부터 순차적으로 탐색해야 합니다.
2. **메모리 사용량**: 각 노드가 데이터와 링크를 모두 저장해야 하므로, 같은 수의 데이터를 저장하는 데 연결 리스트가 배열보다 더 많은 메모리를 사용합니다.

[연결 리스트 종류]
1. **싱글 연결 리스트(Singly Linked List)**: 이는 가장 기본적인 형태의 연결 리스트입니다. 각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 구성되어 있습니다. 따라서 리스트를 순회하려면 항상 첫 번째 노드(헤드)부터 시작해야 합니다. 또한, 노드의 삭제나 삽입을 위해서는 이전 노드의 정보가 필요하므로, 작업을 수행하려는 노드의 이전 노드를 찾는 과정이 필요합니다.

2. **이중 연결 리스트(Doubly Linked List)**: 이중 연결 리스트는 각 노드가 데이터와 두 개의 링크로 구성되어 있는 연결 리스트입니다. 하나의 링크는 다음 노드를, 다른 하나의 링크는 이전 노드를 가리킵니다. 이로 인해 리스트를 양방향으로 순회할 수 있으며, 노드의 삽입과 삭제가 더욱 용이해집니다.

3. **원형 이중 연결 리스트(Circular Doubly Linked List)**: 원형 이중 연결 리스트는 이중 연결 리스트의 변형입니다. 이 리스트에서는 마지막 노드가 첫 번째 노드를 가리키고, 첫 번째 노드가 마지막 노드를 가리킵니다. 이렇게 함으로써 리스트의 끝과 시작이 연결되어 원형처럼 돌아갈 수 있습니다. 이는 순환 리스트를 필요로 하는 특정 상황에서 유용하게 사용됩니다.

각각의 연결 리스트는 그 특성에 따라 적절한 상황에 사용되어야 합니다. 예를 들어, 노드의 삽입과 삭제가 빈번하게 일어나는 경우에는 이중 연결 리스트가 효과적일 수 있습니다. 반면에 메모리를 절약해야 하는 상황에서는 싱글 연결 리스트가 더 적합할 수 있습니다.

### 배열
배열은 동일한 자료형의 데이터를 연속된 메모리 공간에 저장하는 구조입니다. 배열은 인덱스를 사용하여 데이터에 접근할 수 있어 검색이 빠르지만, 데이터의 삽입과 삭제에는 제한이 있습니다. 또한 배열의 크기를 변경하기 위해서는 추가적인 연산이 필요합니다.따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 거이 좋습니다.

1. **랜덤 접근 vs 순차적 접근**: 이를 책을 읽는 것에 비유하면, 랜덤 접근은 책의 목차를 보고 바로 특정 페이지로 이동하여 정보를 얻는 것과 같습니다. 반면에 순차적 접근은 책의 첫 페이지부터 시작하여 원하는 정보가 있는 페이지를 찾을 때까지 페이지를 하나씩 넘기는 것과 같습니다.

2. **배열 vs 연결 리스트**: 이를 쇼핑몰의 상품 배치에 비유하면, 배열은 상품들이 일렬로 정렬되어 있는 백화점의 진열대와 같습니다. 각 상품(데이터)은 그 위치(인덱스)에 따라 고유한 번호를 가지며, 이 번호를 통해 바로 찾아갈 수 있습니다. 하지만 상품을 추가하거나 제거하려면 그 위치의 다른 상품들을 이동시켜야 합니다. 반면에 연결 리스트는 소규모의 각자 독립적인 상점들이 하나의 쇼핑 거리를 이루고 있는 것과 같습니다. 각 상점(노드)은 자신의 상품(데이터)와 다음 상점으로 가는 길(포인터)을 가지고 있습니다. 상점을 추가하거나 제거하는 것은 간단하지만, 특정 상점을 찾기 위해서는 쇼핑 거리의 시작부터 순차적으로 거쳐가야 합니다.

### 벡터
벡터는 배열과 유사한 자료 구조로, 크기가 동적으로 조절될 수 있는 배열입니다. 벡터는 배열과 달리 크기를 동적으로 관리하며, 데이터의 삽입과 삭제가 용이합니다. 하지만 데이터의 중간 삽입과 삭제는 배열에 비해 상대적으로 느릴 수 있습니다.

### 스택
스택은 후입선출(LIFO, Last-In-First-Out) 원칙에 따라 데이터를 저장하는 자료 구조입니다. 데이터의 추가는 스택의 맨 위에 이루어지며, 데이터의 삭제 역시 맨 위에서 이루어집니다. 스택은 함수 호출이나 괄호 짝 맞추기 등에 유용하게 사용될 수 있습니다.

### 큐
큐는 선입선출(FIFO, First-In-First-Out) 원칙에 따라 데이터를 저장하는 자료 구조입니다. 데이터의 추가는 큐의 뒤(rear)에서 이루어지고, 데이터의 삭제는 큐의 앞(front)에서 이루어집니다. 큐는 작업 대기열, 너비 우선 탐색(BFS) 등에 활용됩니다.

## 비선형 자료 구조
비선형 자료 구조는 데이터가 계층적인 구조를 가지는 구조를 의미합니다. 그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해시 테이블 등이 이에 해당합니다.

### 그래프
그래프는 정점과 간선으로 이루어진 자료 구조로, 다양한 형태와 연결 관계를 가질 수 있습니다. 그래프는 네트워크 분석, 경로 탐색, 최단 경로 알고리즘 등에 사용됩니다.

### 트리
트리는 계층적인 구조를 가지며, 하나의 루트(root) 노드에서 시작하여 여러 개의 자식(child) 노드로 이어지는 구조입니다. 트리는 파일 시스템, 계층적인 데이터 구조 등에 사용됩니다. 이진 트리, 이진 탐색 트리, AVL 트리, B-트리 등 다양한 종류의 트리가 있습니다.

### 힙
힙은 완전 이진 트리의 일종으로, 최댓값이나 최솟값을 효율적으로 찾기 위한 자료 구조입니다. 힙은 우선순위 큐, 힙 정렬 등에 사용됩니다.

### 우선순위 큐
우선순위 큐는 데이터에 우선순위를 부여하여 가장 높은 우선순위를 가진 데이터를 먼저 꺼내올 수 있는 자료 구조입니다. 우선순위 큐는 다익스트라 알고리즘, 허프만 코딩 등에 사용됩니다.

### 맵
맵은 키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료 구조입니다. 키를 기반으로 값을 검색하고, 키와 값은 일대일 대응 관계를 가집니다. 맵은 해시 맵, 이진 탐색 트리 기반의 맵 등 다양한 구현 방식이 있습니다.

### 셋
셋은 중복을 허용하지 않는 원소들의 집합을 표현하는 자료 구조입니다. 셋은 원소의 존재 여부를 빠르게 확인할 수 있습니다.

### 해시 테이블
해시 테이블은 키와 값의 쌍으로 데이터를 저장하는 자료 구조입니다. 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용하여 값을 저장하고 검색합니다. 해시 테이블은 데이터의 삽입, 삭제, 검색에 O(1)의 시간 복잡도를 가집니다.