다이나믹 프로그래밍(동적 계획법)
한번 계산된 프로그램은 메모리에 저장하여 다시 계산하지 않도록 한다.
메모리를 적절히 사용하여 시간 효율성을 비약적으로 향상 시킬 수 있다.(시간 복잡도 줄이기)
다이나믹 프로그래밍은 탑다운(하향식), 보텀업(상향식) 두가지로 존재한다.
동적(Dynamic)의 의미
-
자료 구조에서 동적 할당(Dynamic Allocatio)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.
-
다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된다.
다이나믹 프로그래밍의 조건
- 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.
- 종복되는 부분 문제 (Overlapping Subproblem)
- 동작한 작은 문제를 반복적으로 해결해야 한다.
탑다운(하향식) vs 보텀업(상향식)
메모제이션(Memoization)
다이나믹 프로그래밍에서 탑다운(하향식)에 사용되는 방법이다.
한 번 계산한 결과를 메모리 공상네 메호나는 기법이다.
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.
상향식
결과 저장용 리스트를 DP라 부르고 반복문을 통하여 리스트에 값을 기록해 둔다.
예제
- 피보나치 수열
# 재귀함수를 통한 피보나치 수열 만들기
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)- 피보나치 수열의 재귀 함수 사용시 중복 문제
시간 복잡도는 O(2^N)을 갖게 된다.
- 탑다운 다이나믹 프로그래밍을 활용한 피보나치 수열
메모이제이션을 사용시 시간복잡도는 O(N)을 띄게 된다.
# 한번 계산된 결과를 메모이 제이션
n = int(input())
d = [0] * n
# 재귀함수를 사용한 탑 다운
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]- 보텀업 다이나믹 프로그래밍을 활용한 피보나치 수열
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
n = int(input())
d = [0] * n
# 처음 두 피보나치 수는 1
d[1] = 1
d[2] = 1
# 피보나치 함수를 반복문으로 구현
for i in range(3, n+1):
d[i] = d[i -1] + d[i-2]
return(d[n])다이나믹 프로그래밍 vs 분할정복
다이나믹 프로그래밍 분할정복 모두 최적 부분 구조를 가질 때 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있으면 작은 문제의 답을 모아 큰문제를 해결할수 있다.
둘의 큰 차이점은 부분 문제의 중복이다.
-
다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
-
분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않습니다. (퀵 정렬에서는 피벗의 위치가 고정되어 있고 피벗을 다시 처리하는 부분 문제는 호출하지 않는다.)
다이나믹 프로그래밍 문제에 접근하는 방법
-
주어진 문제 어떠한 유형인지를 파악하는것이 중요하다.
-
먼저 그리디, 구현, 환전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토.
- 다른 알고리즘 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍을 고려. -
일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그래도 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.
다이나믹 프로그래밍 문제 풀이
개미전사 문제
# https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7
# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 다이나믹 프로그래밍 진행 (보텀 업)
d[0] =1
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])1로 만들기
# https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7
# 정수 x를 입력받기
x = int(input())
# dp테이블 초기ㅗ하
c = [0] * 30001
# 다이나믹 프로그래밍 (Bottom up)
for i in range(2, x+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)
# 현재 수가 4로 나누어 떨어지는 경우
if i % 4 == 0:
d[i] = min(d[i], d[i//4] +1)
# 현재 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i//5] +1)
print(d[x])효율적인 화폐 구성
# https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7
# 정수 n,m 입력받기
n, m = map(int, input().split())
# n개의 화폐단위 정보 입력받기
array = []
for i in rage(n):
array.apeend(int(input()))
# 한번 게산된 결과를 저장하기 위한 DP테이블 초기화
d = [10001] * (m+1)
# 다이나믹 프로그래밍 (Bottom Up)
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j - array[i]] != 10001: #(i-k)원을 만드는 방법이 존재하는 경우
d[j] = mind(d[j], d[j -array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # m값을 만들 수 없는 경우
print(-1)
else:
print(d[m])
