알고리즘(코딩테스트)

허프만 코딩 & 유클리드 호제법

gbleem 2025. 1. 7. 17:56

코딩테스트 문제를 풀다가 해당 알고리즘들이 떠올라서, 정리해보기로 하였다.

1. 허프만 코딩

  • 허프만 코딩이란
    • 데이터 압축 알고리즘 중 하나인데, 문자의 등장 빈도를 기준으로 인코딩 하는 기술이다.
    • 간단히 과정을 설명하자면, 
      • 우선순위 큐를 이용하여 문자를 빈도에 따라 정렬하고
      • 최소 빈도의 두 노드를 합쳐 새로운 노드를 구성하는 방식을 반복하게 된다.
      • 가장 이해하기 쉬운 그림을 가져오면, 아래와 유사하다
        • 아래 그림에서 각 숫자는 빈도수를 뜻한다.
        • 빈도수대로 정렬한 후, 최소 빈도의 수를 더하는 과정을 반복하는 모습을 볼 수 있다.

출처: https://wkdtjsgur100.github.io/huffman/

  • 간단한 예시 문제를 풀어보자 (백준 1715 https://www.acmicpc.net/problem/1715)
    • 이 문제의 알고리즘 분류가 우선순위큐와 그리디 알고리즘이다. 즉 허프만 코딩이 우선순위큐와 그리디를 사용하는 방식이라는 것을 알 수 있다.
    • 우리가 몇 가지 예시를 들면서 생각해보면 떠오르는 방식인, 가장 작은 두 개의 값을 더해서 하나로 만드는 것을 반복하면 해결할수 있다. (이 방식이 허프만 코딩 방식과 같다)
    • 아래 코드를 보면
      • 우선순위 큐는 queue를 include 해서 사용할 수 있고, 아래처럼 greater<int> 라는 비교 연산자를 통해 오름차순으로 만들어 줄 수 있다.
      • while문 안에서의 동작이 허프만 코딩의 동작이라고 생각하면 된다.
        • 가장 작은 값 두개를 빼고, 그 두값의 합을 다시 넣어주는 것을 반복하는 동작
        • while문은 결국 우선순위큐 안에 값이 하나일 때까지 반복해준다.
#include <iostream>
#include <queue>
using namespace std;

int N;
int answer = 0;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		int num;
		cin >> num;
		pq.push(num);
	}

	while (pq.size() > 1)
	{
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();

		int sum = a + b;
		pq.push(sum);
		answer += sum;
	}
	cout << answer;
}

2. 유클리드 호제법

  • 유클리드 호제법은 최대 공약수를 찾는데, 효율적인 방법이다.
  • 먼저, 우리가 수학적으로 간단하게 생각할 수 있는 최대 공약수를 찾는 코드를 생각해보면 아래와 같이 구현할 수 있을 것이다.
  • 코드
    • 일단 두 수의 공통된 약수들 중에서 가장 큰 약수를 찾아야 하기에 약수를 먼저 구해야 한다.
    • 약수를 찾는 방식은 1부터 증가하면서 나눠떨어지는 값을 저장하면 된다. (Divisor 함수)
    • 그런데, 이 코드를 더 효율적으로 만들 수 있다. (BetterDivisor 함수)
      • 예를 들어 우리가 18의 약수를 찾는다고 할 때, 1, 2, 3을 찾으면 (√18 까지 찾은 약수들)
      • 나머지 약수들은 18을 앞서 구한 약수들로 나눠서 구할 수 있다.
      • 단, 16과 같이 제곱수일 때만 예외처리를 해주면 된다.
    • 마지막으로 최대 공약수를 찾기 위해서는 약수들의 공통된 값들 중 가장 큰 값을 저장하면 된다. (gcd 함수)
vector<int> Divisor(int n)
{
	vector<int> res;

	for (int i = 1; i <= n; ++i)
	{
		if (n % i == 0)
			res.push_back(i);
	}
	return res;
}

vector<int> BetterDivisor(int n)
{
	vector<int> res;

	for (int i = 1; i * i <= n; ++i)
	{
		if (n % i == 0)
			res.push_back(i);
	}

	for (int i = (int)res.size() - 1; i >= 0; --i)
	{
		if (res[i] * res[i] == n) // 제곱수 처리
			continue;
		res.push_back(n / res[i]);
	}
	return res;
}

int gcd(int a, int b)
{
	int gcdNum = 0;

	vector<int> va = BetterDivisor(a);
	vector<int> vb = BetterDivisor(b);

	for (auto a : va)
	{
		if (find(vb.begin(), vb.end(), a) != vb.end())
		{
			gcdNum = max(gcdNum, a);
		}
	}

	return gcdNum;
}
  • 유클리드 호제법
    • 위의 코드보다 더욱 효율적으로 최대공약수를 구할 수 있다. (약수들을 구할 필요도 없다!)
    • 유클리드 호제법의 방식은 다음과 같다
      • A와 B의 최대공약수를 구한다고 할 때
      • A를 B로 나눈 나머지가 R이라면, GCD(A, B) = GCD(B, R) 인 것을 사용하는 방식이다.
      • 예를 들어보면, GCD(20, 12) = GCD(12, 8) = GCD(8,4) = GCD(4, 0) 이런 식으로 반복되고, 최대공약수가 4임을 알 수 있다.
      • 시간 복잡도는 O(lg(max(a,b)) 이므로 매우 빠르다.
    • 코드도 간단하다. 
int GCD(int A, int B)
{
	if (A == 0)
		return B;
	return GCD(B % A, A);
}
  • 추가) 최소 공배수 구하기
    • 최소 공배수는 최대 공약수만 구하면 쉽게 구할 수 있다.
    • 어렸을 적 수학 시간에 배운 공식이면 해결이 가능하다.
    • A * B = gcd(A, B) * lcm(A, B); 이므로
      • lcm(A, B) = A*B / gcd(A, B); 로 구할 수 있다.
      • 그러나 이때 int overflow를 막기 위해서 나눗셈을 먼저 해주는 것이 좋다
int LCM(int A, int B)
{
	return A / GCD(A, B) * B;
}