정글사관학교 26일차 TIL: 그리디 알고리즘

오늘은 그리디 알고리즘에 대해 공부한 내용을 빠르게 정리하고 마무리.

 

앞에서 배웠던 재귀 관련 알고리즘으로는 크게 두 가지가 있었다. 분할 정복(Divide and Conquer)과 동적계획법(Dynamic Programming)이 그것이다.

 

1. 분할정복은 큰 문제를 중복 없는 작은 문제들로 분할하는 방법이다. 재귀적으로 작은 문제부터 해결한다.

2. 반면, 동적계획법은 작은 문제들로 쪼개되 이 작은 문제들 중 중복되는 애들을 DP 테이블에 저장해두고 같은 값이 나왔을 때 계산 없이 바로 테이블에서 꺼낸다.

 

그러면 오늘 다룰 그리디 알고리즘은 어떤 친구일까? 이름처럼 말 그대로 Greedy하게 선택하는 알고리즘을 뜻한다. 즉, 현재 상태에서 가장 좋은 선택을 반복해서 해를 구성한다.

 

예제로 동전 교환 문제를 살펴보자. 동전은 1원, 10원, 50원, 100원 등으로 상당히 많다. 이때, 만약 input으로 372원이 들어왔다고 해보자. 우리의 목적은 최소 갯수의 동전으로 372원을 거스르는 것이다.

 

이를 최소화하려면? 직관적으로 생각했을 때는 가장 큰 동전 단위를 최대한 많이 주는 방법이 이에 해당된다. 372원의 경우, 100원 짜리를 3개, 50원 짜리 1개, 10원짜리 2개, 2원짜리 2개로 총 8개의 동전을 사용하면 된다.

 

여기서 질문: 이보다 적게 거슬러 줄 방법이 있나? 지금과 같은 종류의 동전을 갖고 있다면 현재 방법이 최선임이 이미 증명되어 있다. 여기서 핵심은 지금과 같은 종류라는 것이다. 이게 무슨 말이냐?

각 동전 간의 관계가 배수 관계일 때면 그리디 알고리즘을 적용할 수 있다는 말이다!

위에서 말했던 1, 10, 50원 동전에 대해 100원은 이들과 배수 관계에 해당한다. 만약 우리가 갖고 있는 동전이 1원, 5원, 그리고 7원이라면 어떨까? 이 상황에서 15원을 거슬러준다고 가정해보자.

 

가장 큰 돈이 7원이니 14원을 거슬러주면 1원이 남아서 1원을 준다. 이때 사용된 동전은 총 3개이다. 그런데 5원짜리 3개를 줘도 15원을 거슬러줄 수 있다. 이와 같이 큰 동전이 작은 동전의 배수가 아니면 greedy 알고리즘이 성립하지 않는다. 예제 하나를 더 살펴보자. 만약 10원이라고 해보자. 그리디를 적용하면 7원짜리 하나와 1원짜리 3개로 총 4개의 동전을 거슬러준다. 그런데 5원짜리 2개면 아까와 달리 더 적은 개수의 동전으로 거슬러주는 게 가능해진다. 처음 예제와 지금 예제의 차이점은 딱 하나다. 큰 동전이 작은 단위 동전의 배수로 표현되지 않는다는 것. 반면 그리디에서는 큰 동전이 작은 단위 동전의 배수 단위로 표현된다.

 

따라서 주어진 동전의 단위에 따라 greedy 알고리즘 방식이 해가 될 수도 있고 아닐 수도 있다.