Ch5. Data Structure

5장 자료구조

5.1 자료구조의 기본 개념

자료구조를 이해하는 데 있어서 가장 중요한 개념은 시간 복잡도와 공간 복잡도입니다. 이 두 가지 개념은 자료구조와 알고리즘을 평가하는 데 중요한 기준이 됩니다.

5.1.1 시간 복잡도 (Time Complexity)

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 나타내며, 주어진 입력 크기 n에 따라 함수로 표현됩니다. 시간 복잡도는 빅오 표기법(Big-O Notation)을 사용해 최악의 경우에 대한 성능을 평가합니다.

5.1.2 공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 필요한 메모리의 양을 의미합니다. 시간 복잡도와 마찬가지로 입력 크기 n에 따라 함수로 표현됩니다. 공간 복잡도 역시 빅오 표기법으로 표현되며, 알고리즘이 얼마나 메모리를 효율적으로 사용하는지 평가할 수 있습니다.

5.1.3 자료구조에서의 시간 복잡도

각 자료구조는 특정 연산에서 서로 다른 시간 복잡도를 가집니다. 예를 들어, 배열은 인덱스를 통한 접근은 O(1)의 시간 복잡도를 가지지만, 삽입이나 삭제는 O(n)의 시간이 걸립니다. 반면, 연결 리스트는 삽입과 삭제가 O(1)의 시간 복잡도를 가지지만, 인덱스를 통한 접근은 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)

이러한 시간 복잡도는 자료구조를 선택할 때 중요한 기준이 되며, 효율적인 코드 작성에 필수적인 요소입니다.

5.2 선형 자료구조

선형 자료구조는 데이터가 순차적으로 저장되는 구조를 의미합니다. 이 장에서는 배열, 연결 리스트, 백터, 스택, 큐에 대해 설명합니다.

5.2.1 배열 (Array)

배열은 선형 자료구조의 대표적인 예로, 동일한 데이터 타입의 요소들이 연속적인 메모리 공간에 저장됩니다. 배열의 특징과 사용법은 다음과 같습니다:

• 고정된 크기: 배열은 생성 시 크기가 고정되며, 이후에는 크기를 변경할 수 없습니다.

• 빠른 접근: 인덱스를 통해 O(1) 시간 복잡도로 요소에 접근할 수 있습니다.

• 비효율적인 삽입/삭제: 배열의 중간에 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동해야 하므로 O(n)의 시간 복잡도가 발생합니다.

배열은 데이터의 크기가 고정되어 있고, 인덱스를 통한 빠른 접근이 필요한 상황에 적합합니다.

5.2.2 연결 리스트 (Linked List)

연결 리스트는 배열과 달리 각 요소가 데이터와 다음 요소를 가리키는 포인터를 함께 저장하는 구조입니다. 연결 리스트는 크기가 가변적이며, 삽입 및 삭제가 용이합니다. 종류에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있습니다.

연결 리스트는 삽입과 삭제가 빈번하게 발생하는 상황에서 유리합니다. 그러나 특정 인덱스의 요소에 접근하기 위해 처음부터 탐색해야 하므로, 접근 속도는 배열보다 느립니다.

5.2.3 백터 (Vector)

백터는 동적 배열로, 크기가 자동으로 조정되는 배열입니다. 자바에서의 ArrayList가 백터의 대표적인 예입니다. 백터는 다음과 같은 특징을 가지고 있습니다:

• 동적 크기: 요소가 추가될 때 자동으로 크기가 조정됩니다.

• 빠른 접근: 배열과 마찬가지로 인덱스를 통한 O(1) 시간 복잡도로 요소에 접근할 수 있습니다.

• 메모리 오버헤드: 크기가 동적으로 조정되기 때문에 메모리 사용량이 비효율적일 수 있습니다.

백터는 크기가 자주 변하는 데이터를 관리할 때 유용하며, 배열보다 유연한 대안입니다.

5.2.4 스택 (Stack)

스택은 후입선출(LIFO) 구조를 가지며, 마지막에 삽입된 요소가 가장 먼저 제거됩니다. 주요 연산으로는 push(요소 추가), pop(요소 제거), peek(요소 조회) 등이 있습니다.

스택은 재귀적인 알고리즘, 괄호 짝 맞추기, 웹 브라우저의 뒤로 가기 기능 등에서 자주 사용됩니다.

5.2.5 큐 (Queue)

큐는 선입선출(FIFO) 구조를 가지며, 먼저 삽입된 요소가 먼저 제거됩니다. 주요 연산으로는 enqueue(요소 추가), dequeue(요소 제거), peek(요소 조회) 등이 있습니다.

큐는 데이터가 순차적으로 처리되어야 하는 상황에서 사용되며, BFS(너비 우선 탐색)와 같은 알고리즘에서 활용됩니다.

