그리디 알고리즘
그리디 알고리즘이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다.
그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다. 여기서 탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다. 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다. 또한 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다.
이렇게 탐욕 선택 속성과 최적 부분 구조의 2가지 조건을 만족하면 최적해를 찾을 수 있다. 하지만 그렇지 않더라도 그리디 알고리즘은 정답을 근사하게 찾는 용도로 활용할 수 있으며, 대부분의 경우 계산 속도가 빠르므로 매우 실용적이다.
그리디 알고리즘이 잘 동작하는 예는 무척 많다. 최단 경로 문제를 풀이하는 다익스트라 알고리즘은 대표적인 그리디 알고리즘의 예로서 최적해를 찾을 수 있다. 또한 압축 알고리즘인 허프만 코딩 알고리즘은 허프만 트리를 빌드할 때 그리디 알고리즘을 사용하며, 마찬가지로 최적해가 보장된다. 머신러닝 분야에서는 의사결정 트리 알고리즘으로 유명한 ID3 알고리즘이 그리디 알고리즘이다. 항상 그때 그때 최선의 답을 찾아 트리를 빌드해 나간다. 물론 이 경우는 최적에 가까운 답을 찾을 수 있지만, 반드시 최적해를 찾는 것은 아니다.
그리디 알고리즘은 최적 부분 구조 문제를 푼다는 점에서 흔히 다이나믹 프로그래밍과 비교되는데, 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다르다. 다이나믹 프로그래밍이 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 한다면, 이에 반해 그리디 알고리즘은 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태로, 서로 반대 방향으로 접근하는 구조를 띤다.
그렇다면 여기서는 그리디 알고리즘을 중심으로 풀 수 있는 문제, 다이나믹 프로그래밍으로 풀어야 하는 문제, 그리디 알고리즘으로는 풀 수 없는 문제들에 대해 차례대로 살펴보자.
배낭 문제
배낭 문제는 초합 최적화 분야의 매우 유명한 문제로, 쉽게 말해 밑의 그림과 같이 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고 각각 짐의 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록, 즉 달러의 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제다.
배낭 문제는 위의 그림과 같이 짐을 쪼갤 수 있는 경우인 분할 가능 배낭 문제와 짐을 쪼갤 수 없는 경우인 0-1 배낭 문제로 나뉜다.
짐을 쪼갤 수 있는 분할 가능 배낭 문제의 경우 단가가 가장 높은 짐부터 차례대로 채워나가면 되는데 이 그림에서는 C의 단가가 2.5달러로 가장 높으므로 C, B, E, D 순으로 총 8kg의 짐을 배낭에 담고 마지막 남은 7kg을 위해 A의 7/12 만큼을 쪼개서 배낭에 그리디 알고리즘으로 담는다. 이렇게 하면 17.3이라는 최적해를 찾을 수 있다. 이 부분을 코드로 구현해보면 다음과 같다.
def fractional_knapsack(cargo):
capacity = 15
pack = []
# 단가 계산 역순 정렬
for c in cargo:
pack.append((c[0] / c[1], c[0], c[1]))
pack.sort(reverse=True)
# 단가 순 그리디 계산
total_value: float = 0
for p in pack:
if capacity - p[2] >= 0:
capacity -= p[2]
total_value += p[1]
else:
fraction = capacity / p[2]
total_value += p[1] * fraction
break
return total_value
cargo = [
(4, 12),
(2, 1),
(10, 4),
(1, 1),
(2, 2),
]
print(fractional_knapsack(cargo))먼저, 짐 cargo를 '(가격, 무게)'의 튜플 리스트로 정의하고, 함수 fractional_knapsack()을 호출한다. 우선, 앞서 단가 기준으로 알고리즘을 설명한 그대로 구현하기 위해 단가를 계산하고 역순으로 정렬한다. 다음 단가 순으로 그리디 알고리즘으로 계산하면 된다. 이처럼 구현했을 때 total_value는 17.3이 된다. 앞서 알고리즘을 설명했을 때와 동일한 정답이다. 그러나 이문제에서 만약 짐을 쪼갤 수 없다면 지금까지 실행한 방식대로 단가 순으로 배치해선 안된다. (0-1 배낭 문제는 다이나믹 프로그래밍으로 풀이해야 함)
동전 바꾸기 문제
또 다른 유명한 문제로 동전 바꾸기 문제가 있다. 동전의 액면이 10원, 50원, 100원처럼 증가하면서 이전 액면의 배수 이상이 되면 그리디 알고리즘으로 풀 수 있다. 우리나라 동전은 항상 배수 이상이므로 그리디로 풀 수 있다.
그런데 만약 다른 나라에 갔더니 80원짜리 동전이 더 있다고 치자. 이 경우 더 이상 그리디하게 풀 수 없다. 160원을 거슬러줘야 한다면 80원짜리 2개가 정답인데 그리디 알고리즘으로는 100원부터 선택하게 될 것이고 이렇게 하면 80원 2개로 풀이 할 수 없기 때문이다. 이 경우 앞서 0-1 배낭 문제와 마찬가지로 다이나믹 프로그래밍으로 풀어야 한다.
가장 큰 합
세 번째로는, 그리디 알고리즘의 실패 사례를 살펴보자. 노드를 계속 더해가다가 마지막에 가장 큰 합이 되는 경로를 찾는 문제다. 예로 밑의 그림을 살펴보자.
7부터 시작해 최종적으로 가장 큰합을 만들기 위해서는 간선으로 연결된 2가지 선택지중 더 큰 수를 계속 더해나가면 될 것 같다. 전형적인 그리디 알고리즘의 형태로, 매번 가장 큰 값을 취해 나가면 7 → 12 → 6을 이어서 선택하게 된다. 그런데 이 경우 합은 25에 불과하다. 만약 7에서 3을 택하고 99를 택하면 무려 109가 될 수 있다. 그러나 그리디 알고리즘으로는 99를 발견할 수 없다. 7은 3과 12 중에서 절대로 3을 택하지 않을 것이기 때문이다. 이 문제는 이진 트리를 정렬한다든지 등의 추가 작업을 하지 않는 한, 그리디 알고리즘으로는 풀이 할 수 없다.
분할 정복
분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘으로는 병합 정렬을 들 수 있다.
병합 정렬은 상단에서 '분할'하고 중앙에서 '정복'하고 하단에서 '조합'하는 분할 정복의 단계를 잘 보여준다.
- 분할 : 문제를 동일한 유형의 여러 하위 문제로 나눈다.
- 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
다이나믹 프로그래밍
다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다. 다이나믹 프로그래밍 알고리즘을 이용하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제, 즉 최적 부분 구조를 갖고 있는 문제를 풀이할 수 있다. 최적 부분 구조를 푸는 또 다른 알고리즘으로는 그리디 알고리즘이 있다. 비슷한 유형의 문제를 풀이한다는 점에서 서로 비교 대상이 되기도 하는데, 그리디 알고리즘은 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이해 나가는 것이고, 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해 나간다는 차이가 있다. 여기서 중요한 점은 '중복된' 문제들이란 점이며, 중복되지 않는 문제들은 다이나믹 프로그래밍으로 풀지 않는다. 대표적으로 병합 정렬과 퀵 정렬 등이 있으며, 이들은 모두 분할 정복 알고리즘으로 분류한다.
대부분의 재귀 알고리즘은 밑의 표에서 살펴볼 수 있는 것처럼 최적 부분 구조 문제를 풀 수 있다. 이 중에서도 병합 정렬, 퀵 정렬과 같은 분할 정복 알고리즘은 '중복된 하위 문제들'을 푸는 것이 아니기 때문에 다이나믹 프로그래밍으로 분류되지 않는다. 배낭 문제 중 분할 가능 배낭 문제는 '탐욕 선택 속성'이 있기 때문에 그리디 알고리즘으로 풀이할 수 있다.
다익스트라 알고리즘은 다이나믹 프로그래밍과 그리디 알고리즘 둘다 해당하는 경우인데, BFS시 항상 최단 경로를 찾고 탐욕 선택 속성을 갖는 그리디 알고리즘이면서, 이미 계산한 경로는 저장해두었다가 활용하며 중복된 하위 문제들을 푸는 다이나믹 알고리즘이기도 하다. 즉 다익스트라 알고리즘은 '최적 부분 구조', '중복된 하위 문제들', '탐욕 선택 속성'을 모두 갖는 알고리즘이다.
최적 부분 구조
최적 부분 구조에 대해 좀 더 살펴보자. 서울에서 부산까지 가는 최단 경로를 찾는 간단한 예를 들어본다. 위의 그림에서 보듯이, 서울에서 대구까지 가는 경로는 3가지가 있으며, 부산까지도 마찬가지로 3가지 경로가 있다. 서울에서 부산까지 가는 최단 경로는 200km + 80km = 280km이다. 이 경로는 서울에서 대구까지 가는 최단 경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다. 즉 서울에서 부산까지 가는 최단 경로는 각각의 부분 문제인 1)서울에서 대구까지 가는 최단 경로 문제와 2)대구에서 부산까지 가는 최단 경로 문제의 해결 방법의 합이다. 따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다.
이러한 구조를 최적 부분 구조라 하며, 이런 유형의 문제는 분할 정복으로 풀 수 있다. 또한 다이나믹 프로그래밍 또는 그리디 알고리즘으로 접근해볼 수 있는 문제의 후보가 된다. 그러나 만약 서울에서 부산까지 바로 연결되는 고속도로가 새롭게 개통되어 더 이상 대구를 거칠 필요가 없다면, 이 문제는 더 이상 최적 부분 구조가 아니다. 더는 분할 정복으로 풀 수 없으며, 다이나믹 프로그래밍이나 그리디 알고리즘으로도 풀이할 수 없다.
중복된 하위 문제들
다이나믹 알고리즘으로 풀 수 있는 문제들과 다른 문제들의 결적적인 차이는 중복된 하위 문제들을 갖는다는 점이다. 피보나치 수열을 재귀로 풀면 반복적으로 동일한 하위 문제들이 발생한다. 바로 이 부분이 핵심으로, 중복 문제가 발생하지 않는 병합 정렬은 분할 정복으로 분류되지만, 피보나치 수열을 풀이하는 알고리즘은 다이나믹 프로그래밍의 대상으로 분류되는 이유다.
다이나믹 프로그래밍 방법론
지금까지 최적 부분 구조와 중복된 하위 문제들로 구성된 다이나믹 프로그래밍의 패러다임을 살펴봤고, 이제부터는 다이나믹 프로그래밍의 방법론을 알아볼 차례다. 정리하면 아래의 그림과 같다.
이 그림에서 방법론은 방식에 따라 크게 상향식과 하향식으로 나뉜다. 일반적으로 상향식을 타블레이션, 하향식을 메모이제이션이라고 구분해 부르기도 한다.
- 상향식 : 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다. 타뷸레이션이라 부르며, 일반적으로 이 방식만을 다이나믹 프로그래밍으로 지칭하기도 한다.
- 하향식 : 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나간다. 이 방식을 특별히 메모이제이션이라 지칭한다.
피보나치 수열의 예제 코드를 보면, 상향식과 햐향식의 구분이 금방 이해될 것이다.
상향식
def fib(n):
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]상향식 방법론은 작은 하위 문제부터 차례대로 정답을 풀어나가며 큰 문제의 정답을 만든다. 이 방식을 타블레이션이라 하며, 이 방식만을 다이나믹 프로그래밍이라 지칭하는 경우도 있다. 데이터를 테이블 형태로 만들면서 문제를 풀이한다고 하여 타블레이션 방식이라고 부른다.
하향식
def fib(n):
if n <= 1:
return n
if dp[n]:
return dp[n]
dp[n] = fib(n - 1) + fib(n - 2)
return dp[n]하향식 방법론은 하위 문제에 대한 정답을 계산 했는지 확인해가며 문제를 자연스럽게 재귀로 풀어나간다. 기존 재귀 풀이와 거의 동일하면서도 이미 풀어봤는지 확인하여 재활용하는 효율적인 방식으로, 메모이제이션 방식이라고 부른다.
사실 대부분의 다이나믹 프로그래밍 문제는 어렵기 때문에, 대면 인터뷰 시에는 다양한 문제를 출제하기가 쉽지 않고 결국 기본에 가장 충실한 문제를 낼 수밖에 없다. 피보나치 수열은 그중에서도 다이나믹 프로그래밍의 가장 기본 중의 기본이라 할 수 있는 문제다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]