<div id="readability-page-1" class="page"><div>유용한 링크: <a href="https://math.mit.edu/~shor/PAM/hu-tucker_algorithm.html" target="_blank" rel="noopener">MIT 강의 자료</a>

어떤 문자열이 있고, 각 알파벳에 바이너리를 할당한다. 할당된 바이너리는 어떤 것이 다른 것의 prefix가 되면 안된다. 문자열을 알파벳에 할당된 바이너리로 표현할 때 바이너리의 크기를 최소화하는 문제가 있다. 이는 매우 일반적인 압축 알고리즘을 필요로 하는 상황이다. <a href="https://en.wikipedia.org/wiki/Huffman_coding" target="_blank" rel="noopener">Huffman Coding</a>은 이 문제에 대한 최적해를 $O(N \lg N)$ 시간에 구한다. 각색은 다르지만, Huffman Coding과 같은 상황인 문제는 <a href="https://www.acmicpc.net/problem/13975" target="_blank" rel="noopener">BOJ 13975번 파일 합치기 3</a>이 있다.
<figure id="og_1651513524777" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="Huffman coding - Wikipedia" data-og-description="From Wikipedia, the free encyclopedia Jump to navigation Jump to search Technique to compress data Huffman tree generated from the exact frequencies of the text &quot;this is an example of a huffman tree&quot;. The frequencies and codes of each character are below. " data-og-host="en.wikipedia.org" data-og-source-url="https://en.wikipedia.org/wiki/Huffman_coding" data-og-url="https://en.wikipedia.org/wiki/Huffman_coding" data-og-image="https://scrap.kakaocdn.net/dn/ejpiea/hyOgpI1dLm/LlXLV4phziKz6oUpmiObR1/img.png?width=1200&amp;height=772&amp;face=0_0_1200_772,https://scrap.kakaocdn.net/dn/dLG6GG/hyOgvJewUX/UvlGwWABYecC2uIqQSQaZ0/img.png?width=800&amp;height=515&amp;face=0_0_800_515,https://scrap.kakaocdn.net/dn/cmeRgR/hyOe7DcShZ/1j3KEJF2m9Xl4WMYFmMDG0/img.png?width=640&amp;height=412&amp;face=0_0_640_412"><a href="https://en.wikipedia.org/wiki/Huffman_coding" target="_blank" rel="noopener" data-source-url="https://en.wikipedia.org/wiki/Huffman_coding">

<div>
Huffman coding - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Technique to compress data Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". The frequencies and codes of each character are below.
en.wikipedia.org
</div>
</a><img src="https://scrap.kakaocdn.net/dn/ejpiea/hyOgpI1dLm/LlXLV4phziKz6oUpmiObR1/img.png?width=1200&amp;height=772&amp;face=0_0_1200_772,https://scrap.kakaocdn.net/dn/dLG6GG/hyOgvJewUX/UvlGwWABYecC2uIqQSQaZ0/img.png?width=800&amp;height=515&amp;face=0_0_800_515,https://scrap.kakaocdn.net/dn/cmeRgR/hyOe7DcShZ/1j3KEJF2m9Xl4WMYFmMDG0/img.png?width=640&amp;height=412&amp;face=0_0_640_412"></figure>

Hu-Tucker algorithm은 위와 같은 상황이지만, 알파벳의 순서가 중요한 경우에 필요한 알고리즘이다. 즉, 사전순으로 앞에 오는 알파벳은 할당된 바이너리도 사전순으로 앞에 오도록 하고 싶은 상황에 필요하다. <a href="https://blog.myungwoo.kr/140" target="_blank" rel="noopener">Skew heap</a>을 이용하여 구현하면, $O(N \lg N)$ 시간안에 구현할 수 있다. 마찬가지로 각색은 다르지만, Hu-Tucker algorithm이 필요한 문제로 <a href="https://www.acmicpc.net/problem/19089" target="_blank" rel="noopener">BOJ 19089번 파일 합치기 4</a>가 있다. 상황과 비슷한 각색의 문제로 <a href="https://atcoder.jp/contests/atc002/tasks/atc002_c" target="_blank" rel="noopener">AtCoder Typical Contest 002 C 최적이분탐색트리 문제</a>가 있다. 두 문제가 비슷한 입력 형식을 가지고 있다.

Hu-Tucker algorithm에서 Huffman Coding과 마찬가지로 두 빈도를 합쳐나가는 과정을 반복하지만, 두 수를 합칠 수 있는 조건이 다르다. Huffman Coding에서는 빈도 수가 가장 작은 두 값을 하나로 합쳤었다. Hu-Tucker algorithm에서는 두 수 사이에 기존 수가 하나도 없으면 하나로 합칠 수 있다고 한다. 합칠 수 있는 두 수가 있으면 두 수의 합이 가장 작은 것들부터 합친다. 이해를 돕기 위해 예시 상황을 보자.

