[코딩테스트 필승 공략] 입사 시험에 무조건 나오는 동적 계획법(DP) 핵심 유형 5가지 완벽 정리

안녕하세요! 오늘은 저처럼 이직을 준비하거나 코딩 테스트(이하 코테)라는 거대한 산 앞에 서 계신 분들을 위해, 가장 까다롭지만 절대 피할 수 없는 주제인 '동적 계획법(Dynamic Programming, DP)'에 대해 이야기해보려 합니다.
 
사실 저도 12년 차 개발자이지만, 실무에서 PHP로 백엔드를 구축하고 최근 Java로 넘어오면서 가장 힘들었던 부분이 바로 이 '알고리즘'이었습니다. 실무 경험이 아무리 많아도, 코딩 테스트에서 만나는 DP 문제는 마치 외계어를 해석하는 기분이었거든요. "아니, 그냥 반복문 돌리면 되는 거 아니야?" 하다가 시간 초과(Time Limit Exceeded)를 맞고 좌절했던 경험, 다들 한 번쯤 있으시죠?
 
그래서 준비했습니다. 제가 공부하면서 "아, 이건 꼭 알아야 하는구나!"라고 무릎을 탁 쳤던 DP의 핵심 유형 5가지를 정리했습니다. 저와 함께 공부한다는 마음으로 편하게 읽어주세요.

도대체 DP가 뭔가요? (feat. 캐싱)

동적 계획법, 이름만 들으면 뭔가 엄청나게 역동적이고 거창해 보입니다. 하지만 백엔드 개발자인 우리에게 익숙한 용어로 바꾸면 '캐싱(Caching)'과 아주 비슷합니다.
 
DP의 핵심은 딱 한 문장입니다.

"한 번 구한 답은 기억해두고, 필요할 때 다시 꺼내 쓰자."
 
우리가 DB 부하를 줄이기 위해 Redis에 자주 조회되는 데이터를 캐싱하듯이, 알고리즘에서도 반복되는 연산의 결과를 배열(Array)이나 리스트에 저장해두는 것입니다. 이걸 멋진 말로 메모이제이션(Memoization) 또는 타뷸레이션(Tabulation)이라고 합니다.

• Top-down (Memoization): 큰 문제를 풀다가 작은 문제가 필요하면 그때 풉니다. (재귀 호출 + 캐싱)
• Bottom-up (Tabulation): 가장 작은 문제부터 차근차근 답을 채워 올라갑니다. (반복문)

코딩 테스트에서는 주로 Bottom-up 방식이 스택 오버플로우 위험도 없고 직관적이라 많이 쓰입니다. 자, 이제 본격적으로 유형을 파헤쳐 봅시다.

유형 ①: 1차원 배열 채우기 (기초 중의 기초)

가장 기본이 되는 유형입니다. 이전 단계의 결과가 다음 단계에 영향을 미치는 경우죠. 대표적으로 '계단 오르기'나 '타일 채우기' 문제가 있습니다.
 

상황

"당신은 계단을 오르고 있습니다. 한 번에 1계단 또는 2계단씩 오를 수 있습니다. N번째 계단까지 오르는 방법의 수는?"
 

공략법

이런 문제는 점화식(Recurrence Relation) 하나면 끝납니다.

3번째 계단에 오르려면? '1번째 계단에서 2칸 점프'하거나 '2번째 계단에서 1칸 점프'하는 경우밖에 없습니다.

즉, dp[i] = dp[i-1] + dp[i-2] 라는 피보나치수열과 동일한 공식이 나옵니다.

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

 
너무 쉽다고요? 하지만 이 기본 원리가 나중에 나올 복잡한 문제의 뼈대가 됩니다. "현재 상태는 바로 직전의 상태들로부터 결정된다"는 것을 꼭 기억하세요.

유형 ②: 격자(Grid)에서의 최소/최대 경로

이제 차원을 하나 늘려봅시다. 2차원 배열(N x M) 맵이 주어지고, 왼쪽 위(0,0)에서 오른쪽 아래(N-1, M-1)까지 이동하는데, 숫자의 합이 최소가 되게 하거나 경로의 개수를 구하는 문제입니다. 프로그래머스의 '등굣길'이나 '정수 삼각형'이 여기에 해당합니다.
 

상황

"로봇이 m x n 그리드 위에 있습니다. 로봇은 오직 오른쪽이나 아래쪽으로만 움직일 수 있습니다. 우측 하단까지 가는 최단 경로의 합을 구하세요."
 

공략법

이 문제의 핵심은 "특정 칸 (i, j)에 도달하는 방법은 (i-1, j)에서 내려오거나, (i, j-1)에서 오른쪽으로 오는 것 두 가지뿐"이라는 점입니다.
 

점화식은 보통 이렇게 됩니다.
dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])

 
실전 팁

이 유형에서 가장 주의할 점은 경계 처리(Boundary Condition)입니다. 첫 번째 행(Row)이나 첫 번째 열(Column)은 위쪽이나 왼쪽에서 오는 경우가 없으므로, 반복문 돌리기 전에 미리 초기화해줘야 ArrayIndexOutOfBoundsException을 피할 수 있습니다.

// 첫 행 초기화
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
// 첫 열 초기화
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

 
이 과정을 '전처리'라고 하는데, DP 문제 풀 때 실수를 가장 많이 줄여주는 습관입니다.

유형 ③: 배낭 문제 (Knapsack Problem) - DP의 꽃

