📌 Dynamic Programming(DP)
🤔 원리
가장 대표적인 예로 피보나치 수열을 들어보자면..
피보나치 수열을 계산할 때 재귀 함수를 사용하게 되면,
매번 f(i-2)와 f(i-1)을 호출해야 하므로, 시간을 엄청 낭비하게 된다.
이렇게 낭비되는 부분을 줄이기 위해서는 배열을 사용하여,
f[i] = f[i-2] + f[i-1]와 같이 이미 계산된 이전 인덱스들을 이용한다.
DP는 이처럼 배열에 각각 저장된 결과들을 재활용하여 새로운 결과를 만드는 느낌으로 접근한다.
A지점까지 가는 경우의 수를 구하는 경우,
A지점의 직전 지점까지 가는 경우의 수를 구해서 1을 더하는 느낌이다.
원점 좌표에서 한칸 한칸 이동해보면서 A지점까지 오는 모든 경우를 구하는 것 보다,
각 지점에서 이전 지점까지의 경우의 수 + 1을 하는게 훨씬 절약이 된다는 느낌이다.
⚙️ DP 구현 예시
x = int(input())
li = [0,0]
for i in range(2,x+1):
temp = li[i-1]
if i % 2 == 0:
temp = min(temp, li[i//2])
if i % 3 == 0:
temp = min(temp, li[i//3])
li.append(temp+1)
print(li.pop())💡 문제는 x를 1로 만드는 최소 연산 수를 구하는 것이다.
x가 2나 3으로 나눠 떨어지면 나눌 수 있고,
그렇지 않으면 1을 뺄 수 있다.
별 생각없이 접근하면 x에서 출발해서 1이 될 때까지 연산을 하게 되고,
그렇게 되면 경우의 수가 너무 많아서 시간을 낭비하게 된다.
하지만 DP로 접근하게 되면,
1에서 출발해서 2의 배수인 경우에는 1을 뺀 친구와 2로 나눈 친구의 경우만 본다.
둘 중에서 더 경우의 수가 적은 상태에서 1을 더하거나 2를 곱하는 연산을 한 번만 하면 된다.
3의 배수인 경우에는 마찬가지로 비교해서 진행하고, 둘 다 아니라면 그냥 1만 더하면 된다.
이런 식으로, 작은 숫자에서부터 계속해서 경우의 수가 더 적은 상태에 연산을 한 번만 하며 나아간다.
더 적은 경우를 찾기만 하면, 거기서 연산 한 번만 해주면 되기 때문에 시간이 매우 절약된다.
