📌 다이나믹 프로그래밍 (=동적계획법)
🔸 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
🔸 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
🔸 다이나믹 프로그래밍의 구현은 일반적으로 Top-down(하향식)과 Bottom-up(상향식) 방식으로 구성된다.
1. 다이나믹 프로그래밍의 조건
1. 최적 부분 구조(Optimal Substructure)
🔸 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem)
🔸 동일한 작은 문제를 반복적으로 해결해야한다.
2. 점화식
🔸 점화식이란, 인접한 항들 사이의 관계식을 의미한다.
ex. 피보나치 수열
1,1,2,3,5,8,13,21,...
an = a(n-1)+a(n-2), a1=1, a2=1
🔸 점화식은 재귀함수를 통해 구현할 수 있다.
🔸 프로그래밍에서 수열을 배열이나 리스트를 이용해 표현한다. 배열이나 리스트를 테이블이라고 한다.
ex. 재귀함수를 이용한 피보나치 수열 => 지수 시간 복잡도
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1)+fibo(x-2)
print(fibo(4))🔸 재귀함수를 이용하면 시간 복잡도가 높게 나타남. 피보나치 수열은 다이나믹 프로그래밍 조건을 만족하므로 다이나믹 프로그래밍으로 해결 가능
3. Top-down vs Bottom-up
🔸 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.
🔸 탑다운은 재귀함수를 이용하고 보텀업은 반복문을 이용한다.
🔸 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이고, 결과 저장용 리스트는 DP 테이블이라고 부른다.
🔸 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미하며, 메모이제이션은 다이나믹 프로그래밍에 국한된 개념이 아니고 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.
#Top-down
d = [0]*100
def fibo(x):
if x==1 or x==2:
return 1
if fibo(x) != 0:
return d[x]
d[x] = fibo(x-1)+fibo(x-2)
return d[x]
print(fibo(99))
#Bottom-up
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])4. Top-down: 하향식
Memoization
🔸 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
🔸 한 번 계산한 결과를 메모리 공간에 메모하는 기법으로, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오며 값을 기록한다는 점에서 캐싱(Caching)이라고도 함
5. 다이나믹 프로그래밍 문제에 접근하는 방법
🔸 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
🔸 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토 => 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍 고려
🔸 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있다.
💡 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음
EX
Ex1. 개미전사
n = int(input())
array = list(map(int, input().split()))
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])Ex2. 1로 만들기
x = int(input())
d = [0]*30001
for i in range(2, x+1):
d[i] = d[i-1]+1
if i%2==0:
d[i] = min(d[i], d[i//2]+1)
if i%3==0:
d[i] = min(d[i], d[i//3]+1)
if i%5==0:
d[i] = min(d[i], d[i//5]+1)
print(d[x])Ex3. 효율적인 화폐 구성
n, m = map(int, input().split())
array = []
for _ in range(n):
array.append(int(input()))
d = [10001]*(m+1) #d는 사용 화폐 개수
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j-array[i]] != 10001:
d[j] = min(d[j], d[j-array[i]]+1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
