이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 다익스트라 알고리즘(Dijkstra’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

다익스트라 알고리즘은 너비우선탐색(BFS)을 기본으로 합니다. 하단 좌측과 같은 그래프를 대상으로 다익스트라 알고리즘을 적용해 보겠습니다. 우선 시작노드를 제외한 모든 노드의 거리정보를 무한대로 초기화합니다. 시작노드 $s$를 탐색하고 있다(processing)는 의미로 gray를 칠해둡니다.

(b)를 보겠습니다. 시작노드 $s$를 기준으로 BFS를 적용합니다. $s$에 바로 이웃한 $t$와 $y$에 대해 거리정보를 업데이트한 뒤 $s$ 방문을 마쳤다는 의미로 black을 칠해둡니다. 다음 BFS 적용 대상은 방문하지 않은(white) 노드들 가운데 거리가 최소인 노드입니다. $y$가 5로 가장 작군요. $y$를 탐색하고 있다는 의미로 gray를 칠해둡니다.

(c)를 보겠습니다. $y$에 바로 이웃한 $t,x,z$에 대해 거리정보를 업데이트합니다. 시작노드 $s$와 $t$ 사이의 기존 최단거리는 10이었습니다. 그런데 ($s$와 $y$ 사이의 최단거리)+($y$와 $t$ 사이의 거리)=5+3=8이므로, $s$와 $t$ 사이의 최단거리를 8로 바꾸고, 최단경로를 $y$를 경유하게끔 업데이트합니다(edge relaxation). 나머지 $x,z$도 이렇게 수행합니다. 이후 $y$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 7로 가장 작은 미방문 노드인 $z$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.

(d)를 보겠습니다. $z$를 기준으로 BFS를 적용합니다. $z$에 바로 이웃한 $y,x$에 대해 거리정보를 업데이트합니다. $y$는 이미 방문을 마쳤으므로(black) 건너뛰고 $x$만 처리합니다. $s$와 $x$ 사이의 기존 최단거리는 14였습니다. 그런데 ($s$와 $z$ 사이의 최단거리)+($z$와 $x$ 사이의 거리)=7+6=13으로 기존보다 작으므로, $s$와 $x$ 사이의 최단거리를 13으로 바꾸고, 최단경로를 $z$를 경유하게끔 업데이트합니다. 이후 $z$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 8로 가장 작은 미방문 노드인 $t$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.

(e)를 보겠습니다. $t$를 기준으로 BFS를 적용합니다. $t$에 바로 이웃한 $x$에 대해 거리정보를 업데이트합니다. $s$와 $x$ 사이의 기존 최단거리는 13였습니다. 그런데 ($s$와 $t$ 사이의 최단거리)+($t$와 $x$ 사이의 거리)=8+1=9로 기존보다 작으므로, $s$와 $x$ 사이의 최단거리를 9로 바꾸고, 최단경로를 $t$를 경유하게끔 업데이트합니다. 이후 $t$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 9로 가장 작은 미방문 노드인 $x$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.

마지막으로 (f)를 보겠습니다. $x$를 기준으로 BFS를 적용합니다. $x$에 바로 이웃한 $z$에 대해 거리정보를 업데이트합니다. 그런데 $z$는 이미 방문을 마쳤으므로 건너뜁니다. 더 이상 처리할 이웃노드가 없으므로 $x$ 탐색을 마치고 black을 칠해 둡니다.

이로써 모든 노드 방문을 마쳤습니다. 다익스트라 알고리즘을 종료합니다. 다익스트라 알고리즘의 의사코드는 다음과 같습니다.

계산복잡성

하나의 노드에 대해 다익스트라 알고리즘을 수행하는 경우를 따져보겠습니다. 미방문노드 가운데 거리가 가장 작은 노드에 BFS를 적용합니다. 거리를 가장 작은 미방문노드를 가려내려면 최악의 경우 노드 전체를 모두 따져봐야 하므로 $O($|$V$|$)$입니다. 선택된 노드의 모든 이웃노드들에 대해 최단경로 정보를 업데이트합니다. 한 노드당 엣지의 기대값은 |$E$|/|$V$|입니다.

다익스트라 알고리즘은 이러한 연산을 전체 노드 수만큼 반복하므로 전체적인 계산복잡성은 $O($|$V$|$^2+$|$E$|$)$가 됩니다. 보통의 dense graph는 엣지의 수가 노드 수의 제곱만큼 있으므로 간략하게 계산복잡성을 적으면 $O($|$V$|$^2)$이 됩니다.

단점

다익스트라 알고리즘의 최대 단점은 가중치가 음수인 경우 작동하지 않는다는 점입니다. 이를 도식화한 그림은 다음과 같습니다.

만일 음수인 가중치를 갖는 엣지가 포함된 그래프에 대해 다익스트라 알고리즘을 적용하려고 할 경우, 그래프 전체에서 가장 작은 가중치의 절대값만큼을 모든 엣지 가중치에 더해준 뒤 다익스트라 알고리즘을 적용하고, 적용이 끝난 이후 해당 절대값만큼을 다시 빼서 결과를 내는 방식으로 수행할 수도 있습니다.

이번 글에서는 최단 경로 문제(Shortest Path Problem)를 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

최단거리 문제

최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다. 가중치가 있는 그래프(Weighted Graph)에서는 엣지 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적입니다. 최단 경로 문제엔 다음과 같은 변종들이 존재합니다.

• 단일 출발(single-source) 최단경로 : 단일 노드 $v$에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제.
• 단일 도착(single-destination) 최단경로 : 모든 노드들로부터 출발하여 그래프 내의 한 단일 노드 $v$로 도착하는 가장 짧은 경로를 찾는 문제. 그래프 내의 노드들을 거꾸로 뒤집으면 단일 출발 최단경로문제와 동일.
• 단일 쌍(single-pair) 최단 경로 : 주어진 꼭지점 $u$와 $v$에 대해 $u$에서 $v$까지의 최단 경로를 찾는 문제.
• 전체 쌍(all-pair) 최단 경로 : 그래프 내 모든 노드 쌍들 사이의 최단 경로를 찾는 문제.

다익스트라 알고리즘, 벨만-포드 알고리즘은 여기서 단일 출발 최단경로 문제를 푸는 데 적합합니다. 하지만 여기에서 조금 더 응용하면 나머지 세 문제도 풀 수 있습니다.

optimal substructure

여기에서 최단거리의 중요한 속성을 하나 짚고 넘어가겠습니다. 다익스트라 알고리즘이나 벨만-포드 알고리즘이 최단 경로를 찾을 때 써먹는 핵심 정리이기도 합니다.

• 최단경로의 부분 경로는 역시 최단경로이다.

이를 나타낸 예시 그림이 다음 그림입니다. 아래 그림에서 직선은 엣지, 물결선은 경로를 나타냅니다. 각 숫자는 가중치를 나타냅니다.

엣지 가중치 합이 최소인 최단경로는 굵게 표시된 상단 첫번째 경로임을 알 수 있습니다. 만약 그렇다면 시작노드로부터 중간에 있는 노드에 이르기까지의 경로(그 가중치는 5) 또한 최단경로라는 것이 위 정리의 핵심입니다.

위 정리를 증명한 내용은 다음과 같습니다.

위 정리를 확장하면 최단경로를 다음과 같이 분해(decompostion)할 수 있습니다. 시작노드 $s$에서 $v$에 이르는 최단경로는 $s$에서 $u$까지의 최단경로에 $u$에서 $v$ 사이의 가중치(거리)를 더한 값이라는 겁니다.

\(D\left( s,v \right) =D\left( s,u \right) +w\left( u,v \right)\) 만약 위 식 우변의 값(현재 step에서 구한 새로운 경로의 거리)이 좌변(기존 최단경로의 거리)보다 작다면 최단경로를 업데이트해 줍니다. 이렇게 노드별로 하나씩 구해 확장해 나가면 $s$에서 $v$ 사이의 최단경로를 구할 수 있습니다.

이와 같이 어떤 문제의 최적해가 그 부분문제들의 최적해들로 구성(construct)될 수 있다면 해당 문제는 optimal substructure를 가진다고 말합니다. 이 속성을 가지고 다이내믹 프로그래밍(dynamic programming)이나 탐욕 알고리즘을 적용해 문제를 효율적으로 풀 수 있습니다.

edge relaxation

최단경로를 구하는 알고리즘은 edge relaxation(변 경감)을 기본 연산으로 합니다. 이는 지금까지 이야기한 최단경로 문제의 optimal structure에서 파생된 것입니다.

우선 시작노드 $s$에서 임의의 노드 $z$로의 최단경로를 구한다고 칩시다. 그리고 현재 시점에서 우리가 알고 있는 $s,z$ 사이의 최단거리 $d(z)$는 75, $s,u$ 사이의 최단거리 $d(u)$는 50이라고 두겠습니다.

그런데 탐색 과정에서 엣지 $e$를 경유하는 경로의 거리가 총 60이라고 한다면, 기존에 우리가 알고 있는 $d(z)$보다 짧아서 기존 $d(z)$가 최단경로라고 말할 수 없게 됩니다. 이에 최단경로를 구성하고 있는 노드와 엣지 정보, 그리고 거리의 합을 업데이트해줍니다. 이것이 바로 edge relaxation입니다.

edge relaxation은 최단경로 알고리즘을 수행하는 과정에서 경로를 구성하고 있는 엣지 가중치의 합을 줄여나간다(relax)는 취지로 이런 이름이 붙은 것 같습니다.

알고리즘 특성별 비교

최단경로 알고리즘은 크게 다익스트라와 벨만-포드 알고리즘 두 가지가 있습니다. 다익스트라 알고리즘은 엣지 가중치가 음수일 경우 동작하지 않습니다. 벨만-포드 알고리즘의 경우 엣지 가중치가 음수여도 동작하나, negative cycle이 있을 경우 동작하지 않습니다. 다익스트라 알고리즘의 계산복잡성은 $O($|$V$|$^2+$|$E$|$)$이며, 벨만-포드는 $O($|$V$||$E$|$)$입니다.

전체쌍 최단경로

전체쌍(All-pair) 최단경로 문제는 Floyd-Warshall 알고리즘이 널리 쓰인다고 합니다. 최단경로 문제의 optimal substructure를 활용한 것으로 의사코드는 다음과 같습니다.

작동 예시는 다음과 같습니다.

다만 노드가 다르다면 단일쌍 최단경로 문제는 서로 독립적이기 때문에, 최근엔 단일쌍 문제에 적합한 다익스트라/벨만-포드 알고리즘을 GPU를 활용해 병렬처리하는 방식으로 전체쌍 최단경로를 푸는 경우가 많다고 합니다.

이번 글에서는 그래프(Graph)의 연결요소(Connected Components)를 찾아내는 기법을 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

연결요소란 원그래프 $G$ 가운데 노드와 엣지가 서로 겹치지 않는 부그래프이되, 부그래프 내 모든 노드쌍에 대해 경로가 존재하는 걸 가리킵니다. 연결요소를 구축하는 기법은 디스조인트 셋(Disjoint Set)으로 구현하게 됩니다. 예컨대 원그래프 $G$에 아래와 같은 연결요소들 4개가 있다고 칩시다.

연결요소를 구축하는 알고리즘은 엣지를 중심으로 수행합니다. 위 그래프의 엣지 리스트는 다음과 같습니다.

• ($b, d$)
• ($e, g$)
• ($a,c$)
• ($h,i$)
• ($a,b$)
• ($e,f$)
• ($b,c$)

우선 모든 노드에 대해 make-set 연산을 수행합니다. 각 노드를 유일한 원소로 하는 새로운 셋을 만든다는 뜻입니다.

• {$a$}, {$b$}, {$c$}, {$d$}, {$e$}, {$f$}, {$g$}, {$h$}, {$i$}, {$j$}

이제 그래프 내 모든 엣지를 하나씩 검토합니다. 우선 첫번째 엣지인 ($b,d$)를 보겠습니다. 노드 $b$가 속한 셋의 대표값(루트노드)을 찾습니다(find 연산). 그리고 $c$의 대표값을 찾습니다. 둘을 비교하니 서로 다르므로($b≠c$) 두 셋을 합칩니다(union 연산). 결과는 다음과 같습니다.

• {$a$}, {$b,d$}, {$c$}, {$e$}, {$f$}, {$g$}, {$h$}, {$i$}, {$j$}

다음 ($e,g$)를 보겠습니다. $e$가 포함된 셋과 $g$의 셋이 서로 다르므로 두 셋을 합칩니다. ($a,c$), ($h,i$), ($a,b$), ($e,f$)도 마찬가지입니다. 다음과 같습니다.

• {$a,b,c,d$}, {$e,f,g$}, {$h,i$}, {$j$}

마지막으로 ($b,c$)를 보겠습니다. $b$가 포함된 셋의 루트노드와 $c$가 포함된 셋의 루트노드가 $a$로 서로 같습니다. 이대로 연산을 마칩니다. 다음과 같습니다.

• {$a,b,c,d$}, {$e,f,g$}, {$h,i$}, {$j$}

이렇게 만든 연결요소가 있고, 임의의 노드 $u$와 $v$가 같은 연결요소 내에 있는지 여부를 가려내려면 다음과 같이 수행합니다.

• find(u)와 find(v)가 같은 결과이면 True
• 그렇지 않으면 False

이번 글에서는 그래프(Graph)의 강연결요소(Strongly Connected Components, SCC)를 찾아내는 기법을 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

방향그래프(Directed Graph)의 연결요소(connected component) 내 노드 $u$에서 $v$로 향하는 경로와 $v$에서 $u$로의 경로가 존재한다면 해당 연결요소를 강연결요소라고 합니다. 예컨대 다음 그림에서는 총 네 개의 강연결요소가 있습니다. 그래프가 주어졌을 때 해당 그래프의 강연결요소를 찾아내는 것이 이 글의 목적입니다.

강연결요소를 찾아내는 기법의 핵심 아이디어는 다음 그림과 같습니다. 원그래프 $G$의 노드 $a$에서 $b$로 향하는 경로가 있습니다. 그런데 엣지 방향을 정반대로 바꾼 $G^T$를 분석해본 결과도 역시 $a$에서 $b$로 갈 수 있다(다이렉트로 가지 못하고 여러 노드를 거쳐 가더라도 관계 없음)고 칩시다. 그렇다면 $a$와 $b$ 사이에는 사이클(cycle)이 있어 강연결요소 속성을 만족한다는 것입니다.

algorithm

강연결요소는 깊이우선탐색(Depth First Search)을 기본으로 해서 구합니다. 우선 주어진 그래프에 대해 DFS를 적용합니다. 다음과 같습니다. 아래 예제 그래프의 경우 노드 안에 적혀진 숫자가 각각 DFS 알고리즘의 start time, finish time이 됩니다(음영처리로 클러스터를 표시한 부분은 일단 무시).

이후 다음 두 가지 작업을 수행합니다.

• 그래프를 transpose한다. 다시 말해 노드는 그대로 놔두고 엣지 방향만 바꾼다. (인접행렬을 transpose한다는 의미)
• transpse한 그래프를 대상으로 DFS를 한번 더 수행한다. 기존 적용한 DFS의 finish time을 내림차순 정렬해 그 순서대로 DFS를 수행한다.

이 점 염두에 두고 다음 그림을 보겠습니다. 주어진 그래프를 transpose했으므로 엣지 방향이 위 그림과 반대임을 확인할 수 있습니다. finish time 기준 내림차순으로 DFS를 수행하므로, finish time이 16으로 가장 큰 $b$가 첫번째 대상입니다. $e$까지 순회하면 더 이상 방문할 노드가 없으므로 미방문 노드들 가운데 finish time이 9로 가장 큰 $d$를 대상으로 순회합니다. 마찬가지로 $g$와 $h$에 대해서도 같은 방식으로 각각 수행해주면 DFS가 끝납니다.

이 결과를 기존 그래프에 DFS를 수행한 것과 비교합니다. 여기서 두 결과 모두 서로 도달 가능한 노드들을 클러스터한 것이 음영처리된 부분입니다.

강연결요소끼리는 어떤 방향에서든 서로 도달가능하기 때문에 다음과 같이 그래프 정보를 압축하는 데 요긴하게 쓰일 수 있습니다.

이번 글에서는 탐욕 알고리즘(Greedy Algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

탐욕 알고리즘이란 매순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법을 가리킵니다. 탐욕 알고리즘이 잘 작동하는 문제는 greedy choice property와 optimal substructure 두 가지 속성을 만족합니다. 전자의 경우 앞의 선택이 이후 선택에 영향을 주지 않는다는 걸 의미하고, 후자는 문제 전체에 대한 최적해(global optimum)가 부분문제에 대해서도 역시 최적해가 된다는 걸 뜻합니다.

예컨대 분할가능 배낭문제(Fractional knapsack problem)가 대표적인 탐욕 알고리즘의 사례에 속합니다. 배낭문제는 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제인데요. 분할가능 배낭문제는 짐을 쪼갤 수 있는 경우에 해당합니다.

분할가능 배낭문제는 단위 무게당 값어치가 가장 큰 짐을 먼저 넣으면 되는데요. 순간순간의 선택이 이후 선택에 영향을 주지 않고, 순간순간의 최적 선택이 전체 문제 최적해와 일치합니다. 따라서 분할가능 배낭문제는 탐욕 알고리즘으로 풀 수가 있습니다.

반면 짐을 쪼갤 수 없는 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라고 합니다. 짐을 쪼갤 수 없기 때문에 가능한 모든 조합에 대해 일일이 따져본 후에 가치의 합이 최대가 되도록 하는 조합을 찾는 문제가 되는데, 이 때는 동적계획법(dynamic programming)으로 문제를 풀게 됩니다. 다시 말해 모든 경우의 수를 따져보되 중간계산 결과를 저장해 두었다가 이를 다시 써먹는 방식으로 계산량 감소를 유도하는 전략입니다.

이 글에서는 탐욕 알고리즘의 대표 예시인 Activity-Selection Problem과 Huffman Coding에 대해 살펴보도록 하겠습니다.

Activity-Selection Problem

교실할당(classroom assignment)로도 불립니다. 한정된 교실 공간 내에서 최대 수업을 배정하는 문제입니다. 예컨대 9개 수업이 있고, 시작시간 $s$와 종료시간 $f$가 다음과 같이 주어졌다고 칩시다(종료시간 기준으로 오름차순 정렬).

종료시간이 가장 빠른 수업을 먼저 배치하게 되면 교실 가용시간은 항상 최대가 됩니다. 종료시간이 빠른 수업부터 차례로 배정하기 때문에 앞의 선택이 이후 선택에 변화를 주지 않고, 매순간 선택이 항상 최적이 됩니다. 이 문제는 탐욕 알고리즘 속성을 만족한다는 이야기이죠.

어쨌든 종료시간을 오름차순으로 정렬해 수업을 배정하면 다음과 같은 그림이 됩니다.

탐욕 알고리즘을 적용한 결과 한 교실에 배정할 수 있는 최대 수업의 조합은 $a_1, a_3, a_6, a_8$인 걸 확인할 수 있습니다. 물론 $a_2, a_5, a_7, a_8$ 또한 가능합니다만, $a_1$을 기본 결과값으로 포함시킨 앞의 결과보다 더 나은 해라고 할 수는 없습니다..

이 문제의 계산복잡성은 $O(n)$입니다. 첫번째 수업을 기본 결과값으로 포함시키고, 첫 수업과 나머지 $n-1$개 수업이 겹치는지 여부만 확인하면 되기 때문입니다.

Huffman Coding

허프만 코딩이란 탐욕 알고리즘을 사용해서 데이터를 압축하는 기법입니다. 기본 컨셉은 다음과 같습니다. 예컨대 우리가 가진 데이터는 네 가지 문자(A, B, C, D)만 있다고 칩시다. 정석대로 문자 인코딩을 하는 상황이라면 다음과 같이 글자 하나당 2비트가 필요할 겁니다.

그런데 데이터의 문자별 빈도는 각각 다음과 같다고 칩시다.

위의 경우 전체 데이터를 저장하는 데 총 24비트($6×2+2×2+3×2+1×2$)가 필요합니다. 이제 허프만 코딩을 적용해 빈도가 높은 문자는 적은 비트를 할당한다고 치겠습니다. 다음과 같습니다.

허프만 코딩 적용 결과 전체 데이터를 저장하는 데 총 21비트($6×1+2×3+3×2+1×3$)가 필요합니다. 기존보다 3비트를 줄이는 데 성공했습니다. 압축률은 데이터가 클 수록 좋아질 것입니다.

허프만 코딩 수행 과정은 다음과 같습니다. 예컨대 데이터의 문자별 빈도가 다음과 같다고 치겠습니다.

허프만 코딩을 하려면 다음 그림과 같이 트리를 구축합니다. 우선 가장 빈도가 낮은 H를 말단 왼쪽 노드로 선택합니다. 말단 오른쪽 노드엔 그 다음 적은 F를 놓습니다. 이 둘의 부모노드는 둘의 빈도를 합친 5가 됩니다.

이번엔 이 부모노드(5)를 포함해 가장 작은 값(5)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 B를 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 11이 됩니다.

이번엔 이 부모노드(11)를 포함해 가장 작은 값(G)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 C를 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 13이 됩니다.

이번엔 이 부모노드(13)을 포함해 가장 작은 값(11)를 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 D를 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 23이 됩니다.

이번엔 이 부모노드(23)을 포함해 가장 작은 값(I)를 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 23을 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 38이 됩니다.

이번엔 이 부모노드(38)을 포함해 가장 작은 값(E)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 28을 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 53이 됩니다.

이번엔 이 부모노드(53)을 포함해 가장 작은 값(38)을 왼쪽 노드로 선택합니다. 오른쪽 노드엔 그 다음 적은 53을 놓습니다. 이 둘의 부모노드는 둘의 값을 합친 91이 됩니다.

문자 각각의 코딩 결과는 예컨대 다음과 같습니다. 빈도가 클 수록 그 길이가 짧은 걸 확인할 수 있습니다.

• H : 01000
• G : 1100
• E : 10

허프만 코딩의 계산복잡성은 $O(n\log{n})$입니다.