[Week5] WIL - DP 알고리즘 부수기

약 4주간 진행한 알고리즘 주차가 종료되었다. 이제 백준 기준으로 실버까지의 문제는 어느정도 풀어낼 수 있게 되었다. 하지만 이대로 C언어 주차로 넘어가게 되면 알고리즘 해결 감각이 다시 초기화될 것이 뻔히 보인다. 비록 알고리즘 주차는 끝났지만, 매일 혹은 이틀에 한번 정도는 알고리즘 문제를 꾸준히 푸는 습관을 들이도록 하겠다!

 

핵심 역량 평가

역량	달성도	목표
문제해결	80%	백준 골드5 수준의 문제를 AI, 구글링 도움 없이 풀 수 있음.
LCS 문제를 제외하고는 스스로 해결할 수 있었다.
설계	80%	최대한 효율적인 코드(시간 복잡도/공간 복잡도 고려)를 짜는 것을 목표로 한다.
최대한 시간 복잡도를 낮추는 방식으로 코드를 짜려고 노력했다. 또한 풀이법이 두가지가 있다면(1차원, 2차원 배열) 두 방법 모두 사용하여 문제를 풀어보았다.
구현	75%	문제당 실패 횟수를 3회 이하로 한다.
공간복잡도 및 시간복잡도를 고려하지 못한 경우를 제외하고 문제를 잘못 읽어서 틀린 경우는 거의 없었다.
품질	100%	수요코딩회에서 버그없이 돌아가는 결과물을 만든다.
의도한 동작들이 모두 버그없이 돌아가는 미니 리액트 프로젝트를 완성했다.
유지보수	80%	주석을 통해 명확한 풀이를 기록한다.
과정이 복잡한 내용은 주석을 통해 재학습이 편하도록 했다.
협업	80%	코어타임 뿐만 아니라 팀원들과 적극적인 교류를 한다.
코어타임이 끝나고도, 문제를 팀원 모두가 이해할 수 있도록 시간을 투자하여 동료학습을 꾸준하게 진행했다.
태도	90%	모르겠는 문제에 대해 절대 AI를 사용한 코드 생성을 하지 않는다.
최대한 개념 학습을 할 때만 도움을 받았고, 코드 생성은 최대한 하지 않으려고 노력했다.
AI 활용	80%	맞힌 문제라도 AI에 코드 리뷰를 맡겨 더 최적화된 방법이 있는지를 모색한다.
문제를 해결했어도, 더 좋은 방법이 있는지 AI에게 코드리뷰를 맡겨보았다.
학습 민첩성	90%	수요코딩회에서 리액트의 Component, State, Hooks에 대한 개념을 탑다운 방식으로 빠르게 학습한다.
빠르게 기존 결과물을 리팩토링하고, 각자 맡은 부분을 공부하여 코드를 설명해주는 시간을 통해 빠르게 학습할 수 있었다.

 

이번 주 핵심 개념 - DP(Dynamic Programming)

다양한 개념을 학습했던 이전 주차들과는 달리 이번주는 핵심 개념이 DP, 그리고 이로부터 파생된 그리디 알고리즘 두개 뿐이었다.

DP 알고리즘을 응용할 수 있는 문제들은 모두 점화식이 다르고, 풀이법이 고정된 느낌이 아니라 적응하는 과정이 매우 험난했다.

먼저 DP 알고리즘의 간단한 정의와 종류. 그리고 DP 문제 중 가장 어렵게 느껴졌던 LCS와 평범한 배낭 문제 풀이과정까지 정리해두려고 한다.

 

DP 정의

큰 문제를 작은 문제로 나눠서, 이미 계산한 결과를 재사용하는 방법이다.

문제를 풀다보면 같은 계산을 계속 반복하는 상황이 나온다.

f(5) = f(4) + f(3)
     = (f(3)+f(2)) + (f(2)+f(1))

-> f(3), f(2)가 계속 중복 계산 된다.

 

DP 문제는 크게 두 가지 템플릿을 가지고 있다.

 

1. 점화식형

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

다음과 같이 현재 값을 이전 값들로 정의하는 형식이다.

이런 문제들은 보통 3가지 단계를 거치면 해결할 수 있다.

 

1️⃣ 상태 정의 (dp 배열 의미 정하기)

dp[i] = i번째까지의 최적값

개인적으로 생각하는 가장 중요한 단계이다. dp[i]가 정확히 어떤것을 정의하는지를 인지하고 설계를 해야 문제를 풀 수 있다.

 

2️⃣ 점화식 세우기

dp[i] = 이전 값들로부터 계산

위에서 작성한 수식과 같이 dp[i]를 이전 값들로부터 계산할 수 있는 점화식을 세우는 단계이다. 문제마다 점화식이 다르기 때문에 다양한 문제를 풀어보면서 규칙을 찾는 연습을 하는 것이 중요하다.

 

