[멀티캠퍼스] 풀스택 개발자 아카데미 (16) - Algorithm(5)

0. 동적 프로그래밍

이전 글까지 4편에 걸쳐 기본기부터 브루트 포스, 정렬, 그리고 탐욕 알고리즘까지, 다양한 문제해결 방법을 알아봤다.

오늘은 그 정점에 있는, 복잡한 문제들을 우아하고 효율적으로 해결하는 궁극의 패러다임, **동적 프로그래밍(Dynamic Programming, DP)**에 대해 알아본다.

4편에서 우리는 '매 순간의 최선'을 선택하는 탐욕 알고리즘이 때로는 최적의 해를 놓칠 수 있다는 한계를 확인했다. 동적 프로그래밍은 바로 이 지점에서 출발한다. 모든 가능한 선택지를 고려하되, 어리석게 모든 계산을 반복하지 않고 '기억(메모)'을 통해 효율을 극대화하는 현명한 전략이다.

동적 프로그래밍은 복잡한 문제를 여러 개의 **작은 부분 문제(Subproblem)**로 나누어 푼다는 점에서 분할 정복과 유사하다. 하지만 결정적인 차이는 부분 문제들이 서로 중복되는지 여부이다.

분할 정복의 부분 문제들은 서로 독립적이지만, DP의 부분 문제들은 여러 번 반복해서 재사용된다.

DP는 이 중복되는 부분 문제들의 계산 결과를 한 번만 구하고, 그 결과를 자료구조(주로 배열이나 해시 테이블)에 저장해 두었다가 나중에 필요할 때 다시 꺼내 쓰는 방식을 사용한다. 이를 통해 지수적으로 늘어날 수 있는 계산량을 획기적으로 줄일 수 있다.

DP를 적용하기 위해서는 문제가 다음 두 가지 핵심 속성을 만족해야 한다.

• 중복되는 부분 문제 (Overlapping Subproblems): 큰 문제의 해답을 구하는 과정에서, 동일한 작은 문제의 해답이 반복적으로 필요해야 한다.

  • 예를 들어 '피보나치 수열'에서 fib(5)를 구하려면 fib(4)와 fib(3)이 필요하고, fib(4)를 구하려면 또 fib(3)과 fib(2)가 필요한 것처럼, fib(3)이 여러 번 호출되는 구조를 가져야 한다.
• 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적 해가, 그 문제의 작은 부분 문제들의 최적 해를 이용해 구성될 수 있어야 한다. 즉, 부분 문제들의 최적 해를 올바르게 조합하면 전체 문제의 최적 해를 얻을 수 있다는 믿음이 전제되어야 한다.

1. DP의 두 가지 접근법

1.1. 메모이제이션 (Memoization): Top-Down 방식

메모이제이션은 우리가 일반적으로 생각하는 재귀 호출에 '기록'이라는 개념을 더한 것이다.

큰 문제에서 출발하여 작은 문제로 내려가면서(Top-Down) 답을 구한다.

1.1.1. 해결 과정

1. 문제를 재귀적으로 호출하며 해를 구한다.
2. 특정 부분 문제의 해를 처음 구했다면, 그 결과를 memo라는 배열이나 맵에 저장한다.
3. 다음에 같은 부분 문제를 만나면, 다시 계산하지 않고 memo에 저장된 값을 즉시 반환한다.

1.1.2. 장단점

• 장점: 재귀적인 구조를 그대로 코드로 옮길 수 있어 더 직관적이다. 또한, 필요한 부분 문제만 계산하므로 타뷸레이션에 비해 불필요한 계산을 줄일 수 있다.
• 단점: 재귀 호출의 깊이가 너무 깊어지면 **스택 오버플로우(Stack Overflow)**가 발생할 수 있다.

1.2. 타뷸레이션 (Tabulation): Bottom-Up 방식

타뷸레이션은 재귀 대신 반복문을 사용하여 가장 작은 부분 문제부터 차례대로 해를 구해나가는 방식이다. 마치 표(Table)를 아래에서부터 위로 채워나가는(Bottom-Up) 모습과 같다.

1.2.1. 해결 과정

1. 부분 문제들의 결과를 저장할 dp라는 이름의 배열(Table)을 만든다.
2. 가장 작은, 즉 초기값이 명확한 부분 문제부터 dp 배열을 채워나간다.
3. 반복문을 통해 점화식(Recurrence Relation)을 기반으로 dp 배열을 끝까지 채웁니다. 최종적으로 dp 배열의 마지막 부분이 우리가 원하는 해가 된다.

1.2.2. 장단점

