다이나믹 프로그래밍
메모리를 적절히 사용해 수행 시간 효율성을 비약적으로 향상시키는 방법
다이나믹 프로그래밍 = 동적 계획법
동적 할당 : 프로그램이 실행되는 도중에 실해에 필요한 메모리를 할당하는 기법
조건1) 최적 부분 구조
: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
조건2) 중복되는 부분 문제
: 동일한 작은 문제를 반복적으로 해결해야 함
EX. 피보나치 수열
- 점화식 : 인접한 항들 사이의 관계식
- 이런 수열을 배열이나 리스트를 이용해 표현함
# 피보나치 함수를 재귀함수로 구현
def fibo(x) :
if x == 1 or x == 2 :
return 1
return fibo(x-1) + fibo(x-2)
- 지수 시간 복잡도를 가짐! - 비효율적인 문제 - > 다이나믹 프로그래밍으로 해결~!
다이나믹 프로그래밍 구현 방법
1) 하향식 - 메모이제이션 (Memoization) - 탑다운 방식
: 한 번 계산한 결과를 메모리 공간에 메모
: 큰 문제를 해결하기 위해서, 작은 문제들을 재귀적으로 호출하여 작은 문제가 해결되었을 때 큰 문제가 해결될 수 있음
: 캐싱
: 시간 복잡도는 O(N)
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기ㅗ하
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x) :
# 종료 조건 (1 or 2일때 , 1 반환)
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]
2) 상향식 - 보텀업 방식
: 작은 문제를 해결해나가면서 , 먼저 계산했던 문제들 이용해서 그 다음 문제 차례로 해결함
: SO 반복문 이용함
: 결과 저장용 리스트 = DP 테이블
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수 반복문으로 구현 (보텀업 다이나믹 프로그래밍)
for i in range(3, n+1) :
d[i] = d[i-1] + d[i-2]
분할 정복 알고리즘 공통점
- 최적 부분 구조 (큰 문제를 작은 문제로 나눌 수 O, 작은 문제 답 모아 큰 문제 해결 가능)
분할 정복 알고리즘과 차이 : 부분 문제의 중복
다이나믹 프로그래밍
: 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
분할 정복 알고리즘
: 동일한 부분 문제가 반복적으로 계산되지 않음
Tips!
1. 그리디, 구현, 완전 탐색 등으로 풀어보다가 안된다? -> 다이나믹 프로그래밍 고려해보기!
2. 재귀로 완전 탐색 알고리즘 작성 뒤 -> 탑다운 문제로 코드 개선하기!
문제1) 개미 전사
# 정수 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])
문제2) 1로 만들기
# 정수 x를 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍 진행 (보텀업)
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])
문제3) 효율적인 화폐 구성
Step 0 (초기화)
: 각 인덱스에 무한 값 (10001)로 설정
Step 1
: 첫번째 화폐단위 2 확인
Step 2
: 두번째 화폐단위 3 확인
Step 3
: 세번째 화폐단위 5 확인
# 정수 N, M을 입력받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n) :
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍 진행 (보텀업)
d[0] = 0
for i in range(n) : # i = 각각의 화폐 단위
for j in range(array[i], m+1) : # j = 각각의 금액
if d[j - array[i]] != 10001 : # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i] + 1)
# 계산된 결과 출력
if d[m] == 10001 : # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else :
print(d[m])
문제4) 금광
- 세가지 경우 중 가장 많은 금을 가지고있는 경우를 테이블에 갱신해주어 문제 해결!
# 테스트 케이스 (Test Case) 입력
for tc in range(int(input())) :
# 금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input())
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = []
index = 0
for i in range(n) :
dp.append(array[index:index + m])
index += m
# 다이나믹 프로그래밍 진행
for j in range(1, m) : # 열 확인
for i in range(n) : # 행 확인
# 왼쪽 위에서 오는 경우
if i == 0 : left_up = 0 # 범위 벗어나면 0으로 초기화
else : left_up = dp[i - 1][j - 1]
# 왼쪽 아래에서 오는 경우
if i == n - 1 : left_down = 0
else : left_down = dp[i + 1][j - 1]
# 왼쪽에서 오는 경우
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n) :
result = max(result, dp[i][m - 1])
문제5) 병사 배치하기
가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence, LIS)
: {4, 2, 5, 8, 4, 11, 15} -> {4, 5, 8, 11, 15}
D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
해당 문제는 가장 긴 감소하는 부분 수열을 찾는 문제
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n) :
for j in range(0, i) :
if array[j] < array[i] :
dp[i] = max(dp[i], dp[j] + 1)
# 열외해야 하는 병사의 최소 수를 출력
print( n - max(dp) )
https://www.youtube.com/watch?v=5Lu34WIx2Us&t=1s