3️⃣ 초기값 설정

dp[0], dp[1] 같은 값들 정의

base case를 정의하는 단계이다. 이 부분이 예외상황을 제대로 처리하지 못하면 점화식을 통해 정답을 도출할 수 없다.

 

2. 값 갱신형

dp[i]가 특정 규칙을 항상 만족하는 것이 아니라 점화식으로 정의하기 힘든 문제들을 풀이할때 사용하는 방법이다. 처음 접했을때 굉장히 당황스러운 개념이다.

값 갱신형 문제는 현재 상태를 하나 잡고 거기서 갈 수 있는 다음 상태들을 보면서 다음 상태 값을 업데이트 하는 방식이다. 이 때문에 BFS와 비슷하게 보이기도 한다.

 

예시 템플릿을 확인해보자.

# 최소값 갱신
dp[nxt] = min(dp[nxt], dp[cur] + cost)

# 최대값 갱신
dp[nxt] = max(dp[nxt], dp[cur] + value)

# 가능 여부 체크
if dp[cur]:
    dp[nxt] = True

 

실제로 백준 2253 '점프' 문제를 풀 때 값 갱신 형태로 dp[i]를 정의하였다.

https://www.acmicpc.net/problem/2253

# i + k 칸까지 k만큼 건너뛰어서 가는 경우
dp[i + k][k] = min(dp[i + k][k], dp[i][k] + 1)

 

결론

본질적으로는 둘 다 DP이다. 차이는 보는 방식 / 구현하는 방식의 차이에 가깝다. 작은 상태들의 답은 이용해서 큰 상태의 답을 구한다는 진리는 변하지 않는다.

 

Leetcode - Word Break

https://leetcode.com/problems/word-break/

Word Break - LeetCode

설계 부분에서 큰 어려움을 겪었던 문제이다. 코어 타임 때 손도 못대고 나왔는데, 나중에 까먹을때쯤 다시 풀어보자..^^

 

DP 유형 - Top-down과 Bottom-Up

간단한 예제인 피보나치 문제를 통해 Top-down과 Bottom-Up 방식에 대해 이해할 수 있었다.

 

1. DP(Top-down, Memoization)

dp = {}

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

 

큰 문제를 먼저 정의하고, 필요한 작은 문제들만 재귀적으로 계산하여 저장하는 방식이다. 

 

Top-down 장단점

장점

필요한 부분만 계산한다.

- fib(100)을 구할 때 fib(50)이 필요 없으면 아예 계산하지 않는다.

 

단점

재귀 호출 자체의 오버헤드와 콜 스택 문제가 있다.

- n이 매우 크면 스택 오버플로가 날 수 있고, 함수 호출마다 스택 프레임을 쌓기 때문에 bottom-up 보다 느린 경우가 많다.

 

2. DP(Bottom-Up)

def fib(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]

 

작은 문제를 해결하고, 그걸 이용해서 더 큰 문제를 해결하면 최종 답에 도달하는 방식이다.

- fib(0) = 0

- fib(1) = 1

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

...

 

핵심 특징

재귀 없이 반복문만 쓰기 때문에 stack overflow 위험이 없고, 함수 호출 오버헤드도 없어서 실제 실행 속도가 더 빠른 경우가 많다.

 

Bottom-Up 장단점

장점

속도와 안정성이 좋다.

- 반복문이라 최적화도 쉽다.

 

단점

풀 필요 없는 부분까지 다 채운다.

또한 부분 문제를 채우는 순서를 직접 파악해야하기 때문에, 점화식이 복잡하면 구현이 까다로울 수 있다.

 

❓왜 Top-down 방식만 Memoization이라는 용어를 사용할까?
메모이제이션은 "필요할 때 저장"하는 전략으로, 2가지 핵심을 가진다.
  1. 요청이 왔을 때 계산
  2. 결과를 저장해서 중복 계산 방지
Bottom-up도 결과를 저장해서 중복 계산을 방지하는 방식이지만, 요청과 무관하게 미리 전부 채워두는 방식이라 첫 번째 조건을 만족하지 못한다.

 

이 주의 문제 - LCS, 평범한배낭

DP알고리즘 위주의 문제를 풀다보니 설계 단계에서 많은 생각을 요구하는 문제가 많았다. 그 중 특히 재미있게 풀었던 두개의 문제에 대해 따로 정리를 해두었다.

 

2026.04.02 - [알고리즘] - 백준 9251- LCS

백준 9251- LCS

 

2026.04.02 - [알고리즘] - 백준 12865 - 평범한 배낭 풀이

백준 12865 - 평범한 배낭 풀이