탐욕법 : 지금 상황에 당장 가장 좋은 선택지를 고른다!
그리디 알고리즘이란?
•
현재 시점에서 가장 좋은 선택지를 택하는 방법
•
단순히 가장 좋아보이는 것을 반복적으로 택해도 최적의 해를 구할 수 있는지, 정당성을 올바르게 분석해내는 것이 가장 중요합니다.
문제와 함께 더 살펴보겠습니다
탐욕스러운 선택을 한다? 지금 가장 좋은 선택지를 고른다? 이게 무슨 말일까요?
상황 1 : 루트 노드부터 시작해 거쳐가는 노드 값의 합을 최대로 하기
최적의 해 : 전체 경우에서 최대값이 되겠죠?
그리디 방식은 다음과 같습니다 :
- 5번 노드의 인접 노드 중 가장 큰 값인 10을 선택
- 10번 노드의 인접 노드 중 가장 큰 값인 4를 선택
느낌이 오시나요? 이처럼 매번 무식하게 가장 좋아보이는(가장 큰) 값을 택하는 방식입니다. 그러나 위와 같은 경우를 보면 알 수 있듯이, 그리디 방법은 모든 경우 중에서 가장 큰 값을 만들어내는 것을 보장하는 알고리즘이 아닙니다. 코테에서 만약 그리디 방법을 사용해야한다고 생각이 났을 경우, “내가 탐욕적인 방법으로 택한 것이 가장 최적의 해인걸까?”를 생각해보고 맞다고 추론할 수 있어야 합니다.
상황 2 : 거스름돈 문제
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
동전의 최소 개수를 구해야하는 문제입니다. 만약 700원을 거슬러줘야한다면, 500원을 가장 먼저 떠올려야겠죠? 큰 액수의 동전을 최대한 사용해야합니다. 이처럼, 생각해봤을 때 매 상황에서 사용할 수 있는 최대 액수의 동전을 사용하는 게 자명하다고 생각한다면 그리디 알고리즘을 작성하는게 맞습니다.
n = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += (n // coin) # 해당 동전으로 줄 수 있는 최대의 개수를 카운트에 누적
n %= coin # 해당 동전을 최대한 사용하고 더 줘야하는 나머지 값으로 n 갱신
print(count)
Python
복사
그리디 알고리즘 활용편
그리디 알고리즘은 마치 DP와 비슷한 느낌인데요, DFS/BFS처럼 어느 정도 정해진 로직이 있는 게 아니라 하나의 개념과 같다고 생각합니다. 이런 탐욕스러운 방법을 활용해 만들어진 알고리즘들이 있습니다. 몇가지 살펴볼게요.
다익스트라 알고리즘(최단 경로)
프림 & 크루스칼 알고리즘(최소 신장 트리)
참고 자료