• 장점: 단순 반복문으로 구현되므로 재귀로 인한 오버헤드가 없고 스택 오버플로우의 위험이 없다.
• 단점: 문제에 따라 반복문의 순서(dp 테이블을 채워나가는 순서)를 정하는 것이 까다로울 수 있다. 때로는 최종 답을 위해 필요 없는 부분 문제까지 모두 계산해야 할 수 있다.

2. 예제

2.1. 대표 예제 1

피보나치 수열피보나치 수열은 DP의 두 가지 속성을 가장 잘 보여주는 교과서적인 예제다.

• 순진한 재귀 접근 (O(2ⁿ)): fib(5)를 구하기 위해 fib(4)와 fib(3)을 호출하고, fib(4)는 다시 fib(3)과 fib(2)를 호출합니다. fib(3)이 중복 호출되면서 엄청난 비효율이 발생합니다.

• 메모이제이션 (Top-Down) 접근 (O(n)):

int[] memo = new int[n+1]; // 결과를 저장할 배열

public int fib_memo(int n) {
    if (n <= 1) {
        return n;
    }

    if (memo[n] != 0)  {
        return memo[n]; // 이미 계산한 값이면 즉시 반환
    }

    // 계산하고 결과 저장
    return memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
}

• 타뷸레이션 (Bottom-Up) 접근 (O(n)):

public int fib_tab(int n) {
    if (n <= 1) {
        return n;
    }

    int[] dp = new int[n + 1];

    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2]; // 아래부터 테이블 채우기
    }

    return dp[n];
}

2.1.1. 타뷸레이션의 최적화

타뷸레이션 접근을 살펴보면, dp[i]는 dp[i-1]과 dp[i-2]만을 필요로 하고 있다. 그렇다면, 굳이 전체 배열을 다 저장할 필요가 없을 거라는 생각을 가져볼 수 있다.

• 공간 복잡도 최적화

public int fib_optimized(int n) {
    if (n <= 1) {
        return n;
    }

    // n-2, n-1 번째 값을 저장할 변수 초기화
    int prev2 = 0; // F(0)
    int prev1 = 1; // F(1)
    int current = 0;

    // 2부터 n까지 반복하며 이전 두 항의 합을 구해 현재 항을 갱신
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;     // 다음 반복을 위해 한 칸씩 이동
        prev1 = current;   // 다음 반복을 위해 한 칸씩 이동
    }

    return current;
}

2.2. 대표 예제 2

• DP 상태 정의: dp[i] = i번째 원소로 반드시 끝나는 연속 부분 수열의 최대 합.

• 점화식 도출: i번째에서 끝나는 최대 합은 두 가지 경우밖에 없다.

  • i번째 원소 혼자서 새로운 연속 부분 수열을 시작한다. (값: arr[i])
  • i-1번째에서 끝나는 최대 합에 i번째 원소를 이어 붙인다. (값: dp[i-1] + arr[i] 따라서, 점화식은 dp[i] = max(arr[i], dp[i-1] + arr[i]) 가 된다.
• 논리적 과정 (타뷸레이션): dp 배열을 채우면서, 동시에 전체 최대 합 maxSum을 갱신한다.

• Java 코드 예시:

public int maxSubArray(int[] arr) {
    if (arr == null || arr.length == 0) return 0;
    int[] dp = new int[arr.length];
    dp[0] = arr[0];
    int maxSum = dp[0];

    for (int i = 1; i < arr.length; i++) {
        dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

3. 마치며

지난 다섯 편의 글을 통해 다양한 알고리즘을 알아보았다.

1편의 자료구조라는 기본 도구를 챙기고, 2편에서는 브루트 포스와 DFS/BFS로 모든 길을 탐색하는 법을 배웠다. 3편에서는 정렬과 분할 정복으로 문제의 스케일을 다루는 법을, 4편에서는 탐욕 알고리즘으로 최적값을 찾는 법을 알아보았다.

그리고 오늘, 동적 프로그래밍이라는 가장 정교한 전략으로 마무리했다. 이 패러다임들은 단순히 코딩 테스트를 통과하기 위한 지식이 아니다. 이것들은 복잡하고 추상적인 현실의 문제를 논리적인 단계로 분해하고, 가장 효율적인 해결책을 설계하는 SW 엔지니어의 언어로 볼 수 있다.

어떤 문제를 만났을 때 "이건 DP로 풀 수 있겠다" 또는 "이건 Greedy가 통하겠는데?"라고 생각할 수 있는 능력이야말로, 단순히 코드를 작성하는 Coder를 넘어 문제를 해결하는 Problem Solver로 거듭나는 열쇠이다.