Skip to content

Latest commit

 

History

History
534 lines (385 loc) · 19.6 KB

Concepts_Lab.ko.md

File metadata and controls

534 lines (385 loc) · 19.6 KB

6주차 실습 — 동적 프로그래밍

레포지토리 안내 | English | 한국어

최종 수정일: 2026-11-18

학습 목표:

  1. 피보나치 문제를 통해 단순 재귀, 메모이제이션, 테이블화을 비교할 수 있다
  2. LCS의 2D DP 테이블을 구축하고 역추적으로 실제 부분 수열을 복원할 수 있다
  3. 0-1 배낭 문제를 DP로 구현하고 선택된 물건을 추적할 수 있다
  4. LCS 기반 diff가 실제 웹 애플리케이션에서 어떻게 활용되는지 경험할 수 있다

목차



1. 개요

1.1 실습 목표

  • 핵심 DP 패턴인 메모이제이션과 테이블화을 이해하고 구현한다.
  • LCS의 2D DP 테이블을 구축하고 역추적으로 실제 부분 수열을 복원한다.
  • 0-1 배낭 문제를 DP로 구현하고 역추적으로 선택된 물건을 추적한다.
  • LCS 기반 diff가 실제 웹 애플리케이션에서 어떻게 활용되는지 분석한다.

1.2 실습 구성

섹션 주제
A-1 피보나치 비교
A-2 LCS와 DP 테이블 시각화
A-3 0-1 배낭과 역추적
B-1 텍스트 Diff 뷰어

표 1. 실습 섹션별 주제

1.3 실행 환경

Type A의 코드는 표준 라이브러리만 사용하므로 외부 패키지가 필요 없고, B-1에만 Flask가 필요하다.



2. Type A: 알고리즘 구현

2.1 A-1: 피보나치 비교

피보나치 수를 계산하는 세 가지 접근법을 비교하고 DP가 중복 계산을 어떻게 제거하는지 관찰한다.

2.1.1 문제

목표: 같은 피보나치 수를 세 방식으로 계산하고 측정한 실행 시간을 비교한다.

피보나치 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   n >= 2일 때

단순 재귀가 느린 이유

graph TD
    f5["F(5)"] --> f4["F(4)"]
    f5 --> f3a["F(3)"]
    f4 --> f3b["F(3)"]
    f4 --> f2a["F(2)"]
    f3a --> f2b["F(2)"]
    f3a --> f1a["F(1)"]
    f3b --> f2c["F(2)"]
    f3b --> f1b["F(1)"]
    f2c --> f1c["F(1)"]
    f2c --> f0["F(0)"]
    f2a --> e1["..."]
    f2b --> e2["..."]
Loading

그림 1. 단순 재귀로 F(5)를 계산할 때의 호출 트리

중복 부분 문제가 나타난다. F(3)이 2번, F(2)가 3번 계산되며, F(n)의 총 호출 수는 O(2^n)이다.

2.1.2 세 가지 접근법

# 1. 단순 재귀: O(2^n) — 지수적으로 느림
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# 2. 메모이제이션 (하향식): O(n) — 결과를 캐시
def fib_memo(n, memo=None):
    if memo is None: 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]

# 3. 테이블화 (상향식): O(n) — 테이블을 반복적으로 채움
def fib_tab(n):
    if n <= 1: return 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]

2.1.3 성능 결과

  N   |    Naive     |     Memo       |  Tabulation
------+--------------+----------------+----------------
  10  |   0.000005s  |   0.000003s    |   0.000002s
  20  |   0.001200s  |   0.000004s    |   0.000002s
  30  |   0.150000s  |   0.000005s    |   0.000003s
  35  |   1.800000s  |   0.000005s    |   0.000003s
  40  |   too slow   |   0.000006s    |   0.000003s

측정값은 근삿값이며 실행 환경에 따라 달라질 수 있다.

핵심 비교:

접근법 시간 공간 방향
단순 재귀 $O(2^n)$ O(n) 스택 해당 없음
메모이제이션 O(n) O(n) 캐시 + 스택 하향식
테이블화 O(n) O(n) 테이블 상향식

표 2. 피보나치 세 접근법의 시간, 공간, 계산 방향 비교