DP를 공부하다가 첫 번째 고비가 오는 곳이 바로 이 '배낭 문제'입니다. 하지만 이 패턴만 익히면 중급 난이도의 문제 절반은 풀 수 있습니다.
 

상황

"도둑이 보석상에 들어왔습니다. 배낭에는 최대 K무게까지만 담을 수 있습니다. 각 보석은 무게(W)와 가격(V)을 가집니다. 배낭에 담을 수 있는 보석 가치의 최댓값은?"
 

공략법

처음엔 "가성비(가격/무게) 순으로 정렬해서 담으면 되지 않나?"라고 생각하기 쉽습니다(이건 그리디 알고리즘). 하지만 보석을 쪼갤 수 없는 0/1 배낭 문제에서는 그게 통하지 않습니다.
 

여기서는 2차원 배열 dp[i][w]를 사용합니다.

• i: i번째 보석까지 고려했을 때
• w: 현재 배낭의 임시 용량이 w일 때

점화식은 다음과 같습니다.

1. 현재 보석이 배낭 용량보다 무거우면: 못 넣습니다. 이전 단계 값을 그대로 가져옵니다.
   dp[i][w] = dp[i-1][w]
2. 넣을 수 있다면: 넣는 경우와 안 넣는 경우 중 더 큰 가치를 선택합니다.
   dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight] + value)

이 로직은 단순히 가방 채우기뿐만 아니라, ‘제한된 자원 내에서 효율을 극대화하는’ 모든 문제에 응용됩니다. 예산 내에서 프로젝트 선정하기, 제한 시간 내에 점수 많이 얻기 등이 모두 배낭 문제입니다.

유형 ④: 최장 증가 수열 (LIS, Longest Increasing Subsequence)

수열 내부에서 순서를 유지하면서 가장 길게 증가하는 부분 수열을 찾는 문제입니다. 예를 들어 [10, 20, 10, 30, 20, 50]이 있다면 LIS는 [10, 20, 30, 50]으로 길이는 4가 됩니다.

 

공략법 (O(N^2) 방식)

이중 반복문을 사용합니다.

i번째 숫자를 끝으로 하는 LIS 길이를 구하려면, 0부터 i-1까지의 숫자들(j)을 훑어보면서 "나보다 작은 숫자들 중 가장 긴 LIS 길이 + 1"을 찾으면 됩니다.

for (int i = 0; i < n; i++) {
    dp[i] = 1; // 기본 길이는 자기 자신 1
    for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

 
최근 기업 코테에서는 N이 매우 클 때 O(N log N)으로 푸는 이분 탐색 방식을 요구하기도 하지만, DP의 기초를 묻는 문제에서는 이 O(N^2) 방식이 정석입니다. "앞의 상태를 보고 나를 갱신한다"는 DP 철학이 가장 잘 녹아있는 유형이죠.

유형 ⑤: 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

문자열 두 개가 주어졌을 때, 두 문자열에 공통으로 들어가는 가장 긴 부분 문자열을 찾는 문제입니다. ACAYKP와 CAPCAK의 LCS는 ACAK입니다.

 

상황

이건 도대체 어디에 쓸까요? 바로 우리가 매일 쓰는 Git의 Diff 기능, 표절 검사 프로그램, 생물정보학의 DNA 유사성 검사 등에 쓰입니다. 실무와 꽤 밀접하죠?
 

공략법

2차원 표를 그립니다. 행에는 문자열 A, 열에는 문자열 B를 둡니다. 문자를 하나씩 비교하면서 다음과 같이 채웁니다.

1. 글자가 같으면: 대각선 왼쪽 위 값에 +1을 합니다. (dp[i][j] = dp[i-1][j-1] + 1)
2. 글자가 다르면: 바로 왼쪽 값과 위쪽 값 중 더 큰 값을 가져옵니다. (Math.max(dp[i-1][j], dp[i][j-1]))

처음엔 표 그리는 게 귀찮지만, 직접 손으로 5x5 정도의 표를 그려보시면 "아! 이렇게 채워지는구나" 하고 감이 올 겁니다.

DP는 '점화식' 싸움입니다.

여기까지 읽으시느라 고생 많으셨습니다. 사실 이 5가지 유형만 완벽하게 이해하고 응용할 줄 알아도 코딩 테스트의 DP 문제는 두렵지 않습니다.
 
마지막으로 제가 공부하면서 깨달은 작은 팁 하나를 드리고 싶습니다.

"코드를 먼저 치지 마세요."
 

IDE를 켜고 class Solution부터 작성하면 뇌가 굳어버립니다. 대신 종이와 펜을 꺼내세요. 그리고 N=1일 때, N=2일 때, N=3일 때 값을 직접 구해보며 규칙성을 찾으세요. 규칙성(점화식)만 찾으면 코딩은 3분이면 끝납니다. 그게 바로 DP의 매력입니다.

 
저도 PHP에서 Java로 넘어오면서 수없이 많은 에러와 마주했지만, 결국 꾸준함이 답이더라고요. 이 글이 여러분의 코딩 테스트 준비에 작은 이정표가 되었으면 좋겠습니다.
 
혹시 이해가 안 가는 부분이나 추가로 다뤘으면 하는 주제가 있다면 댓글로 남겨주세요! 우리 같이 성장해봅시다. 여러분의 합격을 진심으로 응원합니다! 파이팅!
 

2025년 코딩테스트 정렬 알고리즘 총정리: 면접 합격까지 한번에 끝내기