다이나믹 프로그래밍
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 방법
이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
다이나믹 프로그램잉의 구현은 탑다운 & 보텀업으로 구성
다이나믹 프로그래밍은 동적계획법이라고도 부름
다이나믹 프로그래밍의 조건
- 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 더 큰 문제 해결 가능
- 중복되는 부분 문제(Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결 가능
피보나치 수열
피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능
1,1,2,3,5,8,13,21,34,55,89, …
점화식: 인접한 항들 사이의 관계식
배열이나 리스트를 이용해 수열 표현
# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
피보나치 수열의 시간 복잡도 분석
단순 재귀 함수로 피보나치 수열 해결 시 지수 시간 복잡도를 가지게 된다
f(2)가 중복 호출되는 문제 발생(중복되는 부분 문제)
피보나치 수열의 시간 복잡도는 다음과 같다
세타 표기법 : theta(1.618…^N)
빅오 표기법: O(2^N)
현실 세계에서 사용하기에는 적합하지 않음
다이나믹 프로그래밍의 사용 조건을 만족하는지 확인
- 최적 부분 구조, 2. 중복되는 부분 문제
피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족
메모이제이션(Memoization)
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
한 번 계산한 결과를 메모리 공간에 메모하는 기법
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
값을 기록해놓는 점에서 캐싱(Caching)이라고도 함
탑다운 VS 보텀업
탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 함
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식
결과 저장용 리스트는 DP테이블이라고 부름
엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님
한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있음
탑다운 방식
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 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]
print(fibo(99))
보텀업 방식
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)이다
다이나믹 프로그래밍 VS 분할 정복
다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복
다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제 중복
분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음
분할 정복의 대표적인 예시인 퀵 정렬
한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음
분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않음
다이나믹 프로그래밍 문제에 접근하는 방법
주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
일단 재귀 함수로 비효율 적인 완전 탐색 프로그램을 작성 뒤 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면, 코드를 개선하는 방법을 사용
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제 됨
<문제> 개미 전사
해결 아이디어
ai = i번째 식량창고까지의 최적의 해(얻을 수 있는 식량의 최댓값)
이렇게 정의 시 다이나믹 프로그래밍을 적용가능
왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고를 털지 안 털지 결정하고, 두 가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택
ai = i번째 식량창고까징의 최적의 해, ki = i번째 식량창고에 있는 식량의 양
점화식 : ai = max(ai-1,ai-2, + ki)
# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])
<문제> 1로 만들기
해결 아이디어
최적 부분 구조와 중복되는 부분 문제 만족
ai = i를 1로 만들기 위한 최소 연산 횟수
점화식: ai = min(ai-1,ai/2,ai/3,ai/5) +1
단, 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용 가능
# 정수 X를 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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])
<문제> 효율적인 화폐 구성
해결 아이디어:
ai = 금액 i를 만들 수 있는 최소한의 화폐 개수
k = 각 화폐의 단위
점화식: 각 화폐 단위인 k를 하나씩 확인하며
ai-k를 만드는 방법이 존재하는 경우, ai = min(ai,ai-k +1 )
ai-k를 만드는 방법이 없을 경우, ai = INF
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
<문제> 금광
해결 아이디어:
세 가지 상황 고려
- 왼쪽 위에서 오는 경우
- 왼쪽 아래에서 오는 경우
- 왼쪽에서 오는 경우
세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제 해결
array[i][j] = i행 j열에 존재하는 금의 양
dp[i][j] = i행 j열까지의 최적의 해(얻을 수 있는 금의 최댓값)
점화식: dp[i][j] = array[i][j] + max(dp[i-1][j-1] , dp[i][j-1], dp[i+1][j-1])
리스트의 범위를 벗어나는지 확인
# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
# 금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))
# 다이나믹 프로그래밍을 위한 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
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])
print(result)
<문제> 병사 배치하기
문제 해결:
가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)로 전형적인 다이나믹 프로그래밍 아이디어
본 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 치환 가능
LIS 알고리즘 확인
D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
점화식: 모든 0≤j<i에 대하여, D[i] = max(D[i], D[j+1]+1) if array[j] < array[i]
가장 먼저 입력 받은 병사 정보의 순서를 뒤집고 LIS 알고리즘을 수행하여 정답을 도출
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))
Uploaded by Notion2Tistory v1.1.0