[코딩테스트, 더 이상 미룰 수 없다] BOJ 11053 - Dynamic Programming (DP)

 

알고리즘 문제를 풀다 보면,
단순한 완전탐색으로는 시간초과가 나는 경우를 자주 마주하게 된다.

이럴 때 사용하는 대표적인 방법이 바로 DP (Dynamic Programming)이다.

---

📌 1. DP란 무엇인가?

DP는 이미 계산한 결과를 저장해두고, 다시 사용하는 알고리즘이다.

즉,
“같은 계산을 여러 번 하지 않기 위해 결과를 저장하는 방식”이다.

---

✔️ DP가 적용되는 조건

DP는 아무 문제에나 쓸 수 있는 게 아니다.
아래 두 가지 조건을 만족해야 한다.

1. 중복되는 부분 문제 (Overlapping Subproblem)

• 같은 계산이 여러 번 반복됨

2. 최적 부분 구조 (Optimal Substructure)

• 작은 문제의 답으로 큰 문제를 해결할 수 있음

---

 2. DP 구현 방식: Top-Down vs Bottom-Up

DP는 크게 두 가지 방식으로 구현할 수 있다.

---

🔼 Top-Down (Memoization)

재귀를 사용하면서, 계산 결과를 저장하는 방식

d = [0] * 100

def fib(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fib(x-1) + fib(x-2)
    return d[x]

특징

• 직관적이다
• 구현이 간단하다
• 재귀 호출로 인해 스택 부담이 있음

---

🔽 Bottom-Up (Tabulation)

반복문을 사용해 작은 문제부터 차례대로 해결하는 방식

d = [0] * 100
d[1] = 1
d[2] = 1

for i in range(3, 100):
    d[i] = d[i-1] + d[i-2]

특징

• 반복문 기반이라 안정적
• 실행 속도가 빠름
• 실전에서 더 많이 사용됨

---

3. 왜 Bottom-Up이 더 많이 쓰일까?

실전 코딩 테스트에서는 대부분 Bottom-Up 방식이 선호된다.

그 이유는 다음과 같다.

---

1. 함수 호출 오버헤드 없음

재귀 호출이 없기 때문에 더 빠르게 동작한다.

2. 스택 오버플로우 위험 없음

깊은 재귀 호출로 인한 에러를 방지할 수 있다.

3. 디버깅이 쉽다

값이 순차적으로 쌓이기 때문에 흐름을 따라가기 쉽다.

---

👉 개략적인 결론

Top-Down은 직관적인 이해용, Bottom-Up은 성능 실전용

---

 4. DP 문제의 핵심: 점화식

DP 문제에서 가장 중요한 것은
바로 점화식(Transition)을 세우는 것이다.

---

✔️ DP 풀이 3단계

1. 상태 정의 (State)

dp[i]가 무엇을 의미하는지 정의

2. 점화식 (Transition)

이전 상태로부터 현재 상태를 만드는 규칙

 

3. 초기값 (Base Case)

시작값 설정

 

👉 이 3개만 정확히 세우면 DP는 거의 해결된다.

 

 5. 대표 DP 예제: LIS (최장 증가 부분 수열)

DP에서 가장 유명한 문제 중 하나가 바로 LIS이다.

---

✔️ 문제

수열이 주어졌을 때,
가장 긴 증가하는 부분 수열의 길이를 구하라.

예:

10 20 10 30 20 50

결과:

4  (10 → 20 → 30 → 50)

---

✔️ 핵심 아이디어

“나보다 앞에 있고, 나보다 작은 값들 중 가장 긴 것 뒤에 내가 붙는다.”

---

✔️ 상태 정의

dp[i] = i번째 원소를 마지막으로 하는 LIS의 길이

---

✔️ 점화식

dp[i] = max(dp[j] + 1)
(단, j < i 이고 A[j] < A[i])

---

✔️ 초기값

dp[i] = 1

(자기 자신만으로도 길이 1짜리 수열)

---

✔️ 코드

n = int(input())
a = list(map(int, input().split()))

dp = [1] * n

for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

---

 

마무리 정리

• DP는 저장 + 재사용
• 핵심은 점화식
• 구현은 Bottom-Up이 실전에서 더 많이 사용