WIL WEEK5

정범진·2026년 3월 27일
WILweek5

DP 정리

DP란

DP(Dynamic Programming)는 큰 문제를 작은 문제로 나누어 풀고, 이미 계산한 결과를 재사용해서 중복 계산을 줄이는 방법이다.

핵심 방식

메모이제이션, 탑다운

  • 재귀를 쓰면서 결과를 저장한다.
  • 이미 계산한 값을 다시 계산하지 않도록 만든다.

바텀업

  • 반복문으로 아래부터 계산한다.
  • 작은 문제의 결과를 이용해 큰 문제의 값을 채운다.

DP 구현 순서

  1. 계산해야 할 배열의 값들을 명확히 정의한다.
  2. 계산할 값의 점화식을 찾는다.
  3. 점화식을 이용하여 배열에 값들을 계산하여 채운다.
  4. 원래 문제의 답을 추출한다.

정리 메모

  • 처음에는 "어떻게 계산할지"보다 "무엇을 저장할지"를 먼저 정의하는 것이 중요하다.
  • 점화식은 문제 안의 재귀적 구조를 찾는 과정이다.
  • 구현은 바텀업 방식으로 계산 순서를 잡으면 흐름이 잘 보인다.

SRTBOT

  • Subproblem
  • Relation
  • Topological order
  • Base case
  • Original problem
  • Time

이건 그냥 DP 문제를 풀 때 체크해야 하는 사고 순서라고 보면 된다.

1. DP = Local brute force 가 무슨 뜻이냐

  • 전체 문제를 한 방에 무식하게 풀면 경우의 수가 너무 많다
  • 그런데 작은 부분 문제 하나만 놓고 보면, 가능한 선택이 몇 개 안 된다
  • 그래서 각 하위 문제에서는 브루트포스처럼 가능한 선택을 다 비교해도 된다
  • 대신 그 결과를 저장해서 중복 계산을 막는다

즉,

  • 전체는 brute force 하면 망함
  • 하지만 로컬(작은 하위 문제) 에서는 가능한 경우를 다 보는 게 가능함
  • 그걸 점화식으로 연결한 게 DP다

예를 들어 피보나치로 보면:

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

여기서 fib(n)을 구할 때 할 일은 사실 로컬하게 보면 별거 없다.
그냥

  • fib(n-1)
  • fib(n-2)

이 두 개만 보면 된다.

이런 식으로 각 위치에서 선택지는 작고, 그 작은 선택들을 반복해서 전체 답을 만든다.

2. DP에서 필요한 단계: SRTBOT

이제 하나씩 자세히 보자.

S = Subproblem (하위 문제 정의)

이게 제일 중요하다.
DP는 사실상 “문제를 어떻게 잘게 자를 거냐” 가 거의 전부다.

하위 문제를 잘 정의해야 한다.

예를 들어 피보나치에서는:

  • dp[i] = fib(i)
    즉, i번째 피보나치 수를 구하는 문제

계단 오르기 문제라면:

  • dp[i] = i번째 계단까지 가는 방법 수

배낭 문제라면:

  • dp[i][w] = 앞에서 i개 물건만 고려해서, 무게 제한 w일 때 얻을 수 있는 최대 가치

이런 식이다.

좋은 subproblem의 조건

좋은 하위 문제는 보통 이런 특징이 있다:

  • 원래 문제보다 작다
  • 여러 번 재사용된다
  • 하위 문제들의 답으로 상위 문제를 만들 수 있다

실수하기 쉬운 부분

DP를 못 푸는 대부분 이유는 점화식이 아니라 subproblem 정의를 이상하게 해서다.

예를 들어
“최대 합을 구한다” 라는 문제에서
dp[i] = 전체 배열에서 최대 합
이렇게 잡으면 안 된다.
왜냐면 이건 i와 상관없이 너무 뭉뚱그려져 있어서, 작은 문제로 쪼개진 게 아니기 때문이다.

대신
dp[i] = i에서 끝나는 최대 부분합
이런 식으로 잡아야 관계가 생긴다.

즉, subproblem은 작고, 구조가 있어야 한다

R = Relation (관계, 점화식)

subproblem을 정의했으면, 이제 작은 문제들끼리 어떤 관계를 갖는지 써야 한다.
이게 바로 점화식이다.

예를 들어 피보나치:

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

계단 오르기:

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

배열 최대 부분합(Kadane 느낌):

dp[i] = max(dp[i-1] + a[i], a[i])

배낭 문제:

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

relation을 세울 때 보는 관점

보통 이런 질문을 던지면 된다:

  • 마지막 선택이 뭐였지?
  • 지금 상태에 오기 직전 상태는 뭐지?
  • 현재 답이 이전 답들로부터 어떻게 만들어지지?

DP 문제에서 자주 나오는 패턴은
“마지막 행동 기준으로 경우를 나눈다” 이다.

예를 들어 “i번째 계단에 도착했다”면 마지막 행동은:

  • i-1에서 한 칸 올라왔거나
  • i-2에서 두 칸 올라왔거나

