[24.06.05] 99클럽 코테 스터디 17일차 TIL - 그리디 알고리즘 해결법, 증명

어제에 이어 오늘도 그리디 알고리즘 문제를 풀었다.

어제는 그리디 알고리즘을 어떻게 풀어야 할지 잘 모르겠어서 갈피를 못잡았지만, 오늘 아래 영상을 보고 그리디 알고리즘의 풀이 방법에 대해 조금 이해한 것 같다.

 

알고리즘 - 그리디 알고리즘 - 강의실 배정 문제 (Chan-Su Shin)

https://www.youtube.com/watch?v=7noZLdfHIMQ

알고리즘 - 그리디 알고리즘 - 강의실 배정 문제 (Chan-Su Shin)

 

 

내가 영상을 보고 느낀 점은 아래와 같다.

 

1. 그리디 알고리즘의 풀이를 위해선 문제를 해결하기 위한 아이디어가 중요하다.

아래 문제에서는 단위가 큰 동전부터 줄 수 있는 동전의 개수를 추가하면 된다는 아이디어가 핵심 아이디어이다.

ex) 거스름돈 문제.
거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동잔이 무한히 존재한다 가정한다.
손님에게 거슬러주어야 할 돈이 N원일 때 최소한으로 줄 수 있는 동전의 개수는??

 

그리고 오늘 푼 문제를 아래와 같다.(출처. 프로그래머스 단속카메라)

문제에서의 핵심은 최대한 많이 겹치는 구간에 카메라를 놓으면 된다는 것이 핵심 아이디어였다.

고속도로를 이용하는 모든 차량이 단속용 카메라를 한번은 만나도록 설치하고자 한다.
고속도로를 이용하는 차량의 경로 routes가 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야하는가?

 

이처럼 그리디 알고리즘 문제가 나오면 당황하지 말고 문제를 해결할 수 있는 핵심적인 아이디어가 무엇인지 고민해보는 것이 우선되어야 한다는 것을 알게되었다. 

 

2. 그리디 알고리즘의 증명에 귀류법을 사용할 수 있다.

그리디 알고리즘으로 생각해낸 "greedy solution은 optimal solution 중 하나"라고 볼 수 있다.

이를 증명하기 위해서는  "optimal solution이 아닌경우 그리디 솔루션에 모순이 생긴다"는 것을 입증함으로써 증명할 수 있다. 

 

이전의 동전 문제를 귀류법으로 증명해보자.

• 가정 P : 큰 동전부터 차례로 선택하는 것이 최적해이다.
• 반대 가정 (~P) : 다른 방법으로 더 적은 개수의 동전을 사용할 수 있다.

예를 들어 거슬러 주어야 할 돈 N이 760원일 때 가정 P에 따르면 총 5개의 동전이 필요하다.
(500원 1개, 100원 2개, 50원 1개, 10원 1개)

 

이제 반대 가정에 따르면 4개 이하의 동전으로 760원을 만들 수 있어야 한다.

하지만 여기서 모순이 발생한다. 760원이라는 금액을 맞추기 위해서는 500원, 100원, 50원, 10원 모두 필요하기 때문이다.

• 500원은 100원으로 대체할 수 있기 때문에 500원을 사용하지 않으면 100원이 7개가 필요하게 된다.
• 50원을 10원으로 대체하는 경우 10원이 6개 이상 필요하게 된다.
• 즉 모든 경우에서 4개 이하의 동전으로 760원을 맞추는 것은 불가능하다. 

결론적으로 "다른 방법으로 더 적은 개수의 동전을 사용할 수 있다."라는 가정에 모순이 발생함으로 "큰 동전부터 차례로 선택하는 것이 최적해이다."가 참임을 증명할 수 있다. 즉, 그리디 알고리즘은 이 문제에서 최적의 해를 제공한다는 것을 알 수 있다.