1. 개요
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식으로 구성된다. (top-down, bottom-up)
다이나믹 프로그래밍은 동적 계획법이라고 합니다.(그런데 여기서 다이나믹은 별 의미 없이 사용됨)
다이나믹 프로그래밍은 다음 조건을 만족할 때 사용 가능합니다.
1. 최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제로 해결이 가능하다. 큰 문제를 분할하여도 여전히 최적의 상태여야 한다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 한다.
- 예시
피보나치 수열 : 앞에 있는 두 수의 합으로 결정된다. 점화식을 세울 수 있어 그들의 관계식을 수학적으로 명시할 수 있다.
An = An-1 + An-2 , A1 = 1, A2 = 1
시작 부분에 대한 값을 알고 있으면 모든 값을 구할 수 있다. 이들을 선형적으로 표현하기 위해 수열을 배열이나 리스트를 이용해 표현합니다.
재귀적으로 해결하면 조금 더 쉽게 프로그래밍을 작성할 수 있다.
2. 피보나치 수열
피보나치 수열이 계산되는 과정을 밑의 그림과 같이 표현할 수 있다. n번째 피보나치 수를 f(n)이라고 할 때, 4번째 피보나치 수열을 구하는 과정이다.
def fibo(x):
if x == 1 or x==2:
return 1
return fibo(x-1) + fibo(x-2) #앞쪽의 칸과 앞두번째 칸
print(fibo(3))
그런데 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가집니다. 위의 그림과 같이 f(2)가 여러번 호출되는 것을 확인할 수 있다. (중복되는 문제 발견)
- 피보나치 수열의 시간 복잡도
O(2^n)이기 때문에 f(30)은 10억 가량의 연산을 수행한다. 너무 많은데, 이를 다이나믹 프로그래밍으로 해결할 수 있다.
다이나믹 프로그래밍을 통해 효율적으로 해결해보자!
- 다이나믹 프로그래밍의 사용 조건을 만족하는지 확인해봅니다.
- 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다.
- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결됩니다.
즉, 피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족합니다.
3. 다이나믹 프로그래밍 방법론
하향식(탑다운/메모제이션)
한번 계산한 결과를 메모리 공간에 메모하는 기법입니다. 주로 재귀함수를 통해서 구현됩니다.
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
- 값을 기록해 놓는다는 점에서 캐싱이라고 합니다.
하향식 VS 상향식
- 다이나맥 프로그래밍의 전형적인 형태는 바텀업 방식입니다.
- 결과 저장용 리스트는 DP 테이블
다이나믹 프로그래밍을 이용하여 피보나치 수열 코드를 다시 작성해보자.
- 탑다운 방식
# 한 번 계산된 결가를 메모제이션
d=[0] * 100
#피보나치 함수를 재귀함수로 구현(탑다운 다이나믹)
def fibo(x):
#종료 조건
if x == 1 or x ==2:
return 1
#이미 계산한 적 있는 문제라면 그대로 반환
if d[x] !=0:
return d[x]
# 아직 계산하지 않은 문제라면 피보나치 결과 반환
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
print(fibo(99))- 바텀업 방식
d = [0] * 100
#재귀함수가 아니라 반복문을 사용
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
위와 같이 색칠된 노드만 처리하면 됩니다.
실제로 호출되는 함수만 확인하면 이렇게 됩니다.
방문한 함수만 호출하도록 출력하는 코드를 보자.
d = [0] * 100
def fibo(x):
print('f(' + str(x) + ')', end='')
if x == 1 or x ==2:
return 1
if d[x] !=0:
return d[x]
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
fibo(6)- 시간 복잡도
O(N)으로 줄어들게 된다. (선형 시간대만큼 줄어들게 됨)
4. 다이나믹 프로그래밍 vs 분할 정복
- 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황이다.
- 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복입니다.
- 다이나믹 프로그래밍 문제에는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됩니다.
- 분할 정복 문제는 동일한 부분 문제가 반복적으로 계산되지 않습니다.
분할된 5가 다시는 사용되지 않습니다. 그래서 부분적으로 나누어진 중복된 부분을 다시 연산에 사용하지 않아요.
다이나믹 프로그래밍 문제에 접근하기 위해서는?
- 가장 먼저 그리디, 구현, 완전 탐색의 아이디어로 문제에 접근해보세요. 너무 큰 시간복잡도가 있다면 다른 알고리즘도 풀이 방법도 없다면 다이나믹 프로그래밍을 생각해보자.
- 일단 재귀 함수로 완전 탐색 프로그램을 작성해보고 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면, 코드를 개선하는 방법을 사용할 수 있다.
5. 다이나믹 프로그래밍 문제 풀이
-
개미 전사
개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 공격한다. 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗는다.
이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챈다.
개미 전사가 메뚜기 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
입력을 {1 3 1 5}로 받으면 2,4 번째 식량창고를 빼앗으면 8개의 식량을 빼앗을 수 있다.
개미 전사를 위해 식량창고 N의 정보가 주어졌을 때 빼앗을 수 있는 최대의 식량은? -
시간 제한 : 1초, 메모리 제한 128MB
-
입력 조건 : 첫째 줄에는 식량창고 N이 주어짐. 둘째 줄에는 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어짐
-
출력 조건 : 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하자.
식량을 고를 수 있는 모든 경우의 수를 고려합니다.
ai를 i번째 식량창고까지의 최적의 해라고 정의합니다. (얻을 수 있는 식량의 최댓값)
두 가지를 비교하여 더 큰 경우를 비교합니다.
큰 문제를 해결하기 위해 i-1, i-2 해도 최적의 해로 등장합니다. 최적 부분 구조가 성립한다.
i-3번째는 고려하지 않는다. 한 칸 이상 떨어진 식량 창고는 항상 털 수 있기 때문이다.
#정수 n을 입력받기
n = int(input())
#모든 식량 정보 입력 받기
array = list(map(int, input().split()))
#앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
#다이나믹 프로그래밍 진행(바텀업)
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])
#계산된 결과 출력
print(d[n-1]) 다이나믹 프로그래밍은 난이도가 높은 알고리즘이기 때문에 이에 대한 공부를 꾸준히 진행한다.
