동적 계획법

정의

• 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 알고리즘.

• 입력 크기가 작은 부분 문제들을 해결한후, 해당 부분문제의 해를 활용해서 보다 큰 크기의 - 부분 문제를 해결한다. 최종적으로는 전체 문제를 해결한다.

• memoization
  프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  
  

시간복잡도

O(N)

구현 방식

top-down

중복되는 하위 문제를 결합하여 최종적으로 최적해를 구하는 방식

num = 10
dp = [0 for _ in range(num+1)]
def fibo(n):
    if n <= 1:
        return n
    if dp[n]:
        return dp[n]
    else:
        dp[n] = fibo(n-2) + fibo(n-1)
        return dp[n]
print(fibo(num))

bottom-up

하위 문제들로 상위 문제의 최적해를 구하는 방식

def fibo_dp(num):
    dp = [0 for _ in range(num+1)]
    dp[0] = 0
    dp[1] = 1
    for index in range(2, num+1):
        dp[index] = dp[index-1] + dp[index-2]
    return dp[num]
print(fibo_dp(10))

문제 풀이

N으로 표현

Answer

DP에 사칙연산 결과의 집합을 넣어두고 다음 연산에서 꺼내 쓰는 방식이다.

def solution(N, number):
    answer = -1
    DP = []

    for i in range(1, 9):
        num_set = { int(str(N) * i) }

        for j in range(0, i - 1):
            for x in DP[j]:
                for y in DP[-j - 1]:
                    num_set.add(x + y)
                    num_set.add(x - y)
                    num_set.add(x * y)

                    if y != 0:
                        num_set.add(x // y)

        if number in num_set:
            return i

        DP.append(num_set)

    return answer

정수 삼각형

Try

아래로 내려올 때마다 합을 구할 수 있는 모든 경우의 수를 DP list에 append 하는 식으로 했다.

def solution(triangle):
    DP = []
    for index, num in enumerate(triangle):
        DP.append([])
        if index == 0:
            DP[0] = num
            continue
        for i_index, i in enumerate(DP[index-1]):
            for j_index, j in enumerate(num):
                if 0<= j_index - i_index < 2:
                    DP[index].append(i+j)                
    print(DP)

tri = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
solution(tri)

Answer

테스트 케이스가 계속 나가서 답을 찾아봤다.
위에서부터 작은 삼각형을 만들어서 점화식으로 더 큰값만 추가해주는 코드다.

이해가 가지 않았던 부분은 인접한 윗 숫자들 중 더 큰 수만 더해주는 부분이었다.

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])

    return max(triangle[-1]) 

Reference

• 동적계획법
• N으로 표현
• 정수삼각형