알고리즘 - DP

동적 계획법(DP: Dynamic Programming)이란

DP는 하나의 커다란 문제를 작은 문제로 나누고, 그 결과를 저장하며 재활용해 효율적으로 해결하는 문제 해결 패러다임이다. 특정 알고리즘이라기보다는 하나의 접근 방식이다.

DP 적용 조건

중복되는 부분 문제 (Overlapping Subproblems)

동일한 하위 문제가 반복적으로 등장할 때 사용.

fibo(n)을 구할 때 → fibo(n-1)과 fibo(n-2)는 여러 번 계산된다.

최적 부분 구조 (Optimal Substructure)

큰 문제의 해답이 작은 문제의 최적해로 구성될 수 있는 경우.

fibo(n) = fibo(n-1) + fibo(n-2)

→ 작은 문제들의 결과를 조합해 큰 문제 해결 가능하다.

DP가 적합한 문제 유형

경우의 수가 너무 많은 문제

DFS나 완전탐색으로는 불가능할 정도의 분기 발생

→ 예 : 정수 삼각형 문제

중복 계산이 많은 문제

→ 예 : 피보나치, LCS, 배낭 문제

시간복잡도상 비효율적인 구현이 예상될 때

→ 그리디나 구현, 완탐 먼저 검토 후, 계산량이 과도하면 DP 고려

DP 문제 해결 절차

1. DP 배열 정의하기

핵심은 dp[i] 또는 dp[i][j]가 무엇을 의미하는가를 한 문장으로 설명할 수 있어야 함.

정의가 명확하지 않으면 점화식 도출도 어렵다.

2. 점화식 도출

큰 문제를 작은 문제들의 결과로 표현하는 수식을 만드는 과정

핵심은 현재 상태를 이전 상태로 표현하는 방법을 찾는 것

예시

피보나치 수열

