그리디 알고리즘
현재 상태에서 가장 좋은 선택을 반복해서 해를 구성하는 알고리즘
문제는 이 그리디 알고리즘을 통해 얻은 해가 진짜 최선의 선택으로 얻은 해이냐는 것인데,
이를 증명하기 위해서는 귀류법을 통해 증명해봐야 한다.
즉 우리가 찾은 해가 해가 아님을 가정으로 하여 다른 해를 가정하여,
그 해를 논리적으로 추론하여 모순을 찾아내면, 우리가 찾은 그리디는 증명된 것이다.
예를 통해 이해해보자.
L = [1, 2, 3, 4, 5]라는 배열에서 원소의 합이 9 (= T)를 넘지 않도록 원소를 추출할 때, 가장 원소가 많은 경우는 몇 개인지 구할 때,
우리는 당연히 가장 작은 원소부터 하나씩 더해가면서 합이 9가 넘어가기 전 원소들만 추출 할 것이다.(1,2,3. 즉 세개)
(가장 작은 값부터 뽑는 방식으로 T까지 뽑으면(p) -> 3개가 가장 최대 갯수이다.(q))
이 논리를 검증하려면 ~q -> ~p임을 증명하면 된다.
즉 3개가 보다 더 많이 뽑을 수 있다고 가정했을 때 p가 모순을 일으키면 우리의 원래 p->q가 증명된 것이다.
우리는 3이라는 답을 우리의 논리(p)로 찾아냈다.
이를 증명하기 위해 3보다 많은 갯수가 해가 존재한다(~q)고 가정해보자.
그렇다면 우리의 논리(가장 작은 값부터 뽑기, p) 찾은 값들 a1, a2, a3가 있을 것이고
역의 해 b1, b2, b3, b4 …가 있을 것이다.
(이때, a와 b 모두 오름차순이라 하자)
자 이제 a1+a2+a3 = X라 하고, b1+b2+b3 = Y라 하면,
p에 의해 무조건 X <= Y 이다. (p = 가장 작은 값부터 뽑는다.)
그리고 문제 조건에 따라 Y + b4 <= T이다.
그런데 p에 따르면
X + a4 >T 이고 a4 <= b4 이다.
즉 종합해보면
X <=Y , a4 <= b4 인데
X + a4 > T 인데 Y + b4 <= T 인 모순적인 상황이 발생한다!
즉 우리의 그리디가 옳았다!