Boj 1715) 카드 정렬하기

문제

백준 1715

설명

대표적인 압축 알고리즘인 Huffman Coding 의 단순화 버전으로, 이하의 두 풀이는 Wiki 에서 제시한 내용 그대로이다. 사실 굳이 Wiki 를 생각하지 않아도 사용되는 Greedy Strategy 을 알고 있다면 쉽게 도출할 수 있는 풀이이다.

이때 Input 이 정렬되어 있다면 후자의 경우가 시간복잡도가 선형으로 더 빠름에 주목하자.

Greedy Strategy 는 다음과 같다.

• 모든 알파벳(파일)을 Root Node 로 둔다.
• 가장 크기가 작은 두개의 Root Node 를 선택해, 이들의 비용을 합쳐서 새로운 Root Node 를 만든다. 이 Root Node 의 Child 로 선택한 두 Node 를 넣는다.
• 하나의 Tree 가 될 때 까지 반복한다.

증명

이러한 전략이 성립한다는 것은 Huffman Coding Optimal 자료 에서 잘 설명되어 있다. n-1 개의 알파벳에서 이 전략이 성립하면 n 개의 알파벳에서도 성립함을 보이는 수학적 귀납법을 이용해 증명을 한다.

Lemma 1. Tree \(T\) 에 leaf node 인 \(x\), \(y\) 가 있다고 하자. 둘을 교환한 결과가 \(T'\) 라고 하면 총 비용의 변화는 다음과 같다.

\(p(v)\) 는 파일크기를, \(d(v, T)\) 는 트리 \(T\) 에서의 파일 \(v\) 의 깊이를 말한다.

\[\begin{multline} \vert T' \vert - \vert T \vert \\ \shoveleft = p(x)d(y, T) + p(y)d(x, T) - p(x)d(x, T) - p(y)d(y, T) \\ \shoveleft = (p(x) - p(y))(d(y, T) - d(x, T)) \end{multline}\]

Lemma 2. Optimal Tree 중에서 가장 작은 크기를 가진 두 파일이 Sibling 인 것이 반드시 존재한다.

Optimal Tree \(T'\) 에서 가장 작은 크기의 두 파일을 각각 \(x\), \(y\) 라고 하자.

우선 \(x\), \(y\) 는 \(T'\) 에서 가장 깊이가 큰 Node 중에 하나임을 보일 수 있다.

증명은 간단하다. 만약 \(d(x) < d(z)\) 인 임의의 노드 \(z\) 가 존재한다고 해보자. \(x\) 와 \(z\) 를 교환하면 Lemma 1. 에 따라 총 비용이 더 줄어든다. 전제 상 \(p(x) < p(z)\) 이고 \(d(x) < d(z)\) 이기 때문이다. 이는 \(T'\) 가 Optimal Tree 라는 것과 모순되므로 불가능하다. 비슷하게 \(y\) 도 가장 깊은 노드가 된다.

그러면 이제 \(T'\) 에서 \(x\) 의 sibling 이 \(p(x) \leq p(z)\) 인 임의의 노드 \(z\) 라고 하자. 그럼 \(y\) 와 \(z\) 의 위치를 바꿀 수 있다. 그리고 그 결과의 총 비용은 같거나 더 늘어나게 된다. 더 늘어나는 경우 \(T'\) 가 Optimal Tree 라는 가정과 모순된다. 그러므로 \(x\), \(y\) 가 sibling 인 Optimal Tree 는 반드시 존재한다.

Lemma 3. Huffman Encoding 방법은 Optimal Tree 를 만든다.

Huffman 방법을 사용해 Tree 를 만든다고 하자. 이는 Full Binary Tree 이고 Lemma 2. 에 따라서 가장 크기가 작은 두 파일은 sibling 이다. 그래서 이러한 두 파일을 제거할 수 있고 그 결과에서의 leaf node 갯수는 하나가 준다. 이런 과정에서의 leaf node 의 갯수에 따른 귀납법을 사용할 것이다.

남은 Leaf Node 가 1 개라면 Optimal Tree 임은 자명하다.

남은 Leaf Node 가 n 개인 Tree \(T'\) 가 Optimal Tree 라고 하자. 그러면 남은 Leaf Node 가 n+1 개인 Tree \(T\) 도 Optimal Tree 일까? 만약 맞다면 sibling 을 삭제하기 전의 원본 Tree 인 Huffman 방법을 통한 Tree 도 귀납법에 의해 Optimal Tree 가 될 것이다.

n+1 단계에서 삭제되었던 파일 두개를 각각 각각 \(x\), \(y\) 이라고 하고 이 둘의 parent 를 z 라고 하자. 참고로 이 둘은 가장 크기가 작은 파일이 된다.

\(T\) 가 Optimal Tree 가 아니라고 귀류법을 사용해보자. 그럼 남은 Leaf Node n+1 에 대한 Optimal Tree 인 \(Z\) 가 존재한다. 여기서 Lemma 2. 에 따라 \(Z\) 에서 \(x\), \(y\) 에 해당되는 두 Node 는 Sibling 으로 존재한다. 이를 제거한 Tree 를 \(Z'\) 라고 하자.

\[\vert T' \vert = \vert T \vert - \vert x \vert - \vert y \vert > \vert Z \vert - \vert x \vert - \vert y \vert = \vert Z' \vert\]

이때 \(Z'\) 는 \(T'\) 와 같은 노드로 이루어져 있다. 그러므로 \(T'\) 가 Optimal Tree 라는 전제에서 모순이다. 그러므로 \(T\) 는 Optimal Tree 이다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드 1 (우선순위 큐)

int main()
{
	int n; cin >> n;
	priority_queue<int, std::vector<int>, std::greater<int>> q;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a; 
		q.push(a);
	}

	long long ans = 0;
	while (q.size() > 1)
	{
		long long a, b;
		a = q.top(); q.pop();
		b = q.top(); q.pop();
		ans += a + b;
		q.push(a + b);
	}
	cout << ans;
}

코드 2 (큐)

using ll = long long;
int arr[100001], q1 = 0, n;
queue<int> q2;

// 낱개 파일이 들어있는 queue1 과 합친파일이 들어있는 queue2 를 비교해 가장 작은것을 꺼낸다.
bool Get(ll& v)
{
	bool b1 = n - q1 > 0, b2 = !q2.empty();
	if (!b1 && !b2) return false;
	if (b1 && b2)
		if (arr[q1] < q2.front()) v = arr[q1++];
		else { v = q2.front(); q2.pop(); }
	else 
		if (b1) v = arr[q1++];
		else { v = q2.front(); q2.pop(); }
	return true;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);

	ll ans = 0;
	while (1)
	{
		ll v1, v2;
		Get(v1);
		if (!Get(v2)) { break; }
		ans += v1 + v2;
		q2.push(v1 + v2);
	}
	cout << ans;
}