---

5.3 비선형 자료구조

비선형 자료구조는 데이터가 계층적이거나 네트워크 구조로 저장되는 자료구조입니다. 이 장에서는 그래프, 트리, 이진 트리, AVL 트리, 레드블랙 트리, 힙, 우선순위 큐, 맵, 셋, 해시테이블에 대해 설명합니다.

5.3.1 그래프 (Graph)

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 정점 간의 관계를 표현합니다. 그래프는 방향 그래프와 무방향 그래프로 나뉘며, 가중치가 있을 경우 가중 그래프라고 부릅니다.

그래프는 네트워크 모델링, 최단 경로 탐색, 사회적 관계 분석 등에서 자주 사용됩니다.

5.3.2 트리 (Tree)

트리는 계층적 구조를 표현하기 위한 비선형 자료구조입니다. 트리는 루트 노드를 중심으로 여러 자식 노드를 가지며, 이 자식 노드들 또한 자신의 자식을 가질 수 있습니다. 트리는 이진 트리, 이진 탐색 트리, AVL 트리 등 다양한 종류가 있습니다.

5.3.3 이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 트리의 특징은 다음과 같습니다:

• 완전 이진 트리: 모든 레벨이 꽉 찬 이진 트리입니다.

• 포화 이진 트리: 모든 노드가 두 개의 자식 노드를 가지며, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있습니다.

• 이진 탐색 트리: 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큽니다.

이진 트리는 데이터 탐색, 정렬, 효율적인 데이터 저장을 위해 자주 사용됩니다.

5.3.4 AVL 트리 (AVL Tree)

AVL 트리는 자가 균형 이진 탐색 트리로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 자동으로 균형을 맞춥니다. 삽입이나 삭제 시 트리의 균형이 깨지면 회전 연산을 통해 균형을 복원합니다.

AVL 트리는 삽입, 삭제, 탐색 연산에서 O(log n)의 시간 복잡도를 유지하기 때문에, 효율적인 검색과 정렬이 요구되는 상황에서 유리합니다.

5.3.5 레드블랙 트리 (Red-Black Tree)

레드블랙 트리는 또 다른 자가 균형 이진 탐색 트리로, 노드에 색깔(레드 또는 블랙)을 부여하여 트리의 균형을 유지합니다. 레드블랙 트리는 AVL 트리보다 조금 덜 엄격하게 균형을 유지하기 때문에, 삽입과 삭제가 더 빠르게 이루어질 수 있습니다.

레드블랙 트리는 주로 데이터베이스나 파일 시스템에서 사용됩니다.

5.3.6 힙 (Heap)

힙은 완전 이진 트리의 일종으로, 부모 노드가 자식 노드보다 크거나 작은 특성을 가집니다. 이 특성에 따라 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉩니다. 힙은 주로 우선순위 큐의 기본 자료구조로 사용됩니다.

힙은 정렬된 데이터를 관리하거나, 가장 큰/작은 요소를 빠르게 찾는 경우에 유용합니다.

5.3.7 우선순위 큐 (Priority Queue)

우선순위 큐는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다. 우선순위 큐는 힙을 사용하여 구현되는 경우가 많습니다.

우선순위 큐는 작업 스케줄링, 시뮬레이션 시스템 등에서 자주 사용됩니다.

5.3.8 맵 (Map)

맵은 키-값 쌍으로 데이터를 저장하는 자료구조로, 해시 테이블을 이용해 구현됩니다. 각 키는 유일하며, 키를 통해 값에 빠르게 접근할 수 있습니다. 자바에서는 HashMap, TreeMap 등이 맵의 대표적인 구현체입니다.

맵은 데이터베이스 인덱싱, 캐싱, 집합 연산 등에서 사용됩니다.

5.3.9 셋 (Set)

셋은 유일한 요소들로 이루어진 집합을 표현하는 자료구조로, 중복된 값을 허용하지 않습니다. 해시 테이블을 기반으로 한 HashSet, 정렬된 순서를 유지하는 TreeSet 등이 자바에서의 셋 구현체입니다.

셋은 집합 연산, 중복 제거 등에서 유용하게 사용됩니다.

5.3.10 해시 테이블 (Hash Table)

해시 테이블은 키를 해시 함수로 변환하여 값을 저장하는 자료구조로, 매우 빠른 검색 속도를 제공합니다. 해시 테이블의 주요 특징은 다음과 같습니다:

• O(1)의 시간 복잡도: 평균적으로 O(1) 시간 내에 데이터에 접근할 수 있습니다.

• 해시 충돌 처리: 동일한 해시 값을 가진 키가 존재할 수 있으므로, 이를 처리하기 위한 방법이 필요합니다.

해시 테이블은 데이터베이스, 캐시, 검색 알고리즘 등에서 널리 사용됩니다.