다익스트라 (Dijkstra's Algorithm)
- 다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 그리디 알고리즘이다. 이 알고리즘은 항상 현재 상태에서 가장 비용이 적은 노드를 선택하는 방식으로 동작한다.
- 시작 노드를 설정하고, 시작 노드에서 직접 연결된 모든 노드까지의 거리를 초기화한다.
- 미방문 노드 중에서 현재까지의 최단 거리가 가장 짧은 노드를 선택한다.
- 선택한 노드를 방문 처리하고, 이 노드를 거쳐 갈 수 있는 다른 노드들의 최단 거리를 갱신한다.
- 모든 노드를 방문할 때까지 2-3 과정을 반복한다.
- touch[i]: 노드 i로 가는 최단 경로에서 i 직전에 방문하는 노드 번호
- length[i]: 시작 노드(v₁)에서 노드 i까지의 현재까지 발견된 최단 거리
- F: 최단 경로가 확정된 노드들의 집합
- vnear: 현재 탐색 중인, 미방문 노드 중 시작점으로부터 거리가 가장 가까운 노드
- 초기화:
- touch[2..n]을 1로 설정 (모든 노드는 처음에는 시작 노드에서 직접 연결된다고 가정)
- length[2..n]을 W[1][i]로 설정 (시작 노드에서 각 노드까지의 직접 연결 거리)
- F를 빈 집합으로 초기화
- 주 반복문:
- 미방문 노드 중 length 값이 가장 작은 노드 vnear를 찾는다.
- (touch[vnear], vnear) 간선을 F에 추가한다.
- vnear를 통해 다른 미방문 노드들의 최단 경로를 갱신한다:
- 각 노드 i에 대해, length[vnear] + W[vnear][i] < length[i]이면
- length[i] = length[vnear] + W[vnear][i]로 갱신
- touch[i] = vnear로 설정
- length[vnear]를 -1로 설정하여 해당 노드를 처리 완료로 표시한다.
- 시작 노드 v₁에서 출발하여 단계적으로 최단 경로를 찾아나간다.
- 첫 단계에서 v₁과 직접 연결된 노드들(v₂, v₃, v₅)까지의 거리를 초기화한다.
- 초기화 이후 가장 거리가 짧은 v₅를 선택하고(거리 1), 이를 통해 v₄까지의 경로를 갱신한다.
- 다음으로 거리가 짧은 v₄를 선택하고(거리 2), 이를 통해 다른 노드들의 최단 경로를 갱신한다.
- 이 과정을 반복하여 v₁에서 v₂까지의 최단 경로 [v₁, v₅, v₄, v₃, v₂]를 찾는다.
허프만 코딩 (Huffman Coding)
허프만 코딩은 문자의 출현 빈도에 따라 가변 길이 코드를 할당하는 데이터 압축 알고리즘이다. 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당하여 전체 데이터 크기를 최소화한다.
알고리즘 원리:
- 각 문자와 그 출현 빈도수를 리프 노드로 하는 초기 포레스트를 구성한다.
- 출현 빈도가 가장 낮은 두 노드를 선택하여 이들을 자식으로 하는 새로운 노드를 생성한다. 이 새 노드의 빈도는 두 자식 노드 빈도의 합이다.
- 새 노드를 포레스트에 추가하고 선택된 두 노드를 제거한다.
- 포레스트에 단 하나의 노드만 남을 때까지 2-3 과정을 반복한다.
- 이렇게 구성된 이진 트리에서 루트에서 각 리프 노드까지의 경로를 코드워드로 사용한다. 왼쪽 간선은 '0', 오른쪽 간선은 '1'로 표현한다.
허프만 코드 구축 단계:
- 빈도수가 가장 낮은 두 노드 b-5와 e-10을 선택하여 합친다. 새 노드의 값은 15이다.
- 다음으로 빈도수가 낮은 두 노드 c-12와 15(b-5+e-10)를 선택하여 합친다. 새 노드의 값은 27이다.
- 다음으로 a-16과 d-17을 선택하여 합친다. 새 노드의 값은 33이다.
- 마지막으로 f-25와 27(c-12+(b-5+e-10))을 선택하여 합친다. 새 노드의 값은 52이다.
- 최종적으로 33(a-16+d-17)과 52(f-25+(c-12+(b-5+e-10)))를 합쳐 루트 노드 85를 생성한다.
트리가 완성되면 왼쪽 간선을 '0', 오른쪽 간선을 '1'로 간주하여 각 문자의 코드를 생성한다. 예를 들어, 'b'의 코드는 '100'이 된다.
이 코드는 힙 자료구조를 사용하여 빈도수가 낮은 노드들을 효율적으로 선택한다.
0-1 배낭 문제 (Knapsack Problem)
0-1 배낭 문제는 각 물품을 통째로 넣거나 넣지 않는 방식으로, 주어진 무게 제한 내에서 가치의 합이 최대가 되도록 물품을 선택하는 문제이다.
0-1 배낭 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결한다. 점화식은 다음과 같다:
여기서:
- P[n][W]: n개의 물품과 배낭 용량 W를 고려할 때 얻을 수 있는 최대 가치
- p_n: n번째 물품의 가치
- w_n: n번째 물품의 무게
다음은 3개의 물품과 최대 무게 30kg인 배낭 문제를 해결하는 과정을 보여준다:
- 물품 정보:
- item₁: 5kg, 50만원, 단위 무게당 10만원/kg
- item₂: 10kg, 60만원, 단위 무게당 6만원/kg
- item₃: 20kg, 140만원, 단위 무게당 7만원/kg
- 점화식을 사용한 계산:
- P[1][0] = 0 (물품이 없거나 배낭 용량이 0인 경우)
- P[1][10] = max(P[0][10], 50 + P[0][10-5]) = max(0, 50 + 0) = 50
- P[1][20] = max(P[0][20], 50 + P[0][20-5]) = max(0, 50 + 0) = 50
- P[1][30] = max(P[0][30], 50 + P[0][30-5]) = max(0, 50 + 0) = 50
- P[2][10] = max(P[1][10], 60 + P[1][0]) = max(50, 60 + 0) = 60
- P[2][30] = max(P[1][30], 60 + P[1][20]) = max(50, 60 + 50) = 110
- P[3][30] = max(P[2][30], 140 + P[2][10]) = max(110, 140 + 60) = 200
따라서 최대 가치는 200만원으로, item₂와 item₃를 선택하는 것이 최적이다.
- P[n][W]는 n개의 물품과 배낭 용량 W를 고려할 때 얻을 수 있는 최대 가치이다.
- 두 가지 경우를 고려한다:
- n번째 물품의 무게(wn)가 W 이하인 경우: max(n번째 물품을 포함하지 않는 경우, n번째 물품을 포함하는 경우)
- n번째 물품의 무게가 W보다 큰 경우: n번째 물품을 포함하지 않는 경우의 값
상호배타적 집합 (Disjoint Sets)
상호배타적 집합(또는 Union-Find 자료구조)은 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.
주요 연산:
- Find: 어떤 원소가 속한 집합의 대표 원소(루트)를 찾는다.
- Union: 두 집합을 하나로 합친다.
최적화 기법:
- Weighting-Union Heuristic:
- Union 연산 시 작은 집합을 큰 집합에 합친다.
- 이를 통해 트리의 높이를 최소화하여 Find 연산의 효율성을 향상시킨다.
- 시간 복잡도: O(n log n)
- Path Compression:
- Find 연산을 수행할 때, 방문하는 모든 노드들을 루트 노드의 직접적인 자식으로 만든다.
- 이를 통해 이후의 Find 연산이 더 빠르게 수행될 수 있도록 한다.
- 위 그림에서 "path compression 수행 후"라고 표시된 부분에서 이러한 최적화가 적용된 결과를 볼 수 있다.
- Weighting-Union Heuristic: union 연산 시 작은 집합을 큰 집합으로 합쳐 트리의 높이를 최소화한다. 이로 인해 시간 복잡도가 O(n log n)으로 개선된다.
- Path Compression: find(z) 연산을 수행할 때 방문하는 모든 노드들을 루트의 직접적인 자식으로 만든다. 이는 find 연산의 성능을 크게 향상시킨다.
이러한 두 가지 최적화를 함께 사용하면, 연산의 수행 시간이 거의 상수 시간에 가까워진다.
