greedy algorithm
greedy는 탐욕이라는 뜻이다.
greedy algorithm은 지금 선택할 수 있는 가장 큰 이익을 선택하는 알고리즘이다.
해당 시점의 최대 이익을 추구하기 때문에 Local optimum을 찾지만 결과적으로 지역적인 최적이 합쳐져
Gloval optimum이 된다는 보장은 없다.
그래프에서 최단 거리 탐색을 할 때 당장은 가장 짧은 도로로 이동하는게 좋지만 그 결과를 합쳤을 때
최종적으로 최적인 답이 된다는 보장되지 않는 것과 같은 이야기다.
최적 부분 구조와 탐욕 선택 속성을 가지는 문제에 그리디 알고리즘을 적용할 때 좋다.
최적 부분 구조
최적 부분 구조란 하나의 문제를 부분 문제로 나눈 뒤 결합하여 풀 수 있는 구조이다.
이런 길 찾기 문제에서 1->2->3->4 로 이동해야 하는데 각각 가는 길이 여러 갈래가 있다면
매 노드에서 가장 작은 거리의 길로 이동하는 것이 최적해가 될 것이다.
이런 케이스를 탐욕 선택 속성을 가진다고 볼 수 있는데 앞의 선택이 이후 선택에 영향을 주지 않는다.
DP(동적 계획법)와 차이
하나의 문제를 부분 문제로 나눈다는 것에서 DP와 비슷하다는 느낌이 드는데
내가 생각하는 DP와 그리디의 차이는 DP는 부분 문제로 나눈 뒤 그 결과가 뒤에 전파되는 느낌이라면
탐욕 속성을 가지는 문제는 앞의 선택이 이후 선택에 영향을 주지 않는다라는 특징이다.
하지만 문제를 딱 보고 이것의 풀이가 그리디일지 DP인지 구별하는 것은 증명하기가 상당히 어렵다.
그래서 그리디의 여러 유명한 유형를 보면서 직관을 키우는게 좋은 것 같다.
동전 문제
가장 대표적인 그리디 문제인 동전 문제로 N원과 동전의 종류가 주어질 때 최소 동전 개수로 N원을
맞추는 문제가 있다.
이 문제가 그리디로 풀리기 위해서는 동전의 모든 값이 배수 관계여야 한다.
동전 문제
위의 문제가 좋은 예시인데 배수가 아니라면 가장 큰 값을 고르는 것이 최선이 아닐 수도 있기 때문이다.
만약 1400원이 주어졌는데 1000원과 100원만 있으면 1000 + 4*100원으로 5개가 최선이지만
700원짜리 동전이 등장하게 되면 700*2로 2개로 해결할 수 있기 때문이다.
이렇게 무턱대고 그리디 같은데? 하고 풀이를 하다가 local optimum에 빠지는 반례에 막힐 때가 많다.
그리디의 가장 큰 장점은 속도가 빠르다는 것인데 뒤의 계산을 고려하지 않고 항상 지금의 최선만
선택하기 때문에 바로바로 구한 값을 이용해서 계산을 할 수 있다.
이런 그리디를 이용한 것으로 대표적으로 다익스트라나 크루스칼 알고리즘이 있다.
문제를 풀 때 증명을 하고 풀 수 있다면 최선이지만 현실적으로 어렵기 때문에 다양한 난이도와 유형의
그리디와 DP문제를 접하면서 직관력을 키우는 방향으로 게속 공부하고 있다.