[탐욕법] STRJOIN 문자열합치기

1. 탐욕법

 

 

문자들을 합쳐 문자열을 만드는데 드는 비용이 최소가 되게 선택하려면 

 

일단 가장 작은 문자 두개를 선택해 합쳐나가야 할 것 같다.

 

합쳐진 문자열에 또 합치게 되면

 

이전에 합치게한 문자열이 중복으로 또 다시 카운트 되기 때문이다.

 

 

2. 증명 

 

 

탐욕적 선택 속성을 증명하기 위해 먼저 가장 작은 두 문자가 서로 합쳐지지 않은 최적해가 있다고 해보자

 

a와 b가 가장 작은 두 수 일때 먼저 다른 문자열과 합친것을 다음과 같이 표현했다.

 

X = b + B

Y = a + C

 

거리가 같은경우 :  X + Y 일 경우 a 와 B를 바꾸어도 비용은 일정하므로 답은 변하지 않는다

 

거리가 다른 경우: X + a 일경우 a와 B를 바꾸게 될경우 B가 병합되는 횟수가 적어져 비용이 줄어들게 된다.

 

그러므로 작은 두 문자열을 합치게 되면 비용은 항상 같거나 항상 줄어들게 된다.

 

작은 두수를 선택하도록 최적해를 바꾸는것으로 인해  총 비용은 더 커지지 않기 때문에

 

가장 작은 두 수를 선택하는 최적해는 반드시 존재하게 된다.

 

 

부분 문제들 또한 합친것을 포함한 남은 문자열 중에서 가장 작은 두개를 선택하는것이 이득이므로

최적 부분 구조는 자명하게 성립된다.

 

 

 

 

 

 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
 
std::vector<int> str;
 
int joint()
{
    int sum = 0;
 
    while(str.size() != 1)
    {
        int a = -str.back();
        str.pop_back();
        int b = -str.back();
        str.pop_back();
 
        str.push_back(-(a + b));
        std::sort(str.begin(), str.end());
 
        sum = sum + a + b;
    }
    return sum;
}
 
int main()
{
    int testCase = 0;
    int N = 0;
    
    std::cin>>testCase;
    for (int i = 0; i < testCase; i++)
    {
        str.clear();
        std::cin>>N;
        for(int j = 0 ; j < N ; j++)
        {
            int tmp;
            std::cin>>tmp;
            str.push_back(-tmp);
        }
        std::sort(str.begin(), str.end());
        std::cout<<joint()<<"\n";
    }
}

3. 허프만 코드

 

이 문제는 탐욕적 알고리즘의 유명한 예인 허프만 코드 알고리즘을 각색한 것이다.

허프만 코드는 가변 길이 인코딩 테이블을 만드는 방법으로 여러 압축 알고리즘에서 사용된다.

가변 길이 인코딩이란 원문의 각 글자를 서로 길이가 다를 수 있는 비트 패턴으로 바꿈으로써

원문의 길이를 줄이는 방법이다.

 

자주출현하는 글자는 더 짧은 패턴으로, 가끔만 출현하는 글자는 더 긴 패턴으로 배당할 필요가 있다.

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

 

각 글자에 대해 출현확률과 코드의 길이를 곱한 것의 합을 최소화 하는 것이다.

 

출현 확률이 문자열 길이로 바뀌었을 뿐 사실 위 문제와 똑같다.