동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 해결한 뒤, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다.

기본 원리

• 큰 문제를 작은 문제로 나누어 해결한다. - 최적 부분 구조 (Optimal Subproblems)
  ex) 피보나치 수열 -> f(n) = f(n-1) + f(n-2)
• 같은 문제를 여러 번 반복해서 풀어야 한다. - 중복 부분 문제 (Overlapping Subproblems)
  ex) 피보나치 수열 -> f(10)을 구할 때 f(9), f(8) 등을 계속 계산해야 한다.

다이나믹 프로그래밍의 두 가지 방식

• Top-Down (메모이제이션, Memoization)
  재귀 + 메모이제이션(이미 계산한 값 저장)
  ex) 재귀함수 f(n) = f(n-1) + f(n-2)
• Bottom-Up (타뷸레이션, Tabulation)
  작은 문제부터 차근차근 해결
  ex) 반복문 (dp[i] = dp[i-1] + dp[i-2])

# 메모이제이션 (Memoization) #메모에 결과 저장
def fib_memo(n, memo={}):
    if n in memo:  # 이미 계산한 값이면 반환
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# 타뷸레이션 (Tabulation)
def fib_tab(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

다이나믹 프로그래밍 문제

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

ex) 12 = 5 + 5 + (5 / 5) + (5 / 5) -> 6번
ex) 12 = 55 / 5 + 5 / 5 -> 5번
ex) 12 = (55 + 5) / 5 -> 12(number)를 5(N)로 4번에 표현 가능!

핵심 전략 : for문을 돌며 i개 만큼 N을 사용하고 사칙연산을 수행해서 여러 조합을 만들고, i+1에는 i번째에 사용한 조합들을 활용해 새로운 조합을 만든다.

def solution(N, number): # +, -, //, *  #N:5, number:12
    if N == number:
        return 1
    
    dp = [set() for _ in range(9)] #0~8

    for i in range(1, 9): #1~8 i=1에서는 5를 1개 쓰고 사칙연산을 i-1(0)개 쓴다. i=2에서는 5를 2개 쓰고 사칙연산을 i-1(1)개 쓴다.
        if i==8:
            return -1
        dp[i].add(int(str(N)*i))
        #dp[2] = dp[1] + dp[1]  dp[3] = dp[2] + dp[1]
        #dp[4] = dp[3] + dp[1] + dp[2]
        for j in range(1, i):
            for num1 in dp[j]: #dp[1] dp[2], dp[3]
                for num2 in dp[i-j]: # dp[3], dp[2], dp[1]
                    dp[i].add(num1 + num2)
                    dp[i].add(num1 - num2)
                    dp[i].add(num1 * num2)
                    if num2 != 0:
                        dp[i].add(num1 // num2)
        if number in dp[i]:
            return i

dp라는 set()을 9개 만들어 dp[1]~dp[8]까지 이용하고, dp[i]에는 N을 i번 사용한 숫자나, 그 숫자와 이전 조합의 숫자들과의 사칙연산을 수행한 결과를 추가한다.

테스트 케이스 중 2개가 실패로 떠서 어디가 잘못되었나 보았고, 최솟값이 8 이상이 아니라 8보다 크면 -1을 return하는 것이었다.

def solution(N, number): # +, -, //, *  #N:5, number:12
    if N == number:
        return 1
    
    dp = [set() for _ in range(9)] #0~8

    for i in range(1, 9): #1~8 i=1에서는 5를 1개 쓰고 사칙연산을 i-1(0)개 쓴다. i=2에서는 5를 2개 쓰고 사칙연산을 i-1(1)개 쓴다.
    
        dp[i].add(int(str(N)*i))
        #dp[2] = dp[1] + dp[1]  dp[3] = dp[2] + dp[1]
        #dp[4] = dp[3] + dp[1] + dp[2]
        for j in range(1, i):
            for num1 in dp[j]: #dp[1] dp[2], dp[3]
                for num2 in dp[i-j]: # dp[3], dp[2], dp[1]
                    dp[i].add(num1 + num2)
                    dp[i].add(num1 - num2)
                    dp[i].add(num1 * num2)
                    if num2 != 0:
                        dp[i].add(num1 // num2)
        if number in dp[i]:
            return i
    return -1