DP(동적 프로그래밍)

DP란?

복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은
하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘입니다.
즉, 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘입니다.

상황에 따라 구현 방식은 다르다. 가장 쉬운 문제는 피보나치 문제이다.
원래 피보나치 수열은 N번째 항을 재귀로 호출해 중복된 연산으로 계산이 오래걸린다. 그러나 DP를 통해 하위의 배열을 미리 만들고, 중간 결과를 저장해서 시간복잡도를 O(N)까지 줄일수 있습니다.

DP문제가 어려운 이유는 문제를 보고 DP를 생각해내기 어렵다는 점입니다. 테이블을 정의해야하고 점화식을 찾은 후에 초기 값을 정의해야합니다. 의외로 점화식 찾기가 어렵기 때문에 많은 문제를 풀어보면서 데이터를 쌓아야 문제를 잘 해결해 나갈 수 있습니다.

DP는 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.), 중복된 하위 문제(동일한 작은 문제를 반복적으로 해결해야 한다.) 와 같은 조건이 만족할 때 사용할 수 있다.

특징

• 중복된 하위 문제들을 여러 번 해결하는 것을 방지하여 효율성을 높입니다.
• 메모이제이션 또는 타뷸레이션 기법을 사용합니다.

++ DP 풀이 방식인 상향식, 하향식에 대해 알아보자

상향식(Bottom-up)

• for반복문
• Base-condition(초기값)으로 시작해서 위로 올라감.
• 오버헤드를 줄일 수 있고, 일반적으로 성능이 더 좋음.

하향식(Top-down)

• 재귀함수 사용
• 큰 문제를 작은 문제로 쪼갬. (큰 문제를 해결하기 위해 작은 재귀 함수를 호출)
• 작은 문제에 대한 값이 제일 먼저 구해지고, 이후 위로 올라가면서 합쳐지는 방식
• 반복적으로 나오는 것들을 메모리에 저장하여 재사용.
• 메모이제이션 있음(캐싱)
• 오버헤드 가능성이 있음.

기본적인 DP 알고리즘 코드는 다음과 같다.

백준 2748 피보나치 수 2

import sys

input = sys.stdin.readline

def DP(n):
    # N번째 피보나치 수 저장 리스트 공간
    dp = [0] * (n + 1)
    
    # 초기값 설정
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
        
    return dp[n]  # N번째 피보나치 수 반환

# 입력 받기
N = int(input().strip())

# 결과 출력
print(DP(N)) 

그럼 문제를 풀어보며 DP에 대해서 이해해보자.