본문 바로가기

알고리즘/이론

04. 탐욕법 - 예제2

[1. 문제 설명]

n 개의 문자열들의 길이가 주어질 때, 

n 개의 문자열들을 순서와 상관없이 합쳐서 한개의 문자열로 만들 때

필요한 비용의 최소 값

 

ex)

{al, go, spot} 을 합칠 때

{al+go}+spot => al+go 비용: 4, algo+spot 비용 8 => 총 비용 12

 

 

[2. 풀이 접근]

한 문자열이 전체 비용에 미치는 영향에 대해서 생각해보면

병합되는 문자열들의 총 길이가 전체 비용에 더해진다. 

 

병합의 대상이 되는 문자열의 길이가 매번 전체 비용에 누적된다고 볼 수 있다.

위 예제에서 "al" 은 "al" + "go" 에서 전체 비용에 더해지고

"algo" + "spot" 에서 전체 비용에 더해진다 볼 수 있다.

 

그래서, 항상 길이가 짧은 두 문자열이 병합의 대상이 되게 하는 것이 타당해보인다.

 

=== 정당성 증명

가장 짧은 두개의 문자열을 합치는 최적해가 반드시 있음을 보이도록 한다.

  1. 문제의 최적해가 가장 짧은 두개의 문자열 a, b 를 서로 처음에 합치지 않는 형태라 가정한다.
  2. 이 최적해를 변형해서, 항상 a 와 b 를 처음에 합치는 최적해도 존재함을 보이도록 한다.
  3. [1] 에서 최적해로 정의한 형태에서 a 와 b 가 최초로 합쳐진 시점에서 문자열을 X 라 하자
  4. 이때, X 이후의 문자열에는 영향을 주지 않는다.
    => X 의 길이는 문자열들의 위치가 바뀌어도 일정하기 때문이다.
    => X 까지 문자열을 합치는데 필요한 비용만 고려하도록 한다.
  5. a 와 b 가 X 에서 몇단계나 떨어져 있나를 비교하도록 한다.
    A. 거리가 같은 경우
    => x 와 b 를 바꿔도 답은 변하지 않는다.

    B. 거리가 다를 경우
    => a, b 중에 X 에 더 가까운 쪽이 더 먼쪽과 합쳐지도록 옮긴다.
    => x 가 병합되는 횟수는 더 줄어들고, b 가 병합되는 횟수는 그만큼 늘어난다.
    => 그러나 x 의 길이는 b 보다 항상 더 크거나 같기 때문에, 바꾼 해는 결과적으로 항상 이득이거나, 같게 된다.

=== 최적 부분구조

두 문자열을 합치고 나면, 남은 문자열들 역시 항상 최소 비용으로 합쳐야 전체가 최소가 된다.

 

 

[3. 코드]

 

'알고리즘 > 이론' 카테고리의 다른 글

05. 조합 탐색  (0) 2022.10.09
04. 탐욕법 - 예제3  (0) 2022.10.03
04. 탐욕법 - 예제1  (0) 2022.10.03
04. 탐욕법  (0) 2022.10.03
03. 동적계획법 - 예제4  (0) 2022.10.02