트리(Tree)
- 트리: 노드와 엣지로 구성된 계층적 데이터 구조.
- 루트 트리(Rooted Tree): 하나의 노드를 루트로 지정한 트리.
- 포레스트(Forest): 트리의 집합, 즉 연결되지 않은 트리 여러 개.
- 내부 노드(Internal Node): 자식 노드를 가진 노드.
- 외부 노드(External Node, Leaf): 자식 노드가 없는 노드.
- 완전 이진 트리(Complete Binary Tree, CBT): 모든 레벨이 채워져 있거나, 마지막 레벨에서 왼쪽부터 채워진 이진 트리.
- MB 힙(Max Binary Heap): 최대 힙, 부모 노드가 자식 노드보다 큰 이진 트리.
- 힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘. Max Heap을 기반으로 배열을 오름차순으로 정렬.
그래프(Graph)
- 그래프: 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조.
- 유향 그래프(Directed Graph): 간선에 방향이 있는 그래프.
- 무향 그래프(Undirected Graph): 간선에 방향이 없는 그래프.
- 그래프 표현 방식: 인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix).
그래프 알고리즘
- 최소 신장 트리(MST), 다익스트라 알고리즘, 플로이드 알고리즘 등이 대표적.
- DFS/BFS: 그래프 탐색 방법으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.
큐와 스택
- FIFO(First In First Out): 먼저 들어온 데이터가 먼저 나가는 방식(큐).
- 스택(Stack): LIFO(Last In First Out) 방식의 데이터 구조.
분리 집합(Disjoint Sets)
- 상호 배타적 집합을 효율적으로 표현하는 데이터 구조로, 합집합과 찾기 연산을 지원하고 주로 Union-Find알고리즘을 사용한다.
- Make-Set 각 정점마다 자신만을 포함하는 집합을 초기화하는 자료구조이다. 즉 그래프의 각 정점을 별도의 집합으로 만들어 초기화한다.
- Find-set 두 정점이 같은 연결 성분에 속하는지 확인하기 위한 자료 구조이다. 이는 각 정점이 속한 집합을 찾는 역할을 한다. 이 과정에서 Path Compression기법을 사용해 효율성을 높일 수 있다.
- Union 두개의 집합을 합치는 연산을 수행하는 자료 구조이다. 이를 통해 두 정점이 같은 연결 성분에 속하도록 한다. 이때 Union by Rank기법을 사용하면 시간 복잡도를 줄일 수 있다.
힙 정렬 알고리즘
- 힙 구성(Heapify): 배열을 힙 구조로 바꿈.
- 루트 제거: 최대값(루트)을 배열의 끝으로 이동.
- 재구성: 남은 요소를 다시 힙 구조로 정렬.
해시 테이블
- 데이터 저장 및 탐색을 효율적으로 할 수 있는 구조. 큰 범위의 데이터를 다 저장할 수 없을 때 일부만 테이블에 저장하는 방식.
1. Build-Max-Heap(A): 최대 힙 구성 과정
2. for i ← ⌊length[A] / 2⌋ downto 1
3. do Max-Heapify(A, i)
설명:
- 1번 라인: 힙 크기(heap-size)는 배열의 길이와 같게 설정합니다. 배열의 모든 요소를 힙 구조로 변환해야 하기 때문입니다.
- 2번 라인: 힙의 마지막 내부 노드부터 시작하여 Max-Heapify를 실행합니다. 이때, 배열의 중간부터 시작하는 이유는 리프 노드(자식이 없는 노드)에서는 Max-Heapify가 필요 없기 때문입니다.
- 힙의 마지막 부모 노드의 인덱스는 length[A] / 2입니다.
- 3번 라인: 각 노드에 대해 Max-Heapify를 호출하여 최대 힙을 구성합니다. 자식보다 부모가 더 큰 성질을 유지하게끔 만듭니다.
2. Max-Heapify (맥스-히피파이) 힙 성질 유지
Max-Heapify는 최대 힙 성질을 위반한 이진 트리를 복구하는 알고리즘입니다. 즉, 트리 내에서 특정 노드가 힙 성질을 위반했을 때, 그 노드와 자식 노드들 간의 관계를 수정하여 최대 힙 성질을 복원하는 과정입니다.
- 언제 사용하나요?
- 새로운 요소가 추가되거나, 기존 요소가 삭제될 때 힙의 성질이 깨질 수 있습니다. 이때 Max-Heapify를 호출하여 루트부터 자식 노드들까지 힙 성질을 유지하도록 만듭니다.
- 작동 방식:
- 특정 노드에서 시작해서 그 자식 노드들 중 더 큰 값과 교환을 하며 아래로 내려갑니다. 이를 통해 위에서 아래로 트리를 정렬하는 방식으로 힙 성질을 유지합니다.
1. l ← LEFT(i)
2. r ← RIGHT(i)
3. if l ≤ heap-size[A] and A[l] > A[i]
4. then largest ← l
5. else largest ← i
6. if r ≤ heap-size[A] and A[r] > A[largest]
7. then largest ← r
8. if largest ≠ i
9. then exchange A[i] ↔ A[largest]
10. Max-Heapify(A, largest)
설명:
- 1, 2번 라인: 노드 i의 왼쪽 자식(l)과 오른쪽 자식(r)의 인덱스를 계산합니다.
- 3, 4, 5번 라인: 왼쪽 자식이 힙 크기 내에 있고, A[l]이 부모 A[i]보다 크다면 largest에 l을 저장합니다. 그렇지 않으면 largest는 i로 설정합니다.
- 6, 7번 라인: 오른쪽 자식이 힙 크기 내에 있고, 오른쪽 자식이 현재 largest로 설정된 값보다 크다면 largest를 오른쪽 자식으로 갱신합니다.
- 8번 라인: 만약 largest가 i와 다르다면, 부모와 자식의 값을 교환합니다.
- 10번 라인: 값이 교환된 자식에 대해서도 Max-Heapify를 재귀적으로 호출하여 힙 성질을 유지합니다.
- Max Heap: 부모 노드가 항상 자식보다 크도록 유지되는 트리 구조.
- Max-Heapify: 부모 노드가 자식들보다 작아 힙 성질이 깨졌을 때 이를 복구하는 과정.
1. 힙 정렬(Heapsort)
- 힙 정렬은 힙 구조를 이용한 정렬 알고리즘입니다. 주로 **최대 힙(Max Heap)**을 사용하여 배열을 정렬합니다.
- 맥스-히피파이(Max-Heapify): 최대 힙의 성질을 유지하기 위해 사용되는 알고리즘입니다. 부모 노드가 자식 노드보다 항상 크도록 배열을 재정렬하는 과정입니다.
- 시간 복잡도는 **O(n log n)**입니다.
2. **유향 그래프(Directed Graph)**와 무향 그래프(Undirected Graph)
- 유향 그래프: 간선에 방향이 있으며, A에서 B로 가는 간선이 있으면 B에서 A로 돌아올 수 없습니다.
- 무향 그래프: 간선에 방향이 없으며, 양방향으로 연결됩니다.
3. DFS(깊이 우선 탐색, Depth First Search)
- DFS는 그래프 탐색 알고리즘으로, 한 노드에서 출발하여 가능한 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색합니다.
- 스택을 사용하거나 재귀적으로 구현할 수 있습니다.
4. 머지 소트(Mergesort)
- 분할 정복(Divide and Conquer) 기법을 사용하는 정렬 알고리즘입니다.
- 배열을 절반으로 나누고, 각각을 정렬한 후 다시 합치는 방식입니다.
- 시간 복잡도는 **O(n log n)**입니다.
5. 자료구조(Data Structure)의 두 가지 관점
- 데이터 구성의 관점: 데이터를 어떻게 효율적으로 저장하고 관리할 것인가에 대한 관점입니다.
- 연산의 관점: 데이터를 기반으로 삽입(Insert), 삭제(Delete), 탐색(Search) 등의 연산을 어떻게 효율적으로 수행할 수 있을지에 대한 관점입니다.
6. 다이나믹 셋(Dynamic Set)
- 시간에 따라 변하는 집합으로, 삽입과 삭제가 자연스럽게 일어나는 데이터 구조입니다.
- 다이나믹 셋은 시간이 지남에 따라 변화할 수 있는 집합을 의미합니다. 이 집합은 데이터를 삽입하거나 삭제할 수 있으며, 집합의 크기가 동적으로 변할 수 있습니다. 다이나믹 셋에서 가장 중요한 것은 데이터의 삽입(insert), 삭제(delete), 탐색(search) 등의 연산을 효율적으로 처리할 수 있어야 한다는 점입니다.
다이나믹 셋에서의 주요 연산
- 삽입(Insert): 새로운 요소를 집합에 추가하는 연산입니다. 이 연산은 집합에 동적으로 새로운 값을 추가해야 할 때 사용됩니다.
- 삭제(Delete): 특정 요소를 집합에서 제거하는 연산입니다. 삽입된 데이터를 삭제할 때 사용하는 연산입니다.
- 탐색(Search): 집합 내에 특정 요소가 있는지 확인하는 연산입니다. 주어진 키(key) 값으로 해당 값을 찾는 것이 목적입니다.
- 최소값(Minimum), 최대값(Maximum): 집합 내에서 가장 작은 값 또는 가장 큰 값을 찾는 연산입니다.
- 전임자(Predecessor), 후임자(Successor): 주어진 요소보다 작은 값 중에서 가장 큰 값(전임자) 또는 주어진 요소보다 큰 값 중에서 가장 작은 값(후임자)을 찾는 연산입니다.
다이나믹 셋이 자주 사용되는 자료 구조
- 이진 탐색 트리(BST: Binary Search Tree): 삽입, 삭제, 탐색을 각각 평균 O(log n) 시간 내에 처리할 수 있는 이진 트리 자료 구조입니다. 대표적으로 AVL 트리나 레드-블랙 트리가 다이나믹 셋을 구현하는 데 사용됩니다.
- 해시 테이블(Hash Table): 삽입, 삭제, 탐색이 평균 O(1) 시간 내에 가능하며, 충돌이 발생할 경우 체이닝(Chaining)이나 오픈 어드레싱(Open Addressing)을 사용하여 해결합니다.
- 우선순위 큐(Priority Queue): 힙(heap) 자료 구조를 사용하여 다이나믹 셋을 구현할 수 있습니다. 삽입과 삭제가 효율적으로 이루어질 수 있으며, 최소값이나 최대값을 빠르게 찾을 수 있습니다.
7. 딕셔너리(Dictionary) (데이터 구조 관점)
- 딕셔너리는 키(Key)-값(Value) 쌍으로 데이터를 저장하는 데이터 구조입니다.
- 삽입, 삭제, 탐색을 빠르게 수행할 수 있도록 설계되어 있습니다.
- 다이렉트 어드레스 테이블의 동작 원리를 설명하고, 공간 복잡도의 장단점을 논하시오.
- 다이렉트 어드레스 테이블과 해시 테이블의 차이점을 설명하시오.
- 다이렉트 어드레스 테이블은 각 키를 배열의 인덱스와 일치시키는 방식으로 저장합니다. 키가 매우 크거나 키의 범위가 넓을 때 메모리 낭비가 심할 수 있다는 단점이 있지만, 직접 접근 방식이므로 조회, 삽입, 삭제는 **O(1)**의 시간 복잡도를 가집니다. 해시 테이블은 이 메모리 낭비 문제를 해결하기 위해 더 작은 크기의 테이블에서 해시 함수를 사용하여 키를 저장합니다.
해시테이블의 충돌 해결방법중 체이닝(위) 오픈어드레싱의 차이를 설명하시오
체이닝 방식은 해시 테이블에서 같은 해시 값이 나오는 키들이 존재할 때, 해당 키들을 연결 리스트로 연결하여 충돌을 해결합니다. 이 방법은 각 슬롯이 리스트를 포함하므로 해시 테이블의 크기보다 많은 키를 저장할 수 있으며, 적절한 해시 함수와 함께 사용할 경우 평균적으로 **O(1)**의 성능을 보장합니다. 오픈 어드레싱은 충돌이 발생하면 테이블 내의 빈 슬롯을 찾아 키를 저장하는 방식으로, 메모리를 더 적게 사용하지만, 충돌이 많이 발생할 경우 성능이 저하될 수 있습니다.
예상 문제 유형
문제 1:
체이닝(Chaining) 방식과 오픈 어드레싱(Open Addressing) 방식을 사용한 해시 테이블의 충돌 해결 방법을 설명하시오. 또한 각 방식의 장단점과 시간 복잡도에 대해 논하시오.
답안:
- 체이닝(Chaining): 각 슬롯에 연결 리스트를 사용하여 충돌을 해결하는 방식입니다. 충돌이 발생하면 해당 슬롯의 리스트에 요소를 삽입합니다. 장점으로는 슬롯의 크기에 구애받지 않고 많은 요소를 저장할 수 있다는 점이 있으며, 탐색, 삽입, 삭제의 평균 시간 복잡도는 **O(1)**입니다. 단점으로는 최악의 경우 충돌이 많이 발생하면 **O(n)**의 성능 저하가 발생할 수 있습니다.
- 오픈 어드레싱(Open Addressing): 해시 테이블 내에서 빈 슬롯을 찾아 데이터를 저장하는 방식입니다. 장점으로는 모든 데이터가 테이블 내에 저장되기 때문에 메모리 절약이 가능하다는 점이 있습니다. 그러나 충돌이 많이 발생하면 탐색 시간이 길어질 수 있으며, 이 경우 시간 복잡도는 최악의 경우 **O(n)**이 될 수 있습니다.
문제 2:
체이닝 방식에서 Chained-Hash-Insert, Chained-Hash-Search, Chained-Hash-Delete 연산을 설명하고 각 연산의 시간 복잡도를 구하시오.
답안:
- Chained-Hash-Insert(T, x): 해시 함수 h(key[x])에 의해 결정된 슬롯에 x를 삽입합니다. 삽입은 리스트의 앞부분에 추가하므로, 평균적으로 **O(1)**의 시간이 소요됩니다.
- Chained-Hash-Search(T, k): 해시 함수 h(k)에 의해 결정된 슬롯에서 k를 탐색합니다. 해당 슬롯의 연결 리스트를 탐색하는데, 평균적으로 **O(1)**의 시간이 소요되지만, 최악의 경우 리스트 전체를 탐색해야 하므로 **O(n)**이 될 수 있습니다.
- Chained-Hash-Delete(T, x): 해시 함수 h(key[x])에 의해 결정된 슬롯에서 x를 삭제합니다. 연결 리스트에서 요소를 삭제하므로, 평균적으로 **O(1)**의 시간이 소요됩니다.