Greedy 기본 이론 정리

수학 증명이 첨가된 PS 이론은 가젤님 블로그에 잘 정리되어 있다. 아래 링크에서 정리한 기본 이론이다.

• 가젤님 Greedy 관련 글: https://gazelle-and-cs.tistory.com/59

기본 원칙

Greedy stays ahead

• 탐욕스러운 것이 항상 앞선다.
• 매번 탐욕 알고리즘이 선택하는 것이 가상의 최적 알고리즘이 선택하는 것보다 항상 좋다는 것을 보임으로써 증명하는 기법

Certificate argument

• 증거 논의
• 알고리즘이 답을 출력할 때, 그 답이 실제로 최적해라는 증거를 함께 제출하는 기법

Exchange argument

• 교환 논의
• 최적해를 조금씩 바꾸어 탐욕 알고리즘의 답과 동일하게 만들되, 매번 나빠지지 않는다는 것을 보임으로써 알고리즘의 답이 최적해라는 것을 증명하는 방법

그리디 & DP & 완전 탐색의 구별법

어딘가(피갤) 에서 설명해준 개념적 이해가 너무 좋아서 아래에 살짝 변형해서 인용해본다.

어떤 상태 S가 있고, 그 상태 S에 대해 풀고자 하는 문제가 f라고 해보자.

• S: input
• f(S): output

1. f(S)라는 값을 구하기 위해 확인해야하는 모든 중간 상태를 나열하고 그걸 다 확인해서 f(S)를 구하는게 brute-force
2. 구하는 과정에서 같은 중간 상태를 확인하는 경우가 많고 그 가짓수가 그렇게 크지 않다는걸 이용해서 중복으로 사용하는 중간 상태들은 저장(메모이제이션)해서 최적화하는게 DP
3. f(S)를 구하기 위해 알아야하는 상태들 중에 몇 가지만 봐도 되는데? 라는걸 증명하고 일부만 보는게 그리디

즉, 어떻게 보면 그리디는 끝판왕이다. 다익스트라와 같은 알고리즘이 DP + Greedy라고 하는데, 이젠 좀 이해할 수 있게 되었다.