[Algorithm]동적 프로그래밍(Dynamic Programming)
아직도 기억이 선명하다. 2000번대 자료구조, 알고리즘 수업을 들었을 당시 호기롭게 Leetcode를 결제하여 DP문제를 푸는데 아무것도 이해가 가지 않았다. 너무 답답한 마음에 집에 가는길에 노래 대신 DP 알고리즘이 어떤 내용인지 들으면서 갔던 기억이 난다. 그렇다면, 이 DP알고리즘은 왜 사용할까?
🔊반복되는 연산을 줄이자
알겠지만, 컴퓨터의 메모리와 연산 속도에는 한계가 있다. DP는 메모리 공간을 조금 더 사용해 실행 시간을 비약적으로 감소 시킬 수 있는 알고리즘이다. 이해가 잘 가지 않을테니 DP를 활용해 어떤 문제를 풀 수 있을지 보자.
DP의 가장 대표적인 예는 피보나치 수열이다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있다.
수학자들은 점화식을 이용해 이 피보나치 수열의 관계식을 표현한다. 피보나치 수열의 점화식은 너무 유명한 존재이니 따로 설명하진 않겠다. 피보나치 수열은 다음 두가지의 특징을 가진다
- n번째 피보나치 수 = (n-1) + (n-2)번째 피보나치 수
- 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
그렇다면, 이 점화식을 이용해 피보나치 수열을 어떻게 풀 수 있을까? 예를들어 f(4)를 계산 한다고 해 보자.
이렇게 보면 아직까진 그렇게 연산 횟수가 많아 보이진 않는다. f(4)의 연산 횟수는 5회이다. 하지만 f(6)일때를 생각 해보자.
f(4)보다 단지 2번째 뒤의 계산(f(6))을 하려고 했지만 15회의 연산을 한다. 결국, N이 늘어날수록, 이 방법은 연산 횟수가 기하급수적으로 늘어난다.
그림을 보면 동일한 연산들이 여러번 수행 되는것을 볼 수 있다. 그림에서 f(3)은 3번 호출되었다. 여기서의 '호출'이란 단순히 O(1)의 호출을 의미 하는것이 아니라, 피호출자의 연산 속도가 O(N)이라면, 호출을 할때마다 O(N)의 시간이 소요 되는것이다.
이때, 동적 프로그래밍을 이용하면 이 문제를 해결 할 수 있다. 다만, 항상 DP를 사용할 순 없으며, 다음 조건을 만족할때 사용 할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 푸는 큰 문제에서도 동일하다.
피보나치 수열은 위 조건들을 만족하는 가장 대표적인 문제이다. 이제 피보나치 수열 문제를 메모제이션(Memozation)을 활용해 풀어보자. 여기서 메모제이션이란, DP를 구현하는 방법중 하나로, 한번 구현한 결과를 별도의 메모리에 저장하여 같은 식을 호출하면 메모리에 메모된 결과를 그대로 가져오는 기법이다. 메모제이션이 이해가 안간다면, 캐싱(Caching)을 생각해보면 된다. 다음 소스코드를 살펴보자. 다음과 같이 피보나치 수열을 DP를 이용해 풀면 O(N)의 수행시간이 소요된다.
#한번 계산된 결과를 저장하기 위한 테이블 선언, 초기화
d = [0] * 100
def fib(x):
#종료 조건(1 혹은 2일때 1을 반환)
if x == 1 or x == 2:
return 1
#이미 계산한적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
#아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
d[x] = fib(x - 1) + fib(x - 2)
return d[x]
정리하자면 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 효율적으로 계산을 하는 것이다. 여기서 분할 정복이 떠오른다. 분할-정복 알고리즘이란 큰 문제를 작은 문제들로 나누어 문제를 해결 하는것이다. DP와 분할-정복의 가장 큰 차이점은 DP는 분할된 작은 문제들이 서로 영향을 끼치고 있음을 나타낸다.
재귀 함수를 사용하면 운영체제 에서는 함수를 다시 호출했을때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생 할 수 있다. 따라서 재귀함수 대신 반복문을 사용하여 DP를 구현하는것이 더 효율적이다.
위 트리에서 볼 수 있듯, 실제 호출되는 함수는 파란색 부분이다. 위에서 단순 재귀 함수와 점화식을 썼을때와 비교하면 훨씬 더 적은 연산으로 수행 할 수 있다.
이처럼 재귀 함수를 사용하여 DP를 구현한 방법을, 큰 문제를 풀기 위해 작은 문제를 호출 한다고 하여 탑다운 방식(Topdown) 이라고 한다. 반면, 단순 반복문을 이용하여 소스코드를 작성하는 방식은 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(BottomUp) 이라고 한다. 피보나치 수열을 보텀업 방식으로 해결한 소스 코드는 다음과 같다. 동일한 원리를 적용하되, 단순히 반복문을 이용해 문제를 해결하면 된다. 다음은 보텀업 방식의 피보나치 수열 소스코드이다.
#앞서 계산된 결과를 저장하기 위한 테이블 초기화
d = [0] * 100
#첫번째 피보나치 수와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
#피보나치 함수를 반복문으로 구현(보텀업 DP)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
return d[n]
DP의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 저장소는 'DP 테이블'이라 불리우며, 메모제이션은 탑다운 방식에 국한되어 사용되는 단어이다.
DP문제를 푸는 첫번째 단계는 주어진 문제가 DP유형인지 확인 하는것이다. 특정한 문제를 완전 탐색으로 수행했을때 시간이 오래 걸린다면 DP를 적용할 수 있는지 확인 해보자.
🧷 실전 문제
이제 실전 문제를 풀어 보도록 하자.
문제 1:
이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 피보나치 수열 문제를 다뤄보았던 것처럼 문제를 풀기 전의 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다. 이 문제에서 동일한 함수에서 구하는 값들은 동일하게 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다.
# 정수 X를 입력받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
문제 2:
이 문제를 어떻게 동적 프로그래밍으로 구현 할 수 있을까? 동적 프로그래밍의 두가지 조건을 다시 떠올려 보자.
1. 큰 문제를 작은 하위 문제들로 나눌 수 있어야 한다.
2. 나누어진 작은 문제들의 답은 큰 문제의 답과 일치한다.
일단, 이 문제를 그림으로 도식화를 하면 다음과 같은 케이스들이 나온다.
[1,3,1,5]의 리스트가 주어질때, 위와 같은 8가지 케이스중 최댓값(8)을 리턴하면 된다.
그럼 이 문제의 점화식은 어떻게 세울까? 왼쪽부터 차례로 식량 창고를 턴다고 가정을 해 보자. 우리는 단 2가지 경우만 생각해보면 된다.
따라서 a와 b중에서 더 큰 값을 선택하면 된다. 여기서 알아둘 점은 i - 3번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 왜냐하면 한칸 이상 떨어진 식량 창고는 항상 털 수 있기 때문이다. 따라서 i번째 식량창고에 있는 식량의 양이 k 라고 했을때 점화식은 다음과 같다.
다음은 보텀업 방식으로 풀이를 한 소스코드이다.
#앞서 계산된 결과를 저장하기 위한 dp테이블 초기화
d = [0]*100
#보텀업 방식의 dp구현
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + array[i])
return (d[n-1])