[알고리즘 문제풀이] STRJOIN 문자열 합치기 / 허프만 코드

1. 문제

 

프로그래밍 언어 C 의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C 에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자열의 끝을 지정하는데, 이래서는 문자열의 길이를 쉽게 알 수 있는 방법이 없기 때문에 여러 가지 문제가 발생하게 됩니다.

void strcat(char* dest, const char* src) {
 // dest 의 마지막 위치를 찾는다
 while(*dest) ++dest;
 // src 를 한 글자씩 dest 에 옮겨 붙인다
 while(*src) *(dest++) = *(src++);
 // 문자열의 끝을 알리는 \0 을 추가한다
 *dest = 0;
}

이런 문제 중 하나로 문자열을 조작하는 함수들의 동작 시간이 불필요하게 커진다는 것이 있습니다. 앞에 주어진 함수 strcat() 은 문자열 dest 뒤에 src 를 붙이는 함수인데, 실행 과정에서 반복문을 두 문자열의 길이를 합한 만큼 수행해야 합니다. 이 함수를 사용해 두 개의 문자열을 합치는 비용은 두 문자열의 길이의 합이라고 합시다.

이 함수를 이용해 n 개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들고 싶습니다. 순서가 상관 없다는 말은 {al,go,spot} 을 spotalgo 로 합치든 alspotgo 로 합치든 상관 없다는 의미입니다. 그러나 문자열을 합치는 순서에 따라 전체 비용이 달라질 수 있습니다. 예를 들어 먼저 al 과 go 를 합치고 (2+2=4), 이것을 spot 과 합치면 (4+4=8) 총 12 의 비용이 들지만 al 과 spot 을 합치고 (2+4=6) 이것을 다시 go 에 합치면 (6+2=8) 총 14 의 비용이 필요합니다.

n 개의 문자열들의 길이가 주어질 때 필요한 최소 비용을 찾는 프로그램을 작성하세요.

 

 

 

 

 

2. 풀이

 

// 문자열의 길이가 주어질 때, 하나로 합치는 최소 비용을 구한다. 

int concat(const vector<int>& lengths) {
	priority_queue<int, vector<int>, greater<int> > pq;
	for (int i = 0; i < lengths.size(); ++i) {
		pq.push(lengths[i]);
	}	
	int ret = 0;
	while (pq.size() > 1) {
		int min1 = pq.top();
		pq.pop();
		int min2 = pq.top();
		pq.pop();

		pq.push(min1 + min2);
		ret += (min1 + min2);
	}
	return ret;
}

 

 

 

 

 

3. 허프만 코드 (Huffman Code)

 

- 탐욕적 알고리즘의 대표적인 예시로, 가변 길이 인코딩 테이블을 만드는 방법으로 여러 압축 알고리즘에 사용된다. 

- 허프만 코드를 통하여 원문 글자들의 출현 빈도가 주어질 때, 예상 길이를 최소화하는 비트 패턴을 얻을 수 있다.

즉 허프만 코드는 주어진 데이터 파일의 문자 개수 n에 대하여, 해당 데이터 파일을 이진 코드로 압축하기 위한 최적의 이진 트리를 구축한다. 

- 빈도 수에 따라, 빈번하게 출현하는 글자는 짧은 패턴으로, 드물게 출현하는 글자는 더 긴 패턴으로 배당한다.

- 우선 순위 큐를 통하여, 가장 작은 두 노드 둘을 꺼내어 합쳐가면서 트리를 구현한다. 

 

 

 

 

 

4. git-hub

 

- https://github.com/SohyeonKim-dev/AlgorithmicProblem/blob/main/GreedyMethod/strJoin.cpp

 

 

 

 

 

5. 출처

 

- https://algospot.com/judge/problem/read/STRJOIN

- https://withhamit.tistory.com/12