오늘부터 다이나믹 프로그래밍을 풀기 시작했다. 어려운데 너무 재밌음

1463: 1로 만들기

1. 내 풀이: 실패

import sys

N = int(sys.stdin.readline())

while N != 1:
    if (N-1)%2==0 or (N-1)%3==0:
        N = N-1
    if N%2 == 0:
        N = N%2

당연히... 실패... 일반적으로 하는 구현만 하면 될 줄 알았는데 결국 -1도 해봐야하고 3으로 나눠도 봐야하고 2로도 나눠 봐야했다. 이렇게 되면 일단 시간복잡도가 되게 커질 것이기 때문에...

2. 다른 풀이

import sys

N = int(sys.stdin.readline())
dp = [0]*(N+1)

for i in range(2, N+1):
    dp[i] = dp[i-1] + 1

    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N])

결국 답을 봤다 ^^ 일단 다이나믹 프로그래밍이라는 것을 처음 접하기도 했고, 해당 알고리즘을 알아야 풀 수 있을 것 같아서 찾아보았다.

DP(Dynamic Programming)에 대한 전체적인 이해는 아래의 블로그를 참고 했다.
https://techblog-history-younghunjo1.tistory.com/183

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

다이나믹 프로그래밍은 한국어로 동적 계획법이라고 불린다. 우리들의 친구, 위키백과에 따르면, 동적 계획법의 사전적 정의는 다음과 같다.

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

이 DP의 핵심은 시간 측면에서 이득을 보기 위해 메모리를 좀 더 사용하는 것이라고 할 수 있다. 좀 더 쉽게 설명하면, n이라는 목표에 다다르기 위해 n번의 계산을 해야한다고 생각해보자.

n<p일 때, p라는 목표에 다다르기 위해서는 p번의 계산을 해야 한다. 그럼, n번까지의 계산 결과는 어떤 메모리에 저장해두고, p번의 계산을 할 때 n번의 계산 결과를 메모리로부터 가져온 후, (p-n)번의 계산만 하는 것이다.

이렇게 메모리를 좀 더 써서 시간적 이득을 보는 것이 DP라고 할 수 있다.
가장 대표적인 예시가 피보나치 수열이다. 이는 위의 블로그에 아주 잘 설명되어 있으니 참고하면 좋을 듯하다.

이 다이나믹 프로그래밍에는 2가지의 접근법(방법)이 존재한다.

• Top-Down식 (하향식) -> 대부분 재귀함수
• Bottom-Up식 (상향식) -> 대부분 for문

이 문제를 예시로 들어보면(10이 1이 되기 위해서 몇 번의 연산을 해야 하는가?),

• Top-Down식: 10 -> 9 -> 3 -> 1
• Bottom-Up식: 1 -> 3 -> 9 -> 10

이다.

위 블로그(책)에서는 상향식으로 접근하는 것을 권장한다. 상향식의 경우 재귀함수를 사용하는데, 테스트에 따라 재귀 횟수 제한이 걸릴 수 있기 때문이다. 그래서 나도 이 문제를 상향식으로 접근해보았다.

import sys

N = int(sys.stdin.readline())

# 계산값 저장소
dp = [0]*(N+1)

DP 문제 풀이의 가장 기본은 (적어도 나는 그렇게 생각한다.) 계산한 값을 저장할 곳을 만드는 것이다. dp라는 리스트는 다음을 의미한다.

• 인덱스: 해당 숫자 (10이라면 10 자체)
• 인덱스에 해당하는 값: 1에서 해당 숫자까지 도달하기 위해 계산해야 하는 횟수

for i in range(2, N+1):
    dp[i] = dp[i-1] + 1

    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N])

그 다음은 이제 3가지의 경우 (1 빼기, 2로 나누기, 3으로 나누기)를 다 따져주는 것이다. 일단 기본적으로 1을 빼고 시작한다. 그 이유는 10에서 9가 되기 위해서는 1을 빼줘야 하고, 이는 연산 횟수가 한 번 더 늘어나는 것과 같으므로 1을 더해주는 것이다.

그 후 if문을 통해 2와 3으로 나눠 떨어지는지 확인한다. 큰 수에서 3으로 나누면 1로만 뺄 때보다 연산 횟수가 확 줄어들게 된다. 그러므로 min 함수를 통해 이를 비교해서 값(연산 횟수 값)을 바꿔준다.

이 부분은

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1  

    if i%2 == 0 and dp[i] > dp[i//2] + 1 :
        dp[i] = dp[i//2]+1
        
    if i%3 == 0 and dp[i] > dp[i//3] + 1 :
        dp[i] = dp[i//3] + 1
        
print(dp[n])

이렇게 쓸 수도 있다.
(출처: https://infinitt.tistory.com/247)

진짜 DP라는 개념이 생소했는데 조금은 가까워진 것 같다. 오늘도 신기한 알고리즘의 세계 끝 ~!