메모이제이션은 재귀에 캐싱을 더한 것이고, 테이블화은 테이블을 반복적으로 채우는 것이다. 둘 다 중복 부분 문제를 제거하며, 테이블화은 재귀 오버헤드도 피한다.



2.2 A-2: LCS와 DP 테이블 시각화

2.2.1 문제

문제: 두 문자열의 최장 공통 부분 수열(longest common subsequence, LCS) 을 찾아라.

부분 수열은 순서는 유지하지만 반드시 연속할 필요는 없다.

X = "ABCBDAB"
Y = "BDCAB"

공통 부분 수열: "B", "AB", "BD", "BCB", "BCAB", ...
최장: "BCAB" (길이 4)

X: A B C B D A B
     ^ ^     ^ ^
Y: B D C A B
   ^   ^ ^ ^

그림 2. X와 Y의 공통 부분 수열과 LCS 문자의 위치 표시

점화식:

X[i] == Y[j]일 때:   dp[i][j] = dp[i-1][j-1] + 1   (일치!)
X[i] != Y[j]일 때:   dp[i][j] = max(dp[i-1][j], dp[i][j-1])

시간: O(m × n), 공간: O(m × n)

2.2.2 DP 테이블

X = "ABCBDAB",  Y = "BDCAB"

          ""   B    D    C    A    B
          0    1    2    3    4    5
    ----------------------------------
 "" 0 |   0    0    0    0    0    0
  A 1 |   0    0    0    0    1    1
  B 2 |   0   [1]  (1)   1    1    2
  C 3 |   0    1    1   [2]   2    2
  B 4 |   0    1    1   (2)   2    3
  D 5 |   0    1    2   (2)   2    3
  A 6 |   0    1    2    2   [3]   3
  B 7 |   0    1    2    2    3   [4]

  [n] = 일치 (대각선 이동, LCS에 포함)
  (n) = 역추적 경로

그림 3. X = ABCBDAB, Y = BDCAB의 LCS DP 테이블

LCS = BCAB (길이 4)

2.2.3 풀이 코드

