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

1. 탐욕법 문자들을 합쳐 문자열을 만드는데 드는 비용이 최소가 되게 선택하려면 일단 가장 작은 문자 두개를 선택해 합쳐나가야 할 것 같다. 합쳐진 문자열에 또 합치게 되면 이전에 합치게한 문자열이 중복으로 또 다시 카운트 되기 때문이다. 2. 증명 탐욕적 선택 속성을 증명하기 위해 먼저 가장 작은 두 문자가 서로 합쳐지지 않은 최적해가 있다고 해보자 a와 b가 가장 작은 두 수 일때 먼저 다른 문자열과 합친것을 다음과 같이 표현했다. X = b + B Y = a + C 거리가 같은경우 : X + Y 일 경우 a 와 B를 바꾸어도 비용은 일정하므로 답은 변하지 않는다 거리가 다른 경우: X + a 일경우 a와 B를 바꾸게 될경우 B가 병합되는 횟수가 적어져 비용이 줄어들게 된다. 그러므로 작은 두 문자열..

2021.01.18