그리디 알고리즘(탐욕법)
그리디 알고리즘이란?
| 욕심쟁이 플랜트와 착한 페이지는 치킨메이트이다. 늘 둘이 함께 다니며, 이 건실하고 재능있는 청년들은 1인 1닭 정도는 가뿐히 처리할 수 있다. 오늘도 어김없이 치킨을 먹으러 간 플랜트와 페이지. 둘은 언제나 그랬듯 플랜트가 가장 좋아하는 양념치킨과 페이지가 좋아하는 파닭을 시켰다. 하지만 가는날이 장날이라고, 하필 튀김기 1대가 망가져 오늘은 치킨이 한마리씩 나온다고 한다. 어쩔 수 없지, 두 청년은 시원한 맥주를 시켜놓고, 먼저 나온 파닭을 먹기 시작했다. 그런데 아뿔싸! 늘 두마리를 나눠먹다가 한마리를 먹으니 욕심쟁이 플랜트의 본성이 드러나고야 말았다. 두 다리를 허겁지겁 먹어 치우더니 급기야 날개, 가슴살, 심지어 야들야들한 허벅지살까지!! 혼자 낼름 먹어치워버린 것이다 !! 착한 페이지가 곧 네가 좋아하는 양념치킨이 또 나오니 천천히 먹으라고 말려도 플랜트에게는 들리지 않았다. 그에게는 그저 눈 앞의 치킨 한마리가 훨씬 중요할 뿐! |
위 이야기에서, 플랜트는 그가 가장 좋아하는 양념치킨이 곧 나옴에도 단순히 "눈 앞에 있는 치킨"인 파닭을 탐하고 있다.
그리디 알고리즘은 플랜트의 행동과 같다. 비록 뒤에 더 좋은 답이 있을지라도 지금 당장 눈앞에 있는 답을 고르는 것.
물론 이 선택이 나중에 미칠 영향은 전혀 고려하지 않는다.
요즘 유행하는 MBTI로 따지면, 극한의 P 성향을 가지는 알고리즘이라는 것이다.
그리디 알고리즘의 특징은 "공식이 없다"는 것. 공식이 없다는 것은 다시 말해 내가 가는 길이 곧 정답이라는 것이다.
그리디 알고리즘은 문제 유형이 매우 다양하기 때문에 단순 암기로 해결할 수 있는 문제는 거의 없다고 보면 된다.
마치 보스를 잡을 때, 단순히 공격을 맞으면 죽는다는 것을 안다고 해서 무조건 클리어 할 수 없는 것 처럼.
하지만 이 길이 빠른 길인지, 맞지만 돌아가는 길인지, 아니면 낭떠러지로 향하는 길인지는 내가 가기에 달려있다.
따라서 그리디 알고리즘을 사용할 때에는 문제에서 주어진 조건을 잘 파악하고, 가장 좋은 조건을 선택하기만 해도 문제가 해결이 되는지, 또는 "가장 큰 순서대로" 등의 기준을 제시해 주는지를 꼼꼼히 확인해야 한다.
하지만, 눈 앞에 있는 답을 고른다고 해서 무조건 최적의 해를 구할 수 있는 것은 아니다.
n = 1000
a = [1,2,100]
b = [10, 20, 30]
c = [50, 10, 10]n에 각 배열의 요소들을 순차적으로 더했을 때, 가장 큰 값을 가지는 배열을 찾고 싶다고 한다.
탐욕법을 이용한다면, 처음 값들을 비교하여 1, 10, 50중 가장 큰 50을 가지는 c 배열을 선택하게 될 것이다.
하지만 두번째, 세번째 값들까지 모두 더하게 되면 가장 큰 값을 갖는 배열은 a 배열이다.
이처럼 무지성으로 그리디 알고리즘을 사용하다가는 잘못된 결론에 도달할 수 있다.
다행히 대부분의 코딩 테스트에서는 그리디 알고리즘을 통해 얻은 해가 최적의 해가 되도록 출제된다고 한다.
단, 그리디 알고리즘을 이용해 구한 해가 최적의 해라는 것을 판단할 근거가 있어야 한다.
이를 그리디 알고리즘의 정당성이라고 한다.
정리
그리디 알고리즘
- 현재 상황에 맞는 가장 좋은 방법을 고르는 알고리즘
- 문제를 풀기 위한 최소한의 아이디어룰 떠올리는 능력 요구
사용 방법
- 주어진 조건 파악 및 가장 좋은 조건 선택만으로 문제 해결이 가능한지 확인
- 기준을 제시해 주는지 확인
그리디 알고리즘의 정당성
- 그리디 알고리즘을 이용해 구한 해가 최적의 해라는 것을 판단할 근거
예제
- 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때, 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야할 돈 N은 항상 10의 배수입니다.(즉, 거슬러주지 못할 경우 없음)
우리가 구해야 하는 것은 "동전의 최소 개수"이다.
주어진 500원, 100원, 50원, 10원짜리 동전을 이용해 거스름돈 N원을 만들때, 사용하는 동전의 개수를 최소화 하라는 것이다.
N이 3000원이라고 가정해 보자. 금액별로 3000원을 만들 수 있는 동전의 개수는 다음과 같다.
| 금액 | 개수 |
| 500 | 6 |
| 100 | 30 |
| 50 | 60 |
| 10 | 300 |
같은 3000원을 만드는데 500원짜리는 6개만 사용해도 되는 반면 10원짜리는 300개나 필요하다.
우리는 최대한 적은 동전을 사용하여 거스름돈을 거슬러줘야 하기 때문에 이 경우에는 500원짜리 6개만을 이용해 3000원을 거슬러 주는 방법을 택하면 될 것이다.
다시 말해, 가장 큰 금액의 동전부터 돈을 거슬러 주는 것.
문제에 주어진 "동전의 최소 개수" 를 잘 확인했다면 충분히 떠올릴 수 있는 아이디어였다.
그렇다면, N이 주어졌을 때 500원-> 100원 -> 50원 -> 10원 순으로 거슬러 주는 방법을 코드로 구현해 보자.
메커니즘은 다음과 같다
- 동전을 금액별로 배열에 담는다
- 주어진 N을 각 금액으로 나누었을 때 "몫 = 사용한 동전의 개수", "나머지 = 동전을 거슬러주고 남은 돈"이 된다
- 사용한 동전의 개수는 더하고, 나머지가 다시 N이 된다.
- N이 0이 될 때 까지 위 과정 반복.
코드
let N = 3420
let num = 0
let coin = [500, 100, 50, 10]
console.log("최초 금액 : " + N)
for(i of coin){
num += parseInt(N / i)
console.log(i + "원을 사용해 거슬러 준 동전의 개수 : " + parseInt(N / i))
N = N % i
console.log("지금까지 사용한 동전의 개수 : " + num)
console.log("잔액 : " + N)
}
console.log("최종 결과 : " + num)
실행 결과
정당성
가장 큰 단위의 동전이 항상 가장 작은 단위의 배수이기 때문에 가장 큰 단위의 동전을 제외한 다른 동전으로는 최적의 해를 수할 수 없다.
예를 들어, N이 900원이고 동전은 500원, 300원, 100원이 있다.
그리디 알고리즘을 이용
- 500원 1개 + 100원 4개 = 총 5개
작은 단위의 동전을 사용
- 300원 3개
- 100원 9개
즉, 그리디 알고리즘을 사용했을 때 도출한 결론이 최적해가 아닌 경우가 생긴다.
따라서 그리디 알고리즘을 사용했다면 내가 가장 좋은 조건을 선택하여 도출한 정답이 최적해가 맞는지 다시 한번 검토해볼 필요가 있다.
오늘은 첫 알고리즘인 그리디 알고리즘(탐욕법)에 대해 공부해 보았다. 아직 개념만 봐서는 어떤 문제 유형인지 조금 알기 어려워서, 문제를 풀며 유형을 익혀 나가야 할 것 같다.
중요한 것은 꺾이지 않는 마음....도 맞지만 그냥 딱 봤을 때 가장 좋아 보이는 조건을 고르는 것.
이걸 단박에 눈치챌 수 있는 능력을 기르는 것이 포인트인 것 같다.