다음과 같이 각 알파벳이 등장하는 횟수(빈도)가 있다고 하자.
[1, 2, 23, 4, 3, 3, 5, 19]
초기에는 인접한 두 수만 합칠 수 있다. 인접한 두 수 중 합이 제일 작은 쌍은 (1, 2)다. 둘을 합쳐 3을 넣자.
[3, 23,&nbsp;4,&nbsp;3,&nbsp;3,&nbsp;5,&nbsp;19]
여기서 3은 볼드 처리가 안되어있는데, 이는 기존 수가 아닌 새로 추가된 수임을 의미한다.
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (3, 3)이다. 둘을 합쳐 6을 넣자.
[3, 23,&nbsp;4, 6,&nbsp;5,&nbsp;19]
이 때, 4와 5는 서로 합칠 수 있는데, 4와 5 사이에는 기존 수가 하나도 없기 때문이다. 합이 제일 작은 합칠 수 있는 두 수는 (4, 5)다. 둘을 합쳐 9를 넣자. 9가 들어갈 수 있는 위치는 기존 4와 5 사이 어디든 상관 없다.
[3, 23, 9, 6,&nbsp;19]
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (9, 6)이다. 둘을 합쳐 15를 넣자.
[3, 23, 15, 19]
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (3, 23)이다. 둘을 합쳐 26을 넣자.
[26, 15, 19]
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (15, 19)이다. 둘을 합쳐 34를 넣자.
[26, 34]
마지막으로 합칠 수 있는 두 수는 (26, 34)이다. 둘을 합쳐 60를 넣자.
[60]
수가 하나만 남았으므로 알고리즘은 종료된다.

지금까지 합친 과정을 그림으로 나타내면 다음과 같다:
<figure data-origin-width="328" data-origin-height="278" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/B7kgF/btrA33n4U70/BP1ET2UgKPAjFF4oXoiT81/img.gif" data-ke-mobilestyle="alignCenter"><figcaption>&lt;그림 1&gt; Hu-Tucker algorithm의 초기 결과</figcaption></figure>
이 초기 결과에서 해결해야할 문제가 하나 있다. 바로, 9와 6이 만들어지는 선분들이 서로 교차하고 있기 때문에 이 트리에서 올바른 인코딩을 구할 수 없다. 위 이진트리에서 각 리프 정점에 루트와의 거리(즉, 노드의 깊이이자 할당된 바이너리 길이)를 적어보면 다음과 같다.
[1(3), 2(3), 23(2), 4(4), 3(4), 3(4), 5(4), 19(2)]
이제 이진트리를 올바르게 만들어주기 위해 다음과 같은 과정을 진행한다.
제일 먼저 제일 깊은 깊이가 4인 정점 4개를 순서대로 이어준다.
<figure data-origin-width="148" data-origin-height="91" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/bxKQVQ/btrA6yUEsJe/2axbGACLpcgKHyqVGlpmRk/img.gif" data-ke-mobilestyle="alignCenter"></figure>
깊이가 4인 정점을 2쌍 이어주었기 때문에 깊이가 3인 정점이 2개 더 생겨서 4개 있는 것과 같다.
<figure data-origin-width="290" data-origin-height="93" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/WrSJs/btrA41XfGBH/ep0BxB0lJkPV5tXRhgbiqK/img.gif" data-ke-mobilestyle="alignCenter"></figure>
이제 깊이가 3인 정점 4개를 순서대로 이어준다.
<figure data-origin-width="343" data-origin-height="148" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/ch2tOD/btrA3tmYrZZ/pbCxhE6SXDoJNvtsp8R1M0/img.gif" data-ke-mobilestyle="alignCenter"></figure>
깊이가 2인 정점 4개를 순서대로 이어주고, 깊이가 1인 정점에 대해서도 처리하면 다음과 같은 결과가 나온다.
<figure data-origin-width="353" data-origin-height="251" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/bUfJx8/btrA3hzvtJ4/jL4YHpiL99YePU67UkRWc1/img.gif" data-ke-mobilestyle="alignCenter"><figcaption>&lt;그림 2&gt; Hu-Tucker algorithm의 최종 결과</figcaption></figure>
이 알고리즘이 올바르게 동작하기 위해서 다음 명제들을 증명해야 한다.
1. Hu-Tucker algorithm의 초기 결과에서 위와 같은 방법으로 올바른 트리를 항상 구할 수 있다.
2. Hu-Tucker algorithm의 초기 결과의 비용(각 알파벳의 빈도 수와 할당된 바이너리 길이를 곱한 값들의 합)이 최적해다.
1번 명제에 대한 증명은 <a href="https://math.mit.edu/~shor/PAM/hu-tucker_algorithm.html" target="_blank" rel="noopener">MIT 강의 자료</a>에 나와있고, 2번 명제에 대한 증명은 나와있지 않다. 아무래도 2번 명제에 대한 증명이 매우 까다로운 듯하다. 강의 자료에 따르면 초기 논문들에서 나온 증명은 틀렸다고 한다.