dp[n] = dp[n-1] + dp[n-2

LCS

※ 보통 dp 테이블은 dp[len(A)+1][len(B)+1]로 만들며,

dp[i][j]는 A의 i-1번째 문자와 B의 j-1번째 문자를 비교하는 의미로 사용.

A[i] == B[j] → dp[i][j] = dp[i-1][j-1] + 1

A[i] != B[j] → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

배낭 문제 (0/1 Knapsack)

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

모든 점화식은 “선택/비선택”, “일치/불일치” 두 가지 상황으로 나눠보면 실마리가 잡힌다.

3. 초기 조건 설정

점화식 계산을 시작하기 위해 반드시 필요한 기본값을 설정하는 단계

→ 이 값이 없으면 계산이 멈추거나 잘못된 결과가 나올 수 있음

예시

피보나치 수열은 dp[0] = 0, dp[1] = 1

LCS는 dp[i][0] = 0, dp[0][j] = 0 (한 쪽 문자열이 비어 있을 경우)

배낭 문제

dp[0][w] = 0 (물건이 없음)
dp[i][0] = 0 (배낭 용량이 0)

초기 조건은 “계산이 멈추지 않게 보장하는 최소 단위”로 이해하면 좋음

팁 요약

정의는 직관적으로 : dp[i]는 무엇을 의미하는가?

점화식은 관계를 찾는 것이다. 큰 문제 ← 작은 문제들

초기 조건은 안전망이다. 시작점이자 실수 방지 포인트

DP를 떠올려야 할 때는 구현[탐색이 시간초과 날 때 or 중복 계산이 느껴질 때

기출에서 자주 나오는 유형은 피보나치, 정수 삼각형, LCS, 배낭, 계단 오르기, 타일 채우기

대표적으로 바텀업과 탑다운이 있다

Bottom-Up 방식 (반복문 사용)

작은 문제부터 차례대로 해결하는 방식으로, 더 직관적이며 중복 계산을 방지 가능. 전형적인 방식

예시로 피보나치 수열에서 작은 수부터 계산해 나가는 방식.

# 바텀업 방식 - 반복문
def fibonacci(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 = 10
dp = [-1] * (n + 1)
print(fibonacci(n))              # Output: 55

Top-Down 방식 (메모이제이션 사용)

재귀적으로 큰 문제를 작은 문제로 나누어 해결하면서, 중복 계산을 방지하기 위해 결과를 저장하는 방식.

메모지제이션은 Top-Down 방식의 핵심 기법으로, 재귀적으로 구한 하위 문제의 결과를 배열에 저장해 같은 계산을 반복하지 않도록 하는 최적화 방법이다.

예시로 피보나치 수열에서 재귀로 계산한 값을 저장해 중복 계산을 방지.

def fibonacci_top_down(n, dp):
    if n <= 1:
        return n
    if dp[n] != -1:
        return dp[n]
        
    dp[n] = fibonacci_top_down(n - 1, dp) + fibonacci_top_down(n - 2, dp)
    return dp[n]

n = 10
dp = [-1] * (n + 1)
print(fibonacci_top_down(n, dp))  # Output: 55

DP와 다른 알고리즘 기법의 차이점

분할 정복 vs DP

항목	분할 정복 (Divide & Conquer)	동적 계획법 (Dynamic Programming)
공통점	문제를 더 작은 문제로 나눠서 해결	문제를 작은 하위 문제로 나눔
차이점	서로 다른 하위 문제, 중복 없음	중복되는 하위 문제 존재
예시	퀵 정렬, 병합 정렬, 이진 탐색	피보나치 수열, LCS, 배낭 문제

핵심 : 하위 문제의 중복 여부가 DP 적용 여부를 결정짓는 핵심.

그리디 vs DP

항목	그리디 알고리즘	동적 계획법 (DP)
접근 방식	매 순간 최적의 선택	모든 가능한 선택을 고려
결과	빠르게 구할 수 있으나, 항상 최적해는 아님	계산은 오래 걸리지만 최적해 보장
필요 조건	그리디 선택 속성과 최적 부분 구조	중복되는 부분 문제와 최적 부분 구조
예시	활동 선택, 다익스트라, 일부 동전 문제	피보나치 수열, LCS, 배낭 문제

핵심은 그리디는 “지금 이 선택이 전체적으로도 최선인가?” DP는 “모든 경우를 계산해 최선인 걸 찾자”

예시로 보는 그리디 vs DP

동전 거스름돈 문제

동전 종류 : [1, 3, 4], 목표 금액 : 6

그리디 : 4 + 1 + 1 → 동전 3개

DP : 3 + 3 → 동전 2개

그리디는 항상 최적해를 보장하지 않음 (통화 체계에 따라 다름)

DP는 모든 조합을 시도하므로 항상 최적해 도출 가능

DP가 적합한 문제의 특징

중복되는 부분 문제 존재

같은 계산이 여러 번 반복됨

→ 메모이제이션(Top-Down) 또는 테이블화(Bottom-Up)으로 해결

최적 부분 구조는 큰 문제의 최적해가 작은 문제의 최적해로 구성 가능

그리디가 실패하는 문제는 부분의 최적이 전체 최적이 아닌 경우

대표 문제

피보나치 수열

배낭 문제 (0/1 Knapsack)

LCS (최장 공통 부분 수열)

그리디가 적합한 문제의 특징

그리디 선택 속성은 현재의 최적 선택이 전체의 최적해로 이어짐

최적 부분 구조는 부분 최적해들을 결합해 전체 최적해 도출 가능

대표 문제는 활동 선택 (종료 시간이 빠른 순), 최소 신장 트리 (크루스칼, 프림), 다익스트라 알고리즘

실전에서의 판단 기준

문제를 보자마자 “중복 여부”와 “현재 선택이 전역 최적에 영향을 줄까?”를 먼저 생각해보기

실전 팁은 그리디 먼저 시도 → 최적해가 안 나오면 DP 고려하기.

DP는 구현이 복잡하더라도 항상 정답을 보장할 수 있는 강력한 방법

그리디는 빠르게 접근할 수 있지만, 반드시 정답을 보장하지 않음

DP 문제 예시(피보나치, 개미 전사, 1로 만들기, 최단 경로)

피보나치 수열 (Bottom-Up, Top-Down, 재귀) 관련 문제

피보나치 수열을 Bottom-Up 방식으로 구현하면, 중복 계산을 피하면서 효율적으로 값을 계산 가능하다.

#  재귀로 피보나치
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

print(fibonacci_recursive(10))  # Output: 55
# 시간복잡도 O(2^n)

개미 전사 문제

첫째 줄에 식량창고의 개수 N이 주어짐 (3≤N≤100).

둘쨰 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어집니다(0≤K≤1,000). 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하기.

# 4
# 1 3 1 5 <- 입력 예시

# 정수 N 입력 받기
n = int(input())

# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위해 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍 진행(바텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
	d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])
# 시간복잡도 O(N) - 단일 for 루프

1로 만들기 문제

첫째 줄에 정수 X가 주어짐.

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

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍 진행 (보텀업 방식)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

# 입력 예시 26
# 출력 예시 3

최단 경로 문제 (Shortest Path Problem) - 다익스트라 알고리즘 단순화

그래프에서 시작점부터 도착점까지의 최단 경로를 찾는 문제로, DP를 이용해 각 노드까지의 최단 거리를 저장하여 해결할 수 있다.

def shortestPath(graph, start, end):
    n = len(graph)
    
    # dp 리스트는 시작점에서 각 노드까지의 최단 거리 저장. 
    # 처음에는 모든 노드에 대해 무한대로 설정, 시작점의 거리는 0
    dp = [float('inf')] * n
    dp[start] = 0
    
		# 모든 노드를 순회하면서 최단 거리 갱신
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:  # i -> j 간선이 존재하면
                dp[j] = min(dp[j], dp[i] + graph[i][j])
		
		# 최종적으로 시작점에서 종료점까지의 최단 거리를 반환
    return dp[end]
    
# 예시 그래프. 각 노드는 0부터 시작, 그래프는 인접 행렬로 표현.
# 예: graph[i][j]는 노드 i에서 노드 j로 가는 가중치(거리) 나타냄.
graph = [
    [0, 4, 2, 0],
    [4, 0, 1, 5],
    [2, 1, 0, 8],
    [0, 5, 8, 0]
]

# 노드 0에서 노드 3까지의 최단 거리를 계산
print(shortestPath(graph, 0, 3))  # Output: 6
# 시간복잡도 O(n^2). n은 그래프의 노드의 수