def build_lcs_table(x, y):
    """
    LCS DP 테이블을 구축한다.

    dp[i][j] = X[0..i-1]과 Y[0..j-1]의 LCS 길이
    시간 복잡도: O(m * n)
    공간 복잡도: O(m * n)
    """
    m, n = len(x), len(y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp

def backtrack_lcs(dp, x, y):
    """
    DP 테이블을 역추적하여 실제 LCS 문자열을 복원한다.
    dp[m][n]에서 시작하여 dp[0][0]까지 추적한다.
    """
    lcs = []
    i, j = len(x), len(y)
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            lcs.append(x[i - 1])
            i -= 1; j -= 1          # 대각선
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1                   # 위
        else:
            j -= 1                   # 왼쪽
    return "".join(reversed(lcs))

2.2.4 역추적 시각화

dp[7][5] = 4에서 시작, dp[0][0]까지 추적:

  (7,5): X[7]='B' == Y[5]='B' -> 대각선 (일치: 'B')
  (6,4): X[6]='A' == Y[4]='A' -> 대각선 (일치: 'A')
  (5,3): X[5]='D' != Y[3]='C' -> 위  (dp[4][3]=2 >= dp[5][2]=2)
  (4,3): X[4]='B' != Y[3]='C' -> 위  (dp[3][3]=2 >= dp[4][2]=1)
  (3,3): X[3]='C' == Y[3]='C' -> 대각선 (일치: 'C')
  (2,2): X[2]='B' != Y[2]='D' -> 왼쪽 (dp[1][2]=0 < dp[2][1]=1)
  (2,1): X[2]='B' == Y[1]='B' -> 대각선 (일치: 'B')

수집 (역순): B -> C -> A -> B = "BCAB"

LCS의 응용:

  • git diff: 파일 버전을 줄 단위로 비교한다.
  • DNA 서열 정렬: 유전자 서열을 비교한다.
  • 편집 거리: 한 문자열을 다른 문자열로 변환하는 최소 편집 수를 구한다.


2.3 A-3: 0-1 배낭과 역추적

2.3.1 문제

문제: 용량을 초과하지 않으면서 가치를 최대화하도록 물건을 선택하라. 물건은 쪼갤 수 없으므로 통째로 담거나 남겨야 한다.

용량: 50

물건       가치    무게
--------------------------
Laptop      60      10
Camera     100      20
Painting   120      30
Book        40       5

점화식:

dp[i][j] = 처음 i개 물건으로 용량 j에서의 최대 가치

weight_i > j일 때:   dp[i][j] = dp[i-1][j]          (물건 i를 담을 수 없음)
그 외:               dp[i][j] = max(
                         dp[i-1][j],                  (물건 i 건너뛰기)
                         dp[i-1][j - weight_i] + v_i  (물건 i 담기)
                     )

어떤 물건을 골라야 하는가?

2.3.2 DP 테이블과 역추적

          용량 ->      0   5  10  15  20  25  30  35  40  45  50
          ---------------------------------------------------------
(없음)  0 |            0   0   0   0   0   0   0   0   0   0   0
Laptop  1 |            0   0  60  60  60  60  60  60  60  60  60
Camera  2 |            0   0  60  60 100 100 160 160 160 160 160
Paint.  3 |            0   0  60  60 100 100 160 160 180 180 220
Book    4 |            0  40  60 100 100 140 160 200 200 220 220

정답: dp[4][50] = 220

dp[4][50]부터 역추적:
  dp[4][50]=220 == dp[3][50]=220 -> Book 건너뛰기
  dp[3][50]=220 != dp[2][50]=160 -> Painting 담기 (j: 50->20)
  dp[2][20]=100 != dp[1][20]=60  -> Camera 담기   (j: 20->0)
  dp[1][0]=0 == dp[0][0]=0      -> Laptop 건너뛰기

선택: Camera (100, 20kg) + Painting (120, 30kg) = 220

그림 4. 용량 50인 0-1 배낭 예제의 DP 테이블과 역추적

참고: 또 다른 최적해. Laptop + Painting + Book(무게 45, 가치 220)도 같은 최대 가치를 내는 최적해이다. 2.3.3절의 코드는 dp[i][j] = dp[i-1][j]이면 물건을 건너뛰므로 Camera + Painting을 고른다.

2.3.3 풀이 코드

def knapsack_01(capacity, items):
    """
    DP로 0-1 배낭 문제를 해결한다.

    items: (가치, 무게, 이름)의 리스트
    Returns: 최대 가치, 선택된 물건 리스트

    시간 복잡도: O(n * W)
    공간 복잡도: O(n * W)   (W = 용량)
    """
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        v, w, _ = items[i - 1]
        for j in range(capacity + 1):
            dp[i][j] = dp[i - 1][j]           # 건너뛰기
            if w <= j and dp[i - 1][j - w] + v > dp[i][j]:
                dp[i][j] = dp[i - 1][j - w] + v  # 담기

    # 역추적으로 선택된 물건 찾기
    selected = []
    j = capacity
    for i in range(n, 0, -1):
        if dp[i][j] != dp[i - 1][j]:
            selected.append(items[i - 1])
            j -= items[i - 1][1]               # 무게 차감

    return dp[n][capacity], list(reversed(selected))

시간: O(n × W), 공간: O(n × W) (W는 용량)



3. Type B: 웹 코드 분석

3.1 B-1: 텍스트 Diff 뷰어

3.1.1 설정

먼저 pip install flask로 의존성을 설치한 뒤 Flask 앱을 실행한다.

두 텍스트를 입력하면 LCS를 기반으로 차이점을 강조 표시한다.

  텍스트 A: "The quick brown fox"
  텍스트 B: "The slow brown dog"

  Diff 출력:
    "The "
    [-quick-] [+slow+]
    " brown "
    [-fox-] [+dog+]

이것은 GitHub의 diff 기능과 같은 원리이다.

3.1.2 Diff 동작 원리

1. 텍스트를 토큰(단어 또는 줄)으로 분할
2. 두 토큰 시퀀스의 LCS를 계산
3. LCS에 있는 토큰     -> 변경 없음 (흰색)
   A에만 있는 토큰     -> 삭제됨   (빨강)
   B에만 있는 토큰     -> 삽입됨   (초록)

  텍스트 A 토큰: [The, quick, brown, fox]
  텍스트 B 토큰: [The, slow,  brown, dog]

  LCS: [The, brown]

  정렬:
    The    The      <- 동일 (LCS)
    quick  ---      <- 삭제됨
    ---    slow     <- 삽입됨
    brown  brown    <- 동일 (LCS)
    fox    ---      <- 삭제됨
    ---    dog      <- 삽입됨

그림 5. LCS 기반 diff의 처리 단계와 토큰 정렬

실험:

  • 단어 몇 개만 바꾼 짧은 문장을 입력해 결과를 확인한다.
  • 긴 문단을 입력하고 LCS가 공통 구조를 어떻게 포착하는지 관찰한다.
  • m, n이 토큰 수일 때 이 방법이 O(m × n)인 이유를 따져 본다.


4. DP 레시피

DP 알고리즘은 다음 다섯 단계로 설계한다.

1. 부분 문제 정의   — dp[i][j]가 무엇을 나타내는가?
2. 점화식 작성      — dp[i][j]가 더 작은 부분 문제와 어떻게 관련되는가?
3. 기저 사례 식별   — dp[0][...] = ?, dp[...][0] = ?
4. 채움 순서 결정   — 보통 왼쪽에서 오른쪽, 위에서 아래로
5. 필요시 역추적    — 값뿐 아니라 실제 해를 복원


요약

개념 핵심 요약
피보나치 단순 재귀는 $O(2^n)$이지만 메모이제이션과 테이블화은 중복 부분 문제를 제거하여 O(n)에 계산한다.
LCS 2D DP 테이블을 채운 뒤 역추적으로 실제 부분 수열을 복원한다.
0-1 배낭 DP 테이블을 구축하고 역추적으로 선택된 물건을 찾는다.
텍스트 Diff LCS를 실제 웹 애플리케이션에 적용한 것으로, GitHub diff와 같은 원리이다.
DP 레시피 부분 문제 정의, 점화식 작성, 기저 사례 식별, 채움 순서 결정, 필요할 때의 역추적 순서로 DP를 설계한다.


점검 문제

  1. 피보나치의 단순 재귀가 왜 $O(2^n)$의 시간 복잡도를 가지는가? F(5)의 재귀 트리를 그리고 F(2)가 몇 번 계산되는지 세어 보라.

    정답

    각 호출이 두 재귀 호출로 분기하고 재귀 깊이가 최대 $n$이므로 호출 트리의 노드 수는 대략 $2^n$ 이하이다. 다만 오른쪽 가지가 더 짧아 트리가 균형을 이루지 않으므로, 정확한 호출 수는 $\Theta(\phi^n)$($\phi \approx 1.618$)으로 늘어난다. 같은 부분 문제가 여러 가지에서 반복 계산되며, F(5)의 호출 트리는 F(5) → F(4), F(3); F(4) → F(3), F(2); 그리고 두 F(3) → F(2), F(1)로 펼쳐진다. 잎까지 모두 세면 F(2)는 3번 계산된다(F(1)은 5번, F(0)은 3번). $n$이 커질수록 중복 계산이 지수적으로 늘어나므로 전체 시간 복잡도는 $O(2^n)$이 된다.

  2. LCS 문제에서 역추적 단계의 역할은 무엇인가? 최종 값 dp[m][n]만으로는 왜 실제 부분 수열을 결정할 수 없는가?

    정답

    DP 테이블은 각 셀에서 LCS의 길이만 저장하고 어떤 문자들이 선택되었는지는 저장하지 않는다. 같은 길이를 만드는 부분 수열은 여러 개가 존재할 수 있으므로 dp[m][n] = 4는 LCS가 4글자임만 알려 줄 뿐 어떤 4글자인지는 알려 주지 않는다. 역추적은 dp[m][n]에서 dp[0][0]까지 거꾸로 걸어가며 각 셀의 결정을 되짚는다. 일치(X[i] == Y[j])하면 해당 문자를 출력하고 대각선으로 이동하며, 그렇지 않으면 더 큰 이웃 방향으로 이동한다. 각 단계가 $O(1)$이므로 복원에 $O(m+n)$만 추가된다.

  3. 0-1 배낭 예제에서 Book (가치 40, 무게 5)이 가장 높은 가치/무게 비율 (8.0/kg)을 가지고 있음에도 불구하고 왜 선택되지 않는가?

    정답

    0-1 배낭은 비율 우선 그리디로 풀리지 않는다. 물건을 쪼갤 수 없기 때문이다. 비율 순으로 담으면 Book(8.0/kg), Laptop(6.0/kg), Camera(5.0/kg)을 담아 무게 35에서 가치 200에 그치고, Painting은 더 들어가지 않는다. 반면 Camera (100, 20) + Painting (120, 30)은 정확히 50kg을 채우며 가치 220을 만든다. 같은 220을 내는 다른 최적해 Laptop + Painting + Book(무게 45)도 있으므로 Book이 최적해에 들어갈 수 없는 것은 아니다. 2.3.3절의 역추적은 dp[4][50] = dp[3][50] = 220이어서 Book 없이도 최댓값을 얻을 수 있음을 확인하고 Book을 건너뛴다. DP는 모든 부분집합 조합을 암묵적으로 비교하므로, 물건 조합의 결합 가치가 비율 우선 선택보다 크다는 것을 찾아낸다.

  4. 텍스트 diff 뷰어는 LCS를 어떻게 활용하는가? 이 접근법이 왜 O(m × n)인지, 텍스트가 매우 길 때 어떤 일이 발생하는지 설명하라.

    정답

    두 텍스트를 토큰(단어 또는 줄)으로 분할한 뒤, 토큰 시퀀스에 대한 LCS로 가장 긴 공통 정렬을 찾는다. LCS에 포함된 토큰은 변경 없음, A에만 있는 토큰은 삭제, B에만 있는 토큰은 삽입으로 표시된다. LCS 테이블의 각 셀이 $O(1)$로 채워지므로 전체는 $O(m \times n)$이다. 텍스트가 매우 길어지면 문제가 된다. 10,000줄 × 10,000줄 diff는 $10^8$개의 셀과 그만큼의 메모리가 필요하다. 실제 도구(git diff 등)는 Myers의 diff 알고리즘($O((m+n)D)$, $D$는 편집 거리)이나 Hunt-McIlroy 식 최적화를 사용해 실전 성능을 크게 끌어올린다.

  5. 메모이제이션과 테이블화을 비교하라: 각각 언제 선호하는가? 스택 깊이, 구현 용이성, 캐시 효율성을 고려하라.

    정답

    메모이제이션은 자연스러운 재귀 정의에 캐시 검사만 추가하면 되므로 구현이 쉽고, 실제로 도달하는 부분 문제만 풀기 때문에 상태 공간이 희소할 때 유리하다. 단점은 재귀 오버헤드와 스택 깊이 한계이다(Python 기본값은 약 1000 프레임이며, 깊은 DP 점화식은 sys.setrecursionlimit 없이는 한계를 넘는다). 테이블화은 의존성 순서로 반복 계산하여 재귀를 완전히 피한다. 상수 계수가 작고 캐시 지역성이 좋으며(순차적 메모리 접근) $O(1)$행으로 공간 최적화도 가능하다. 희소하게 사용되는 상태나 복잡한 점화식이면 메모이제이션을, 성능이 중요하고 거의 모든 상태가 필요하면 테이블화을 선호한다.

  6. DP 레시피에서 채움 순서가 왜 중요한가? LCS 테이블을 오른쪽 아래에서 왼쪽 위로 채우려고 하면 어떻게 되겠는가?

    정답

    채움 순서는 점화식의 의존성 방향을 따라야 한다. 모든 셀은 자신이 참조하는 입력이 이미 계산되어 있어야 한다. LCS 점화식은 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]을 읽으므로 왼쪽→오른쪽, 위→아래 순서가 이를 보장한다. 오른쪽 아래 → 왼쪽 위로 뒤집으면 아직 계산되지 않은 셀(초기값 0)을 읽어 잘못된 결과가 나온다. 반대 방향으로 가려면 dp[i][j]를 접미사 X[i..m]과 Y[j..n]의 LCS로 재정의하여 의존성을 뒤집어야 한다.