그리디 알고리즘이란?
-
탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
-
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
-
속도가 빠르다
그리디 알고리즘 정당성
- 그리디 알고리즘으로 최적해를 도출하기 위해서는 아래 두가지 조건을 만족해야 함
-
greedy choice property : 탐욕적인 선택이 항상 안전하다는 것이 보장된다는 의미이다. 즉, 그리디한 선택이 언제나 최적해를 보장해야한다.
-
optimal substructure : 부분 최적해(Local optimum)들이 모여 전체 최적해(Global optimum)를 구할 수 있는 경우이다. 즉, 전체 문제가 여러 부분 문제로 분할되며, 이 단계 하나하나에 대한 최적해가 도출되어야 한다는 의미이다.
예를 들면, 아래와 같은 경로 찾기가 있을 수 있다.
위 그림 처럼 도시간 이동을 위와 같이 밖에 할 수 없다고 했을 때, 서울에서 대전의 최단경로(Local optimum)와 대전에서 부산의 최단 경로(Local optimum)가 모여 서울에서 부산까지 가는 최단 경로(Global optimum)가 될 것 이다.
-
코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제
-
기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시
-
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
-
하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
거스름돈 문제
가장 큰 화폐 단위부터 돈을 거슬러 주는 것
10,100,500
=> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 가능함.
그러나 400원과 같은 단위가 생긴다면? 800원을 거스름돈 주는 경우, 그리디의 경우 500, 100x3 = 4개가 되지만,
최적의 해는 400x2 이므로 그리디를 적용할 수 없음. => 다이나믹 알고리즘 활용해야 함
=> 문제풀이를 위한 최소한의 아이디어가 정당한 지 검토할 수 있어야 함
