나동빈님의 <이 것이 취업을 위한 코딩테스트다 with파이썬> 자료를 많이 참고하여, 정리했습니다.
그리디(greedy) 알고리즘
그리디 알고리즘이란 단어 뜻대로, 탐욕스러운 알고리즘이라고 한다. 즉, 단순 무식하게 탐욕적으로 문제를 풀어가는 것이라고 하는데.. 전혀 '단순 무식'하지 않다;;
무튼, 현재 상황에서 지금 당장 좋은 것을 고르는 방법이라고 한다. 다른 알고리즘 풀이 방법(정렬, 탐색 등)에 비해 외워야 할 것은 거의 없다고 봐야한다. 그러나 그리디 알고리즘으로 문제풀이가 가능하다는 것을 찾는 것이 힘들 수 있다.
그리디 알고리즘 문제에서 가장 중요한 점
그리디 알고리즘으로 풀어도 되는지에 대한 정당성 확인이 중요하다. 단순히 어떤 상황에서 최대값 혹은 최소값을 구해나간다고 해서 최종 답이 구해지는 지에 대한 정당성을 확인해야 한다.
그리디 알고리즘을 적용할 수 없는 문제
일반적으로 아래 같은 문제가 많은데. 이런 문제들에는 그리디 알고리즘을 이용해서 답을 얻을 수 없다. 따라서 정당성을 꼭 확인해봐야 한다.
대표적인 그리디 알고리즘 문제
아래 같은 문제는 그리디 알고리즘으로 풀 수 있다. 각 상황에서 가장 큰 거스름 돈의 단위를 먼저 거슬러주면 되기 때문이다.
정당성 확인
1. 거스름 돈의 단위가 항상 작은 단위의 배수이다.
2. 즉, 작은 단위의 거스름 돈을 합쳐서 다른 해를 구할 수 없다.
코드를 입력하세요반면, 거스름 돈의 단위가 [500원, 400원, 100원]이라고 하면 그리디 알고리즘으로 풀어낼 수 없을 것이다. (ex : 800원을 거슬러 줘야 할 때)
고재개발