그래서 dp[i] = dp[i-1] + dp[i-2]가 되는 거다.

relation이 중요한 이유

DP는 결국
“답을 저장하는 재귀”
라고 생각해도 된다.

relation이 없으면 그냥 저장만 하는 거고, relation이 있으면 문제 구조가 드러난다.

T = Topological order (위상 순서, 계산 순서)

DP에서 어떤 상태 dp[i]를 계산하려면,
그보다 먼저 필요한 상태들이 다 계산되어 있어야 한다.

예를 들어
dp[i] = dp[i-1] + dp[i-2]
라면 dp[i-1], dp[i-2]를 먼저 알아야 한다.

그래서 계산 순서는 보통

  • 0
  • 1
  • 2
  • ...
  • n

이 된다.

이걸 어려운 말로 topological order 라고 한다.

왜 위상 순서라는 말을 쓰냐

각 subproblem을 노드라고 생각하고,
“이 상태가 저 상태에 의존한다” 를 간선으로 보면,
의존 그래프가 생긴다.

그 그래프에서
의존하는 애보다, 의존받는 애를 먼저 계산하는 순서
가 topological order다.

쉽게 말하면:

  • 필요한 재료 먼저 만들고
  • 그 다음 완성품 만든다

이거다.

예시

피보나치:

  • dp[0], dp[1] 먼저
  • dp[2]
  • dp[3]
  • ...
  • dp[n]

2차원 DP에서도 마찬가지다.

예를 들어 dp[i][j]가 위쪽과 왼쪽에 의존하면:

  • 위에서 아래로
  • 왼쪽에서 오른쪽으로

채우면 된다.

즉, 점화식이 “누구를 참조하는지” 보면 계산 순서가 나온다.

B = Base case (베이스 케이스)

점화식만 있으면 무한히 내려간다.
그래서 시작점이 필요하다.

피보나치면:

  • dp[0] = 0
  • dp[1] = 1

계단 오르기면 문제 정의에 따라:

  • dp[0] = 1
  • dp[1] = 1

이런 식이다.

왜 base case가 중요하냐

점화식은 보통 이전 상태를 참조하는데,
맨 처음 상태들은 이전 상태가 없다.

그러면 직접 값을 박아줘야 한다.

이걸 안 하면:

  • 논리가 끊기거나
  • 인덱스 에러가 나거나
  • 점화식이 성립하지 않는다

base case 고를 때 주의

base case는 그냥 “작은 입력 몇 개”가 아니라,
relation이 정상 작동하도록 만드는 최소 시작 상태다.

예를 들어 dp[i] = dp[i-1] + dp[i-2] 라면 최소 두 개는 필요하다.

O = Original problem (원래 문제와 연결)

DP 배열을 다 만들었다고 끝이 아니다.
그래서 최종 답이 뭐냐? 를 확인해야 한다.

예를 들어:

  • 피보나치 수 n번째를 구하면 정답은 dp[n]
  • 0번에서 n번까지 가는 최소 비용이면 정답은 dp[n]
  • 하지만 LIS(최장 증가 부분 수열) 같은 건 정답이 dp[n]이 아닐 수도 있다

예를 들어 LIS에서
dp[i] = i에서 끝나는 LIS 길이
라면 전체 답은
max(dp[0], dp[1], ..., dp[n-1])
이다.

즉, subproblem은 중간 상태를 나타낼 뿐이고,
원래 문제가 원하는 답이 정확히 어느 상태인지 확인해야 한다.

T = Time (시간 분석)

마지막으로 시간 복잡도를 봐야 한다.

DP 시간 분석은 보통 되게 단순하다:

총 상태 수 × 상태 하나 계산하는 비용

이 공식으로 거의 끝난다.

예시 1: 피보나치

  • 상태 수: n
  • 상태 하나 계산 비용: O(1)

그래서 총 시간: O(n)

예시 2: LIS 기본 DP

  • 상태 수: n
  • 각 상태에서 이전 모든 j를 봄: O(n)

그래서 총 시간: O(n^2)

예시 3: 2차원 배낭

  • 상태 수: n * W
  • 상태 하나 계산 비용: O(1)

그래서 총 시간: O(nW)

공간 복잡도도 같이 보자

보통

  • 배열 전체 저장: O(number of states)
  • 이전 값 몇 개만 필요하면 압축 가능

예를 들어 피보나치는 사실 dp[i-1], dp[i-2]만 필요하니까 O(1) 공간으로도 가능하다.

3. 메모이제이션

메모이제이션은
한 번 계산한 값을 저장해두고, 다시 계산하지 않는 것이다.

보통 DP 구현 방식은 2개다.

1) Top-down + Memoization

재귀로 푼다.
필요한 문제를 호출해 내려가고,
이미 계산한 건 저장해두고 재사용한다.

피보나치 예시:

memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

장점

  • 문제 정의를 그대로 코드로 옮기기 쉬움
  • 재귀적 사고와 잘 맞음

단점

  • 재귀 호출 오버헤드가 있음
  • 깊이가 깊으면 스택 문제 생길 수 있음

