다이나믹 프로그래밍
- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함(완전탐색 때 사용)
- 다이나믹 프로그래밍의 구현 ⇒ 탑다운(위에서부터 아래 : 하향식 ⇒ 재귀 함수 이용) 과 보텀업(반복문 사용)으로 구성
- 동적(Dynamic)계획법이라고도 부름
- 자료 구조에서의 동적(Dynamic) 할당 : 프로그램이 실행되는 도중에 실행에 필요한 메모리 할당 기법
- 다이나믹 프로그래밍에서의 다이나믹 : 별다른 의미 없음
- 최적 부분 구조
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결 가능
- 중복되는 부분 문제
- 동일한 작은 문제를 반복적으로 해결해야 함
- 피보나치 수열 ⇒ 중복되는 부분 문제점화식 : 인접한 항들 사이의 관계식 => 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가짐
python
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
# 3
java
import java.util.*;
public class Main {
// 피보나치 함수 재귀함수로 구현
public static int fibo(inx x) {
if (x == 1 || x == 2){
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
public static void main(String[] args) {
System.out,println(fibo(4));
}
}
// 3
다이나믹 프로그래밍의 전형적인 형태는 보텀업
- 결과 저장용 리스트는 DP 테이블이라고 함
메모이제이션 : 한 번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
- 값을 기록해 놓는다는 점에서 캐싱이라고 함
- 다이나믹 프로그래밍에 국한된 개념은 아님
메모이제이션 필요한 이유
⇒ 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
메모이제이션을 사용하게 되면 계산이 줄어든다
탑다운 방식
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
dp = [0] * 100
# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if dp[x] != 0:
return dp[x]
# 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
return fibo(x - 1) + fibo(x - 2)
return dp[x]
print(fibo(99))
보텀업 방식
dp = [0] * 100
dp[1] = 1
dp[2] = 1
n = 99
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp [i - 2]
print(dp[n])다이나믹 VS 분할정복
최적 부분 구조를 가질 때 사용 가능
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황에
- 차이점 ⇒ 부분 문제의 중복
- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음
분할 정복의 예시 ⇒ 퀵 정렬
- 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음
- 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않음
📑 다이나믹 프로그래밍 문제 접근 방법
- 다이나믹 프로그래밍 유형인지 파악하기
- 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토⇒ 그게 아니라면 고려
- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용
- 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우 많음
다이나믹 프로그래밍 문제
개미 전사
# n = 4 일 때 선택할 수 있는 경우의 수 8가지
# 1, 3, 1, 5, 1 1, 1 5, 3 5, 0
n = int(input())
arr = list(map(int, input().split()))
d = [0] * 100
# d 인덱스 = 0 1 2 3
# 1 3 3 8
d[0] = arr[0]
d[1] = max(arr[0], arr[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + arr[i])
# d[i] = i번째 식량창고까지의 최적의 해(얻을 수 있는 식량의 최댓값)
# arr[i] = i번째 식량창고에 있는 식량의 양
# 한 칸 이상 떨어진 식량창고는 항상 털 수 있으므로 (i - 3)은 고려할 필요 없음
print(d[n - 1])1로 만들기
n = int(input())
dp = [0] * (n + 1) ## dp에 계산된 값을 저장해둔다. n + 1이라고 한 이유는, 1번째 수는 사실 dp[1]이 아니고 dp[2]이기 때문에, 계산하기 편하게 dp[1]을 1번째 인 것 처럼 만들어준다.
for i in range(2, n + 1):
## 여기서 왜 if 1빼는 방법, 2 나누기, 3 나누기 동등하게 하지 않고 처음에 1을 빼고 시작하는지 의아해 할 수 있다.
## 1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다.
## 즉 셋 다 시도하는 방법이 맞다.
## 여기서 if elif else를 사용하면 안된다. if만 이용해야 세 연산을 다 거칠 수 있다, 가끔 if continue, else continue를 쓰는 분도 계신데, 난 이게 편한듯.
dp[i] = dp[i - 1] + 1
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1) ## 1을 더하는 것은 dp는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다. dp[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1)
print(dp[n])효율적인 화폐 구성
n, m = map(int, input().split())
arr = []
for i in range(n):
arr.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 dp 테이블 초기화
d = [10001] * (m + 1)
d[0] = 0
for i in range(n):
for j in range(arr[i], m + 1):
if d[j - arr[i]] != 10001: # (i - k) 원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - arr[i]] + 1)
# print(d)
# 계산된 결과 출력
if d[m] == 10001: # m원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])