그리디 알고리즘 (1) / 그리디 알고리즘이란

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다 

---

▷그리디 알고리즘이란? 

 

탐욕법으로 번역되는 해당 알고리즘은 현재 주어진 상황에서 가장 좋은 것만 고르는 방법이다. 문제를 보고 해당 문제를 풀 수 있는 아이디어를 떠올리는 것이 중요하다. 코테에서 많이 출제되는 유형이지만 아이디어를 생각하는 것이 중요하기 때문에 사전에 알고리즘을 외우지않아도 충분히 풀 수 있는 문제유형이다. 아이디어를 떠올린 후에는 가장 좋아보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다. 

 

 

 

▷ 그리디 알고리즘 풀이법

 

즉 그리디 알고리즘은,

 

1. 최소한의 아이디어를 생각해내고, 

2. 아이디어의 정당성을 분석해야한다. 다른 말로 내가 생각해낸 아이디어로 해를 구하고자 할때 최적의 해를 항상 보장할 수 있는지 검토해야한다.

 

 

 

▷ 거스름돈 예시

 

예를 들어보자.

 

손님에게 돈을 받으면 직원이 손님에게 최소의 동전의 사용하여 거스름돈을 거슬러 줘야한다고 생각해보자. 몇개의 동전이 최소 동전 개수가 될지 풀기위해 우리는 '가장 큰 단위부터 가능한만큼 거슬러주자'라는 아이디어를 생각해낼 수 있다. 만약 1500원 물건에 대해 손님이 1320원을 냈다면 우리는 가장 큰 단위인 500원 부터 500+500+100+100+100+10+10으로 거슬러줄 수 있다. 즉 최소동전개수는 7개이다. 

그렇다면 '가장 큰 단위부터 가능한만큼 거슬러주자'라는 아이디어가 항상 최소동전개수가 7개가 되도록 만들어줄 수 있는가? 이에 대한 대답은 '만들어줄 수 있다. 왜냐하면 작은 단위의 돈의 배수가 큰 단위의 수가되기 때문이다.' 만약 동전의 단위가 500,400,20원이라면 해당 아이디어로는 최적의 해를 구할 수 있는 정당성이 만족되지 않을 것이다. 

 

이처럼  그리디 알고리즘은 아이디어, 정당성을 항상 고려해두는 것이 중요하다. 만일 문제를 봤을 때 문제의 유형을 단번에 알지 못하겠다면 그리디 알고리즘으로 풀 수 있진 않은지 확인해보자! 

 

 

 

다음 포스팅에서 그리디알고리즘을 적용한 문제를 풀어보고자 한다.