자, 그러면 마지막으로 남은 것은 이것을 구현하는 방법에 대한 것이다. 이 알고리즘은 증명도 까다롭고, 구현도 간단하지 않다. 다음 그림은 Hu-Tucker algorithm의 중간과정을 그림으로 표현한 것이다. 기존 수는 검은 동그라미, 기존 수가 아닌 것은 파란 동그라미로 그려졌다. 초록색 덩어리들을 하나로 묶어서 <a href="https://blog.myungwoo.kr/140" target="_blank" rel="noopener">Skew heap</a>(두 힙을 하나로 합치는데 $O(\lg n)$ 시간이 걸리는 힙)으로 구현이 비교적 간단하다.
<figure data-origin-width="1590" data-origin-height="142" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/cpIpDm/btrAYtHdvNz/dT6saAG16XDE1qHksWVCN1/img.png" data-ke-mobilestyle="alignCenter"><figcaption>&lt;그림 3&gt; Hu-Tucker algorithm 구현 중 Skew heap 관리 방법</figcaption></figure>
초록 직사각형이 하나의 Skew heap을 나타내고, heap 안에는 초록색 직사각형 안에 있는 파란 동그라미에 적힌 빈도수가 들어있다. 자세한 구현은 아래 첨부된 코드를 참고하자. 첨부된 코드는 위에서 소개한 <a href="https://www.acmicpc.net/problem/19089">BOJ 19089번 파일 합치기 4</a>&nbsp;문제를 푸는 코드다.
</div></div>

PS 이야기

유용한 링크: MIT 강의 자료
 
어떤 문자열이 있고, 각 알파벳에 바이너리를 할당한다. 할당된 바이너리는 어떤 것이 다른 것의 prefix가 되면 안된다. 문자열을 알파벳에 할당된 바이너리로 표현할 때 바이너리의 크기를 최소화하는 문제가 있다. 이는 매우 일반적인 압축 알고리즘을 필요로 하는 상황이다. Huffman Coding은 이 문제에 대한 최적해를 $O(N \lg N)$ 시간에 구한다. 각색은 다르지만, Huffman Coding과 같은 상황인 문제는 BOJ 13975번 파일 합치기 3이 있다.
 
Hu-Tucker algorithm은 위와 같은 상황이지만, 알파벳의 순서가 중요한 경우에 필요한 알고리즘이다. 즉, 사전순으로 앞에 오는 알파벳은 할당된 바이너리도 사전순으로 앞에 오도록 하고 싶은 상황에 필요하다. Skew heap을 이용하여 구현하면, $O(N \lg N)$ 시간안에 구현할 수 있다. 마찬가지로 각색은 다르지만, Hu-Tucker algorithm이 필요한 문제로 BOJ 19089번 파일 합치기 4가 있다. 상황과 비슷한 각색의 문제로 AtCoder Typical Contest 002 C 최적이분탐색트리 문제가 있다. 두 문제가 비슷한 입력 형식을 가지고 있다.
 
Hu-Tucker algorithm에서 Huffman Coding과 마찬가지로 두 빈도를 합쳐나가는 과정을 반복하지만, 두 수를 합칠 수 있는 조건이 다르다. Huffman Coding에서는 빈도 수가 가장 작은 두 값을 하나로 합쳤었다. Hu-Tucker algorithm에서는 두 수 사이에 기존 수가 하나도 없으면 하나로 합칠 수 있다고 한다. 합칠 수 있는 두 수가 있으면 두 수의 합이 가장 작은 것들부터 합친다. 이해를 돕기 위해 예시 상황을 보자.
 
