Dynamic Programming(동적 계획법)
- 동적 계획법(Dynamic Programming)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘
- 다음과 같은 조건을 만족할 때 사용
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
- 따라서 동적 계획법은 작은 문제의 결과를 메모리에 저장해두었다가, 같은 작은 문제가 나타날 때마다 이를 활용하여 문제를 풀 수 있음
- 동적 계획법은 메모리 공간을 사용하여 시간 복잡도를 줄일 수 있다.
- O(n^2) → O(f(n)) 로 개선
(다항식 수준으로, 문제에 따라 다름)
- O(n^2) → O(f(n)) 로 개선
동적 계획법의 구현 방법
- 작은 문제로 나눈다.
- 작은 문제를 풀어 정답을 구한다.
- 작은 문제의 정답을 저장한다.
- 큰 문제를 작은 문제로 나누어 1 ~ 3을 반복한다.
동적 계획법의 예시 - 피보나치
다음은 동적 계획법을 활용한 예시이다.
피보나치 수열
- 피보나치 수열의 n번째 수를 구하는 문제를 동적 계획법을 활용하여 풀 수 있다.
- 재귀로 푸는 경우 return F(n) = F(n-1) + F(n-2)하여 풀 수 있지만, 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 큰 n번 째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다.
- 따라서, 작은 문제인 F(1)과 F(2),…로 나누어 정답을 배열에 저장한다.
- 그리고 배열을 순회하며, 이전에 구한 작은 문제의 정답을 활용하여 큰 문제의 정답을 구한다.
def fibonacci(n):
if n <= 1:
return n
# 작은 문제의 정답을 저장할 배열 초기화
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 1
# 큰 문제를 작은 문제로 분할하여 풀기
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
# 큰 문제의 정답 반환
return dp[n]동적 계획법의 시간 복잡도
- 동적 계획법은 작은 문제의 정답을 저장해두고 이를 활용하여 문제를 푸는 방식이므로, 시간 복잡도는 작은 문제의 수와 작은 문제를 푸는 시간의 곱이 된다.
- 따라서, 동적 계획법의 시간 복잡도는 O(nk)이다.
- n: 문제의 크기
- k: 작은 문제의 수
BOJ: Q1463 - 1로 만들기 [ 실버 3 ]
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
힌트
10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.
풀이 과정
전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다.
⏩ 메모제이션 방법으로 중복해 계산되는 값을 저장해 효율을 높여준다.
처음 두 수를 알기 때문에 상향식(bottom-up)으로 풀 수 있다.
X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되게 되는데
9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며
3의 경우에는 3 -> 1의 과정을 거친다.
즉, 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다.
앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다.
일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에
dp[i] = dp[i-1] + 1을 통해 횟수를 +1 해준다.
그리고나서, dp[i]가 2 와 3으로 나누어 떨어지는 경우에는 dp[i](1을 빼는 경우)와 dp[i//2or3]+1(나누었을 경우) 중 최소값을 선택한다.
동적프로그래밍으로 푸는 방법
n = int(input())
# DP 테이블 초기화
d = [0] * 1000001
# 다이나믹 프로그래밍 진행(bottom-up)
for i in range(2, n+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)
# 결과 출력
print(d[n])참고
[백준] 1463번 1로 만들기 (Python 파이썬)
[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)