2) Bottom-up (Tabulation)

작은 문제부터 직접 차례대로 채워나간다.

def fib(n):
    if n == 0:
        return 0
    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]

장점

  • 반복문이라 안정적
  • 계산 순서가 명확함

단점

  • subproblem 구조를 코드로 바로 옮기기엔 top-down보다 덜 직관적일 수 있음

4. 왜 DP가 필요한가

DP가 필요한 상황은 보통 두 가지 특징이 있다.

1) Overlapping subproblems

같은 하위 문제가 여러 번 반복된다.

예:

  • fib(5)를 재귀로 풀면 fib(3) 같은 게 여러 번 호출됨

2) Optimal substructure

큰 문제의 최적해가 작은 문제의 최적해로부터 만들어진다.

예:

  • 최소 비용 경로 문제에서 어떤 칸까지 오는 최소 비용은 이전 칸들까지의 최소 비용으로부터 결정된다

이 두 개가 있어야 DP 냄새가 난다.

5. 예시로 SRTBOT 전체 적용해보기

예제: 계단 오르기

한 번에 1칸 또는 2칸 올라갈 수 있을 때, n칸에 도달하는 방법 수를 구하라.

S: Subproblem

dp[i] = i칸에 도달하는 방법 수

R: Relation

마지막 이동 기준으로 보면:

  • i-1에서 1칸 올라옴
  • i-2에서 2칸 올라옴

그래서
dp[i] = dp[i-1] + dp[i-2]

T: Topological order

dp[0], dp[1], dp[2], ... 순서로 계산

B: Base case

  • dp[0] = 1
  • dp[1] = 1

O: Original problem

정답은 dp[n]

T: Time

  • 상태 수: n개
  • 각 상태 계산: O(1)

총 시간 O(n), 공간 O(n)

6. DP를 볼 때 머릿속에서 돌려야 할 질문

문제 보면 이렇게 생각하면 된다.

  1. 상태를 뭐로 둘까?

    • dp[i]?
    • dp[i][j]?
    • dp[i][j][k]?

  2. 마지막 선택은 뭐지?

    • 마지막에 어디서 왔지?
    • 마지막에 뭘 골랐지?

  3. 점화식은 어떻게 되지?

    • 이전 상태 몇 개를 보면 현재가 결정되나?

  4. 시작점은 뭐지?

    • base case는 뭘 넣어야 하지?

  5. 어떤 순서로 채워야 하지?

    • 작은 것부터?
    • 왼쪽에서 오른쪽?
    • 길이 짧은 구간부터?

  6. 최종 답은 어디 있지?

    • dp[n]?
    • max(dp)?
    • dp[0][n-1]?

이 순서가 거의 SRTBOT이랑 같다.

7. 한 문장씩 다시 번역하면

  • DP = Local brute force
    → 전체를 무식하게 탐색하지 말고, 작은 하위 문제 안에서 가능한 선택만 비교해라
  • Subproblem
    → 문제를 어떤 상태로 쪼갤지 정해라
  • Relation
    → 현재 상태가 이전 상태들과 어떻게 연결되는지 점화식을 세워라
  • Topological order
    → 필요한 하위 문제부터 먼저 계산하는 순서를 정해라
  • Base case
    → 가장 작은 문제의 답을 직접 정해라
  • Original problem
    → DP 배열 중 어디가 진짜 최종 답인지 확인해라
  • Time
    → 상태 수 × 상태당 계산 비용으로 시간 복잡도를 분석해라
  • 메모이제이션
    → 이미 푼 하위 문제를 저장해서 중복 계산을 없애라

Greedy 정리

Greedy란

Greedy는 매 순간 가장 좋아 보이는 선택을 하면서 답을 만들어 가는 방식이다.

최소 신장 트리

  • 최소의 간선을 사용해서 모든 정점을 연결한 그래프이다.
  • 모든 정점을 연결하면서 가중치 합이 최소가 되는 구조를 찾는다.
  • 최소 신장 트리는 사이클이 없는 트리 형태가 된다.

크루스칼 알고리즘

  • 간선의 가중치가 작은 것부터 선택한다.
  • 사이클이 생기지 않는 간선만 추가한다.
  • 이렇게 간선의 가중치 합을 가장 적은 비용으로 만든 최소 신장 트리를 구한다.

Union Find

  • 크루스칼 알고리즘에서 사이클을 판단할 때 사용하는 기법이다.
  • 두 정점이 같은 집합에 있으면 해당 간선을 추가했을 때 사이클이 생길 수 있다.

정리 메모

  • Greedy는 항상 현재 시점의 최선의 선택을 한다.
  • 이 방식이 항상 정답이 되지는 않기 때문에, 문제에 Greedy 성질이 있는지 먼저 확인해야 한다.

이번주 회고

작성 예정

profile
정범진
이전 포스트

WIL WEEK4

다음 포스트

WIL WEEK6

1개의 댓글

comment-user-thumbnail
김동현
2026년 4월 2일

이거 은근 시험에서 많이 틀린다 임마.

답글 달기