다음과 같이 각 알파벳이 등장하는 횟수(빈도)가 있다고 하자.
[1, 2, 23, 4, 3, 3, 5, 19]
초기에는 인접한 두 수만 합칠 수 있다. 인접한 두 수 중 합이 제일 작은 쌍은 (1, 2)다. 둘을 합쳐 3을 넣자.
[3, 23, 4, 3, 3, 5, 19]
여기서 3은 볼드 처리가 안되어있는데, 이는 기존 수가 아닌 새로 추가된 수임을 의미한다.
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (3, 3)이다. 둘을 합쳐 6을 넣자.
[3, 23, 4, 6, 5, 19]
이 때, 4와 5는 서로 합칠 수 있는데, 4와 5 사이에는 기존 수가 하나도 없기 때문이다. 합이 제일 작은 합칠 수 있는 두 수는 (4, 5)다. 둘을 합쳐 9를 넣자. 9가 들어갈 수 있는 위치는 기존 4와 5 사이 어디든 상관 없다.
[3, 23, 9, 6, 19]
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (9, 6)이다. 둘을 합쳐 15를 넣자.
[3, 23, 15, 19]
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (3, 23)이다. 둘을 합쳐 26을 넣자.
[26, 15, 19]
다음으로 합이 제일 작은 합칠 수 있는 두 수는 (15, 19)이다. 둘을 합쳐 34를 넣자.
[26, 34]
마지막으로 합칠 수 있는 두 수는 (26, 34)이다. 둘을 합쳐 60를 넣자.
[60]
수가 하나만 남았으므로 알고리즘은 종료된다.
 
지금까지 합친 과정을 그림으로 나타내면 다음과 같다:
이 초기 결과에서 해결해야할 문제가 하나 있다. 바로, 9와 6이 만들어지는 선분들이 서로 교차하고 있기 때문에 이 트리에서 올바른 인코딩을 구할 수 없다. 위 이진트리에서 각 리프 정점에 루트와의 거리(즉, 노드의 깊이이자 할당된 바이너리 길이)를 적어보면 다음과 같다.
[1(3), 2(3), 23(2), 4(4), 3(4), 3(4), 5(4), 19(2)]
이제 이진트리를 올바르게 만들어주기 위해 다음과 같은 과정을 진행한다.
제일 먼저 제일 깊은 깊이가 4인 정점 4개를 순서대로 이어준다.
깊이가 4인 정점을 2쌍 이어주었기 때문에 깊이가 3인 정점이 2개 더 생겨서 4개 있는 것과 같다.
이제 깊이가 3인 정점 4개를 순서대로 이어준다.
깊이가 2인 정점 4개를 순서대로 이어주고, 깊이가 1인 정점에 대해서도 처리하면 다음과 같은 결과가 나온다.
이 알고리즘이 올바르게 동작하기 위해서 다음 명제들을 증명해야 한다.
1. Hu-Tucker algorithm의 초기 결과에서 위와 같은 방법으로 올바른 트리를 항상 구할 수 있다.
2. Hu-Tucker algorithm의 초기 결과의 비용(각 알파벳의 빈도 수와 할당된 바이너리 길이를 곱한 값들의 합)이 최적해다.
1번 명제에 대한 증명은 MIT 강의 자료에 나와있고, 2번 명제에 대한 증명은 나와있지 않다. 아무래도 2번 명제에 대한 증명이 매우 까다로운 듯하다. 강의 자료에 따르면 초기 논문들에서 나온 증명은 틀렸다고 한다.
 
