[이코테] 2. 그리디

January 15, 2021

현재 상황에서 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 ‘가장 큰 순서대로’ or ‘가장 작은 순서대로’ 와 같은 기준을 티 안나게 제시해준다.

이런 기준은 정렬 알고리즘을 사용해야 만족시킬 수 있으므로 그리디는 정렬 알고리즘과 짝을 이뤄 출제된다.

가장 대표적으로 쉬운 그리디 문제이며 아래와 같다.

동전 종류(500원, 100원, 50원, 10원)를 주고, 거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라

그리디 알고리즘은 최적의 해 를 찾을 수 없을 가능성이 다분하다. 즉, 항상 최적의 해를 갖는 것이 아니다.

하지만 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다.

따라서 그리디 알고리즘을 사용할 때는 그 해법이 정당한지 검토해야 한다.

예를 들어 500원 400원 100원을 갖고 있을 때 800원을 거슬러줘야 하는 경우 그리디를 사용하면 500 + 100*3, 4개의 동전을 사용하도록 해가 도출되는데, 실제 정답은 400*2, 2개이다.

따라서 동전의 형태가 서로 배수의 형태인지와 같은 정당성을 검토할 수 있어야 한다.

문제 유형을 파악하기 어렵다면 그리디 알고리즘이 아닌지 의심해보고, 그리디 알고리즘으로도 해결하기 어렵다면 DP나 그래프 알고리즘이 아닌지 고민을 해보자. 즉, 알고리즘 몇 개를 머리속에 넣어놓고 항상 다른 방법이 있는지 의심하면서 문제를 풀자

악곱 == 악성곱슬