[이코테 chapter3] 그리디

그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 다른 유형에 비해 알고리즘의 사용 방법을 정확히 알고 있어야 하지 않아도 됨.

 

예시) 그리디 알고리즘이란?

사진과 같은 노드가 있을 때, 루트 노드로부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고자 한다. 그럼 다음과 같이 5 + 7 + 9로 진행하여 21이 되는 것이 최적의 루트이다.

 

하지만 그리디 알고리즘을 활용해 매 상황(현재 위치)에서 가장 큰 값만 반환을 하게 된다면 5 -> 10 -> 4로 된다. 이는 최적의 해인 21보다는 낮은 값이다. 즉 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많아, 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 추론할 수 있어야 문제가 풀린다.

 

추가적으로 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 다음과 같은 예시로 '거스름돈' 예시로 그리디 알고리즘을 설명하겠다.

 

예시) 거스름돈 문제

위 사진과 같이 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구해야 하는 문제가 있다. 이를 그리디 알고리즘의 아이디어를 통해 문제를 해결하자면, '가장 큰 화폐 단위부터 돈을 거술러 주는 것이다. 500->100->50->10처럼 차례로 돈을 거슬러 주는 것이다.

 

예를 들어 N이 1,260원일 때를 가정해보자.

화면의 그림처럼 가장 큰 화폐 단위인 500원부터 2개를 거슬러주면 260원이 남고, 다시 100원을 거슬러주면 60원, 이와 같이 거슬러주면 2+2+1+1 =6. 즉 거슬러줘야 할 동전의 최소 개수는 6개이다.

 

이를 코드로 구현하면 다음과 같다.

코드를 보면 화폐의 종류만큼 반복을 수행하여, 화폐의 종류가 K개라고 할 때 위 소스 코드의 시간 복잡도는 O(K)이다. 시간 복잡도에서 거슬러 줘야 할 돈 N은 찾아 볼 수 없는 것을 알 수 있는데, 즉 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.

 

 

그리디 알고리즘의 정당성

 

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 '최적의 해'를 찾을 수 없을 가능성이 크다. 따라서 그리디 알고리즘으로 찾은 문제의 해법은, 해법이 정당한지 검토해야 한다. 위 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 '가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.'

 

예를 들어 800원을 거슬러 줘야 하는데, 500, 400, 100원일 때를 생각해보면 그리디 알고리즘으로는 500+100+100+100원을 거슬러 줘야 하므로 총 4개가 나온다. 하지만 최적의 해는 400+400, 총 2개를 거슬러 주는 것이다. 따라서 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

어떤 코딩 테스트 문제를 만났을 때, 문제 유형을 바로 파악하기 어렵다면 그리디 알고리즘을 먼저 의심해보고 해결방방법이 떠로으지 않는다면 다이나믹 프로그래밍이나 그래프 알고리즘으로 재차 고민해보는 것도 한 방법이다.

 

실제로 문제에서 동전의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없어 다이나믹 프로그래밍으로 해결할 수 있다.