IT 엘도라도 로고
IT 엘도라도
황금

그리디 알고리즘 (Greedy Algorithm) 정당성 증명 방법

2020-03-29 15:56

그리디 알고리즘 (Greedy Algorithm) 정당성 증명 방법

1. 그리디 알고리즘 정당성 증명

"매 순간 내리는 선택을 포함하는 최적해가 반드시 존재한다"를 증명하면 된다. 늘 그렇듯 기초가 가장 중요하므로, 쉬운 문제들을 예시로 삼아서 그리디 알고리즘의 정당성을 어떻게 증명하는지 한 번 살펴보도록 하자.
 

2. 백준 1931번 문제 <회의실 배정>

종료 시간이 가장 빠른 회의를 이라고 하자. 이때 이 최적해에 포함되지 않는다고 가정하자. 그러면 최적해의 회의들 중 종료 시간이 가장 빠른 회의를 으로 대체하여 또 다른 최적해를 얻을 수 있다. 따라서 을 포함하는 최적해는 반드시 존재한다. 그러면 이제는 을 선택했다는 가정하에 을 제외한 나머지 회의들에 대해 동일하게 생각해보자.
전역 최적해를 얻기 위해서는 여기서도 최적해를 얻어야 한다. 그렇지 않으면 여기서 얻는 최적해를 이용하여 더 좋은 전역 최적해를 얻을 수 있어서 모순이 발생하기 때문이다. 따라서 이제는 을 제외한 나머지 회의들에 대해서 "종료 시간이 가장 빠른 회의를 포함하는 최적해가 존재한다."를 증명하면 되고, 이는 위에서 했던 증명과 동일하다. 결국 이런 식으로 반복하게 되면, 매 순간 남은 회의들 중에 종료 시간이 가장 빠른 회의를 선택함으로써 전역 최적해를 얻을 수 있다는 것이 증명된다.
 

3. 백준 11047번 문제 <동전 0>, 5585번 문제 <거스름돈>

맞춰야 하는 금액이 원이고, 원 이하의 크기를 가진 동전들을 크기 순서대로 내림차순 정렬했을 때 , , , . . . , 이라고 가정하자. 그리고 최적해가 () + () + . . . + ()이라고 가정하자. 이는 동전 개, 동전 개, . . . , 동전 개를 사용한다는 것을 의미한다. 이때 는 0 혹은 양의 정수이다(1 ≤ - 1). 즉, 최적해가 을 포함하지 않는다고 가정하는 것이다.
notion image
그러면 의 약수이기 때문에 로 표현이 가능하다. 이때 는 2보다 크거나 같은 양의 정수이다. 이해를 돕기 위해 이를 그림으로 표현하면 위와 같다. 개념적으로, 1개의 블록이 개의 블록으로 구성된다고 생각할 수 있다.
이때 만약 라면, 개의 블록들 중 개의 블록들은 1개의 블록으로 대체할 수 있다. 그런데 이렇게 되면 최적해보다 적은 개수의 동전을 사용하는 해를 얻을 수 있기 때문에 가정에 모순이 발생한다.
그러나 만약 라면, 개의 블록들을 활용하여 1개의 블록을 구성하는 블록들의 자리를 채우면 총 ()개의 블록들이 남게 된다. 그러면 이제 남은 ()개의 블록들에 대해 다시 생각해보자. 로 표현한다면(마찬가지로 는 2보다 크거나 같은 양의 정수), 남은 ()개의 블록들은 개의 블록들로 바꿔 생각할 수 있다. 그러면 이러한 개의 블록들은 마찬가지 원리로 개의 블록들로 다 채워질 수도 있고, 몇 개가 남을 수도 있다. 남게 되면 이 과정을 똑같이 반복하면 된다.
이 과정을 반복하면서 블록을 잘게 계속 쪼개다 보면, 언젠가 블록이 전부 채워지는 순간이 온다. 블록을 가득 채운 작은 단위의 블록들의 총개수를 라고 한다면, 개의 블록들을 1개의 블록으로 대체할 수 있는 것이다. 그런데 이렇게 되면 앞서 설명했듯이 최적해보다 적은 개수의 동전을 사용하는 해를 얻을 수 있다는 것이므로, 가정에 모순이 발생한다. 이로써 를 포함하는 최적해가 반드시 존재함이 증명된다.
그리고 이번에도 마찬가지로 전역 최적해를 얻기 위해서는 동전 하나를 제외한 나머지 동전들에 대해서도 최적해를 얻어야 한다는 점을 이용한다. 그렇지 않으면 여기서 얻는 최적해를 이용하여 더 좋은 전역 최적해를 만들 수 있기 때문이다. 따라서 같은 과정을 반복하면, 매 순간 남은 금액보다 작거나 같은 크기의 동전들 중 가장 크기가 큰 동전을 선택함으로써 전역 최적해를 얻을 수 있음이 증명된다.
말풍선
댓글 0
좋아요 2
    아직 작성된 댓글이 없어요.
사용자