다이나믹 프로그래밍
복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법
💡 DP 사용 조건
✅ 큰 문제를 작은 문제로 나눌 수 있다.
✅ 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
➡ 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 !!
ex) 피보나치 수열
Top-Down
큰 문제를 해결하기 위해 작은 문제 호출
메모이제이션 (Memoization)
: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
➡ 한 번 구한 정보를 리스트에 저장하여 구현
📍 메모이제이션을 활용한 피보나치 수열 코드 (재귀적)
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현
def fibo(x):
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]Bottom-Up
📌 다이나믹 프로그래밍의 전형적인 형태
작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구하기
DP 테이블 : 결과 저장용 리스트
📍 bottom up 방식을 이용한 피보나치 수열 코드 (for문 사용)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
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])
DP 문제 푸는 방법
✅ 저장하기
변수에 따른 결과를 DP 테이블에 저장하고 저장된 값을 재사용 !
✅ 변수 간 관계식 만들기
점화식을 만드는 것 ! 가장 중요한 부분 ⭐
📝 문제 풀어보기
1로 만들기
✏ 문제
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 4가지다.
- X가 5로 나누어떨어지면, 5로 나눈다.
- X가 3으로 나누어떨어지면, 3으로 나눈다.
- X가 2로 나누어떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
4가지 연산을 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력 조건 첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000)
출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
입력 예시
26출력 예시
3🔑 답안
num = int(input())
# DP 테이블 초기화
dp = [0] * 30001
# 다이나믹 프로그래밍 진행 (bottom-up)
for i in range(2, x+1):
# 현재 수에서 1을 빼는 경우
dp[i] = dp[i-1] + 1
# 현재 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
# 현재 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
# 현재 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
dp[i] = min(dp[i], dp[i//5] + 1)
print(dp[num])
📍 26 - 1 = 25
26이 주어지면 25에서 1을 빼는 연산을 하면 되고 여기서 25에 걸리는 연산 횟수보다 1이 더 추가된다.
➡️ dp[i] = dp[i-1] + 1
📍 25 / 5 = 5
25는 5로 나누면 5가 되니까 5보다 연산 횟수가 1이 추가된다.
➡️ dp[i] = min(dp[i], dp[i//5] + 1)
📍 5 / 5 = 1
5는 5로 나누면 1이 되는데 dp[5 // 5] + 1 = dp[1] + 1이고 dp[1]은 0이 들어가 있으니까 1이 된다.
이렇게 같은 연산을 여러 번하는 과정이 있으니 매번 다시 계산하는 것이 아니라 DP 테이블에 저장해놓은 값을 활용하면 된다는 것을 이해하면 된다!
Reference
- 이것이 코딩 테스트다 with 파이썬
- https://doing7.tistory.com/75
- https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming
- https://velog.io/@hoonww/DP%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EB%B0%8F-%ED%99%9C%EC%9A%A9
