[백준] 1로 만들기

다이나믹 프로그래밍(동적 계획법)

 

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있습니다.

대표적인 방법이 다이나믹 프로그램 기법으로 동적 계획법이라고도 합니다.

 

대표적인 문제는 피보나치 수 입니다.

6번째 피보나치 수 f(6)을 구하려면 다음과 같이 함수 f를 반복해서 호출해야 할 것입니다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 여기서 호출이 정지되게 됩니다.

 

또한 그림을 살펴보면 똑같은 호출이 반복적으로 나타납니다. 이러한 반복적인 호출은 불필요하며, 번수가 증가함에 따라 불필요한 호출 횟수는 기하급적으로 증가하게됩니다.

 

재귀 함수를 사용해서 피보나치 함수 코드를 작성해보겠습니다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

해당 코드의 시간 복잡도는 O(2^n)의 지수 시간이 소요됩니다. 이는 x가 30이면 약 10억 가량의 연산을 수행하는 복잡성을 가지고 있습니다.

 

그래서 우리는 불필요한 연산을 굳이 할 필요가 없으니, 했던 연산은 따로 기억(저장)해놓고 불러오는 방식을 적용하고 합니다. 우리는 그것을 메모이제이션 기법이라고 합니다. 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

메모제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식으로 다시 호출하면 메모한 결과를 그래로 가져오는 기법을 의미합니다.

# 큰 문제를 작은 하위 문제로 나누고, 작은 하위 문제를 풀어나가는 함수
def fibo(x):
    # 기저 조건: x가 1 또는 2인 경우, 결과는 1
    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]

정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법입니다. 

 

이렇게 메모이제이션 기법을 이용하여 그려보면

그림처럼 색칠된 노드만 방문하게 됩니다. 이렇게 프로그램된 알고리즘의 시간 복잡도는 O(N) 입니다. 

 

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 합니다.

 

반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 합니다.

 

피보나치 수열 문제를 아래에서 위로 올라가는 보텀업 방식으로 풀면 다음과 같습니다.

# 피보나치 수열의 값을 저장하기 위한 리스트 초기화
d = [0] * 100

# 초기 조건: 1번째와 2번째 피보나치 수는 1로 설정
d[1] = 1
d[2] = 1

# n까지의 피보나치 수를 계산
for i in range(3, n+1):
    # 다이나믹 프로그래밍을 사용하여 현재 피보나치 수를 이전 두 수의 합으로 계산하고 저장
    d[i] = d[i-1] + d[i-2]

 

가능 하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장합니다. 

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문입니다.

 

---

이제 다이나믹 프로그래밍으로 관련 문제를 풀어보겠습니다.

BOJ: Q1463 - 1로 만들기 [ 실버 3 ]

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

---

풀이 과정

해석

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(나누었을 경우) 중 최소값을 선택한다.

1. 큰 문제를 작은 문제로 나누는 방식을 사용합니다. 작은 문제는 주어진 숫자 N을 1로 만드는 최소 연산 횟수입니다.

 

2. 작은 문제를 해결하기 위해 Bottom-Up 방식을 사용합니다. 즉, 1부터 N까지의 모든 숫자에 대한 최소 연산 횟수를 계산하며 더 큰 숫자들을 작은 숫자들로부터 구합니다.

 

3. 각 숫자 i에 대해 최소 연산 횟수를 저장할 리스트를 만듭니다. 이 리스트를 dp라고 하겠습니다.

 

5. dp[i] 는 숫자 i를 1로 만들기 위해 필요한 최소 연산 횟수입니다. dp[i]를 계산할 때, 이전 단계의 연산횟수를 활용합니다. 예를 들어, dp[i]를 계산할 때, dp[i-1], dp[i /2], dp[i / 3]의 값을 이용합니다.

 

# 사용자로부터 정수 N을 입력받습니다.
n = int(input())

# dp 리스트 초기화: 각 숫자 i를 1로 만들기 위한 최소 연산 횟수를 저장합니다.
dp = [0] * (n+1)

# 숫자 2부터 N까지 순회하며 최소 연산 횟수를 계산합니다.
for i in range(2, n+1):
    # 현재 숫자 i를 1로 만드는 최소 연산 횟수는 기본적으로 i-1을 1로 만드는 횟수에 1을 더한 값입니다.
    dp[i] = dp[i-1] + 1
    
    # 만약 i가 2로 나누어 떨어지는 경우, 2로 나눈 숫자를 이용한 연산 횟수와 비교하여 더 작은 값을 선택합니다.
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    
    # 만약 i가 3으로 나누어 떨어지는 경우, 3으로 나눈 숫자를 이용한 연산 횟수와 비교하여 더 작은 값을 선택합니다.
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

# dp[n]에는 주어진 N을 1로 만드는 최소 연산 횟수가 저장되어 있습니다.
print(dp[n])

 

n을 5로 설정했을 때, 주어진 코드에서 연산 과정을 시각적으로 이해를 도와드리겠습니다.

1. 초기 설정:
   - n = 5로 설정됩니다.
   - dp 리스트를 초기화하고, dp = [0, 0, 0, 0, 0, 0] 형태로 시작합니다.

2. i = 2일 때:
   - dp[2] = dp[1] + 1 = 0 + 1 = 1
   - 2를 1로 만드는 최소 연산 횟수는 1입니다.

3. i = 3일 때:
   - dp[3] = dp[2] + 1 = 1 + 1 = 2
   - 3을 1로 만드는 최소 연산 횟수는 2입니다.

4. i = 4일 때:
   - dp[4] = dp[3] + 1 = 2 + 1 = 3
   - 4를 1로 만드는 최소 연산 횟수는 3입니다.

5. i = 5일 때:
   - dp[5] = dp[4] + 1 = 3 + 1 = 4
   - 5를 1로 만드는 최소 연산 횟수는 4입니다.

6. 최종 결과:
   - dp[5]에 저장된 값인 4가 출력됩니다.
   - 주어진 N = 5를 1로 만드는 최소 연산 횟수는 4입니다.

따라서, 주어진 코드를 사용하여 N = 5일 때, 5를 1로 만들기 위한 최소 연산 횟수는 4회입니다.