자, 그러면 마지막으로 남은 것은 이것을 구현하는 방법에 대한 것이다. 이 알고리즘은 증명도 까다롭고, 구현도 간단하지 않다. 다음 그림은 Hu-Tucker algorithm의 중간과정을 그림으로 표현한 것이다. 기존 수는 검은 동그라미, 기존 수가 아닌 것은 파란 동그라미로 그려졌다. 초록색 덩어리들을 하나로 묶어서 Skew heap(두 힙을 하나로 합치는데 $O(\lg n)$ 시간이 걸리는 힙)으로 구현이 비교적 간단하다.
초록 직사각형이 하나의 Skew heap을 나타내고, heap 안에는 초록색 직사각형 안에 있는 파란 동그라미에 적힌 빈도수가 들어있다. 자세한 구현은 아래 첨부된 코드를 참고하자. 첨부된 코드는 위에서 소개한 BOJ 19089번 파일 합치기 4 문제를 푸는 코드다.
더보기
#include <bits/stdc++.h>
using namespace std;
using lld = long long;
template<typename T>
struct SkewHeap{
	using value_t = T;
	struct Node;
	using node_t = Node;
	using nodeptr_t = unique_ptr<node_t>;
	struct Node{
		Node() = default;
		Node(const T& value): value(value){}
		value_t value;
		nodeptr_t left = nullptr, right = nullptr;
		static nodeptr_t merge(nodeptr_t t1, nodeptr_t t2){
			if (t1 == nullptr) return t2;
			if (t2 == nullptr) return t1;
			if (t2->value < t1->value) return merge(move(t2), move(t1));
			nodeptr_t tmp = move(t1->right);
			t1->right = move(t1->left);
			t1->left = merge(move(t2), move(tmp));
			return t1;
		}
	};
	nodeptr_t m_root{};
	size_t m_size{};
	bool empty()const{ return m_size == 0; }
	size_t size()const{ return m_size; }
	value_t top()const{
		return m_root->value;
	}
	value_t second_top()const{
		if (m_root->left == nullptr) return m_root->right->value;
		if (m_root->right == nullptr) return m_root->left->value;
		return min(m_root->left->value, m_root->right->value);
	}
	value_t pop(){
		--m_size;
		auto value = m_root->value;
		m_root = node_t::merge(move(m_root->left), move(m_root->right));
		return value;
	}
	void push(const value_t& value){
		++m_size;
		m_root = node_t::merge(move(m_root), nodeptr_t{new node_t(value)});
	}
	void merge(SkewHeap<value_t>&& other){
		m_size += other.m_size;
		m_root = node_t::merge(move(m_root), move(other.m_root));
		other.m_size = 0;
		other.m_root = nullptr;
	}
};
template<typename T>
struct HuTucker{
	using value_t = T;
	static constexpr value_t inf = numeric_limits<value_t>::max();
	HuTucker(const vector<T>& arr){
		N = size(arr);
		W.resize(N+2); C.resize(N+2); L.resize(N+2); R.resize(N+2);
		for (int i=0;i<N;i++) W[i+1] = arr[i];
		for (int i=0;i<=N;i++) R[i] = i+1, L[i+1] = i;
		W[0] = W[N+1] = inf;
		heaps.resize(N+1);
		for (int i=1;i<N;i++){
			C[i] = W[i]+W[i+1];
			main.emplace(-C[i], i);
		}
	}
	value_t get_min(int i){
		value_t ret = inf;
		if (W[i] != inf && W[R[i]] != inf) ret = min(ret, W[i]+W[R[i]]);
		if (W[i] != inf && heaps[i].size() >= 1) ret = min(ret, W[i]+heaps[i].top());
		if (W[R[i]] != inf && heaps[i].size() >= 1) ret = min(ret, W[R[i]]+heaps[i].top());
		if (heaps[i].size() >= 2) ret = min(ret, heaps[i].top()+heaps[i].second_top());
		return ret;
	}
	value_t solve(){
		value_t ans{};
		for (int elements=N;elements>1;){
			auto [c, i] = main.top(); main.pop(); c = -c;
			if (C[i] != c) continue;
			if (heaps[i].size() >= 2 && heaps[i].top()+heaps[i].second_top() == c){
				heaps[i].pop(); heaps[i].pop();
			}
			else if (W[i] != inf && heaps[i].size() >= 1 && W[i]+heaps[i].top() == c){
				C[i] = W[i] = inf;
				R[L[i]] = R[i];
				L[R[i]] = L[i];
				heaps[i].pop();
				heaps[L[i]].merge(move(heaps[i]));
				i = L[i];
			}
			else if (W[R[i]] != inf && heaps[i].size() >= 1 && W[R[i]]+heaps[i].top() == c){
				C[R[i]] = W[R[i]] = inf;
				heaps[i].pop();
				L[R[R[i]]] = i;
				heaps[i].merge(move(heaps[R[i]]));
				R[i] = R[R[i]];
			}
			else if (W[i] != inf && W[R[i]] != inf && W[i]+W[R[i]] == c){
				C[i] = C[R[i]] = W[i] = W[R[i]] = inf;
				R[L[i]] = R[R[i]];
				L[R[R[i]]] = L[i];
				heaps[i].merge(move(heaps[R[i]]));
				heaps[L[i]].merge(move(heaps[i]));
				i = L[i];
			}
			else assert(0);
			heaps[i].push(c); C[i] = get_min(i);
			main.emplace(-C[i], i);
			--elements; ans += c;
		}
		return ans;
	}
	int N;
	vector<value_t> W, C;
	vector<int> L, R;
	vector<SkewHeap<value_t>> heaps;
	priority_queue<pair<value_t, int>> main;
};
void solve(){
	int n; scanf("%d", &n);
	vector<lld> arr(n);
	for (lld& v: arr) scanf("%lld", &v);
	printf("%lld\n", HuTucker(arr).solve());
}
int main(){
	int T;
	for (scanf("%d", &T);T--;) solve();
}

Hu-Tucker Algorithm

댓글