다이나믹 프로그래밍 (Dynamic Programming)

#1463번 1로 만들기 https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

수학과 관련된 문제를 모두 해결하고 나니 다이나믹 프로그래밍이라는 새로운 분야를 만나게 됐다. 바로 다이나믹 프로그래밍. 동적 계획법이라고도 표현되는 이 문제는 기존에 내가 애용해왔던 재귀함수와 유사한 부분이다.

 

def : 큰 문제를 작은 문제로 나누어 푸는 방법. 

분할 정복과 비슷하지 않냐는 의견을 낼 수도 있지만, 분할 정복은 같은 형태의 계산을 반복해서 수행하지만 다이나믹 프로그래밍은 작은 문제를 해결한 결과를 재사용하는 형태이다. 

 

동적 프로그래밍을 진행하기 위한 충분조건은 다음과 같다

1) 작은 문제가 반복해서 일어날 것

2) 같은 문제는 구할 때마다 정답이 같을 것

 

2번 조건을 충족시켜야만 동적 프로그래밍의 핵심인 메모이제이션을 사용할 수 있기 때문이다.

 

메모이제이션(Memoization)은 말 그대로 기억하기 방법인데 한번 진행한 연산의 결과를 기억하는 방법이다.

내가 기존에 사용했던 재귀함수의 경우,

이렇게 연산을 작은 값으로 나눠서 진행하는데 (분할 정복)

한번 진행한 연산을 또 다시 진행하는 걸 볼 수 있다.

 

 이런 과정 마저도 최소화 하고자 하는 방법이 동적 프로그래밍, 다이나믹 프로그래밍이라고 할 수 있다.

 

예전에 확률과 통계를 공부할 때 나왔던 개념인 "점화식"을 바탕으로 이해하면 좋다. 

 

피보나치 수열을 예로 들자면

An = An-1 + An-2

이런 식으로 말이다.

 

그럼 A1과 A2를 구하면 이후 모든 An값을 구할 수 있다.

 

위 개념으로 #1463번을 해결해보자.

 

N = int(input())

dp = [0]*(N+1)
for idx in range(2, N+1):
    dp[idx] = dp[idx-1] + 1
    if idx % 2 == 0:
        dp[idx] = min(dp[idx], dp[idx//2]+1)
    if idx % 3 == 0:
        dp[idx] = min(dp[idx], dp[idx//3]+1)

print(dp[N])

문제는 주어진 값을 1로 만드는데 드는 연산횟수를 구하는 건데

연산 방법은 총 3가지이다.

1) 3으로 나누어 떨어질 때 3으로 나누기

2) 2로 나누어 떨어질 때 2로 나누기

3) 1을 빼기

 

각 인덱스에 해당하는 연산횟수를 저장해준다.

0은 의미없는 값이니까 그냥 1로 채우도록 하자.

 

중요한 점은 연산횟수의 최솟값을 구하는건데 

큰 값인 경우에 그 수를 2또는 3으로 나누었을 때 특정한 값이 되는데 (리스트 상으로 보면 1에 가깝게 점프한다고 봐도 괜찮을 것 같다.)

그 값이 1이되는 연산횟수는 이미 저장되어 있기 때문에 그 값의 연산횟수에 1을 더해주면 된다.

 

설명을 진짜 못하니까 그림으로 알아보자

 

1~10까지의 수를 1로 만드는데 필요한 연산횟수를 list로 저장한 결과이다.

2의 경우에는 1을 빼주면 1이된다. : 1

3의 경우에는 3으로 나눠주면 1이 된다. : 1

 

코드 작성 순서는 다음과 같다

2의 경우는 1이다.

3이 들어왔을 경우에 3보다 1 작은 값인 2의 경우를 가져와 1을 더한다.

왜냐면, 3에서 1을 빼면 2가 된다. 그럼 2의 연산 횟수에 1을 더해주면 (3에서 1을 빼는 연산)

3이 1이 되기까지의 연산 횟수가 나온다.

 

보통 이렇게 진행하면 된다.

하지만 3의 연산횟수는 2가 아닌 1이다.

왜냐하면 3은 3으로 나누면 1이 되기 때문이다.

 

따라서 연산을 진행해야 하는 값이 3이나 2의 배수인 경우에는, 1을 빼는 연산을 진행했을 때의 연산 횟수와 비교한 뒤 더 작은 값을 저장하면 된다.

 

그렇게 3의 연산횟수에는 1이 저장된다.

 

이렇게 순차적으로 진행하다보면

작은 수 부터 순서대로 최소한의 연산 횟수가 저장되고

다른 값들은 그 값을 참조? 재사용? 하여 연산 횟수를 구하게 된다. 

 

10의 경우를 생각해보자.

두가지 방법이 있을 수 있는데

하나는 10에서 1을 빼고 9의 연산 횟수에 1을 더하는 방식이다.

또 다른 방법은 10이 2의 배수라는 점을 이용한건데

이렇게 하면 4라는 값이 나온다.

이 두 값을 비교해서 최솟값으로 저장해주면 된다.

 

이정도면 이해 가능?