1. 탐욕법이란?
그리디 알고리즘(탐욕법)은 현재 상황에서 가장 좋아 보이는 선택을 반복하며 최적의 해답을 찾는 알고리즘이다.
즉, 앞으로의 결과를 고려하지 않고 현재 단계에서 최선이라고 판단되는 선택을 하는 방식이다.
이러한 특성 때문에 그리디 알고리즘은 항상 최적의 해를 보장하지는 않지만, 특정한 조건을 만족하는 문제에서는 매우 효과적인 해결 방법이 될 수 있다.
2. 그리디 알고리즘의 핵심 개념
그리디 알고리즘을 사용할 수 있는 문제는 대개 다음과 같은 특징을 가진다.
-
탐욕적 선택 속성 (Greedy Choice Property)
- 앞선 선택이 이후의 선택에 영향을 주지 않아야 한다.
- 각 단계에서 최적의 선택을 하면 전체적으로도 최적의 해가 되어야 한다.
-
최적 부분 구조 (Optimal Substructure)
- 부분 문제의 최적해를 조합하면 전체 문제의 최적해가 되어야 한다.
이 두 가지 속성이 충족되면 그리디 알고리즘을 사용하여 문제를 해결할 수 있다.
3. 거스름돈 문제로 살펴보는 그리디 알고리즘
대표적인 그리디 알고리즘 예제인 거스름돈 문제를 살펴보자.
문제
당신은 거스름돈을 동전으로 줄 때, 동전의 개수를 최소한으로 사용해야 한다.
사용할 수 있는 동전의 종류가 500원, 100원, 50원, 10원이라고 할 때, 손님에게 거슬러 줘야 할 금액이1260원이라면, 동전의 최소 개수는 몇 개일까?
그리디 알고리즘 풀이
- 가장 큰 단위의 동전부터 가능한 한 많이 사용한다.
- 남은 금액을 그다음으로 큰 단위의 동전으로 거슬러준다.
- 이를 반복하여 최소 개수의 동전으로 거스름돈을 만든다.
# 거스름돈 문제 - 그리디 알고리즘
def min_coins(n):
coins = [500, 100, 50, 10] # 동전 단위
count = 0
for coin in coins:
count += n // coin # 해당 동전으로 거슬러 줄 개수
n %= coin # 남은 거스름돈
return count
print(min_coins(1260)) # 출력: 6정당성 검토
위의 방식이 항상 최적의 해를 보장하는 이유는 큰 단위의 동전이 작은 단위의 동전의 배수 형태로 주어졌기 때문이다.
따라서, 작은 단위의 동전을 조합하여 더 적은 개수로 거슬러 줄 수 있는 경우가 없으므로, 이 문제에서는 그리디 알고리즘을 적용할 수 있다.
그러나 동전의 단위가 서로 배수 관계가 아닐 경우, 그리디 알고리즘이 최적의 해를 보장하지 못할 수도 있다.
예를 들어, 동전의 단위가 [500원, 400원, 100원]이라면 800원을 거슬러 줄 때
그리디 알고리즘을 사용하면 500원 1개 + 100원 3개 (총 4개)를 선택할 수 있다.
그러나 실제 최적해는 400원 2개 (총 2개)이다.
따라서 문제를 풀 때 그리디 알고리즘이 최적해를 보장하는지 반드시 검토해야 한다.
4. 그리디 알고리즘의 활용과 문제 해결 전략
그리디 알고리즘 문제는 다양한 유형이 있으며, 항상 적용할 수 있는 것은 아니다.
문제를 해결하기 위해 다음과 같은 접근법을 사용할 수 있다.
1️⃣ 문제에서 "가장 큰 순서대로", "가장 작은 순서대로" 등의 기준이 주어지는지 확인하기
- 많은 경우, 그리디 알고리즘은 정렬 알고리즘과 함께 사용된다.
2️⃣ 탐욕적 선택이 전체 문제에서도 최적해를 보장하는지 검토하기
- 선택이 이후의 선택에 영향을 미치지 않고, 부분 최적해가 전체 최적해가 될 수 있는지 확인해야 한다.
3️⃣ 그리디 알고리즘으로 해결되지 않는다면 다른 알고리즘을 고려하기
- 만약 탐욕적 해결법이 존재하지 않는다면,
다이나믹 프로그래밍(DP), 그래프 탐색(BFS/DFS) 등의 알고리즘을 고려해야 한다.
5. 마무리
그리디 알고리즘은 빠르고 직관적인 해결법을 제공하지만, 모든 문제에 적용할 수 있는 것은 아니다.
따라서, 문제의 조건을 잘 분석하고, 탐욕적 선택이 최적의 해를 보장하는지 검토하는 과정이 중요하다.
코딩 테스트에서 문제 유형을 바로 파악하기 어렵다면 그리디 알고리즘을 먼저 의심해보고,
탐욕적 해결법이 존재하지 않는다면 다이나믹 프로그래밍이나 그래프 알고리즘을 고려해보는 것도 좋은 접근법이다.
