Post

⚡ 알고리즘 - 동적 계획법(Dynamic Programming)

⚡ 알고리즘 - 동적 계획법(Dynamic Programming)

🔹 동적 계획법이란?

▫️ 개념

  • 큰 문제를 여러 개의 작은 문제로 나눠서 푸는 방식
  • 동일한 하위 문제가 반복되는 경우, 그 결과를 저장해 중복 계산을 피함
  • 하향식(메모이제이션) 또는 상향식(반복문) 방식으로 구현

▫️ 특징

  • 중복되는 하위 문제(Overlapping Subproblems)
  • 최적 부분 구조(Optimal Substructure)
  • 재귀 호출 또는 반복문 기반으로 해결 가능

🔹 DP 구현 방식

하향식 (Top-Down)

  • 재귀 호출을 사용하며, 이미 계산한 결과는 배열 등에 저장
  • 메모이제이션이라고도 부름
1
2
3
4
5
6
7
8
int[] memo = new int[100];

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    
    return memo[n] = fib(n - 1) + fib(n - 2);
}

상향식 (Bottom-Up)

  • 작은 문제부터 차례대로 값을 구해 나가며 테이블을 채워감
1
2
3
4
5
6
7
8
9
int fib(int 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];
}

🔹 대표 문제 유형

▫️ 피보나치 수열

  • 기본적인 DP 예제
  • n번째 수는 n-1, n-2번째 수의 합

▫️ 0-1 배낭 문제

  • 무게 제한이 있는 가방에 최대 가치를 넣는 문제
  • 물건을 담거나 담지 않는 두 선택 사이에서 최적 해 선택

▫️ 최장 공통 부분 수열(LCS)

  • 두 문자열에서 순서를 유지한 채 가장 긴 공통 부분 문자열의 길이 구하기

▫️ 최소 편집 거리

  • 한 문자열을 다른 문자열로 바꾸는 최소 연산 횟수 구하기
  • 삽입, 삭제, 교체 연산이 사용됨

🔹 DP와 그리디의 차이

  • 그리디는 각 단계에서 최선만 선택
  • DP는 모든 경우를 고려하고 저장하면서 최적 해를 도출
  • 같은 문제라도 조건에 따라 적절한 방법을 선택해야함

🔹 마무리

  • 동적 계획법은 중복되는 하위 문제와 최적 부분 구조가 있는 경우 매우 강력한 알고리즘
  • 효율적인 시간 복잡도를 갖고, 많은 면접 문제에 출제되므로 다양한 유형을 연습하는 것이 중요하다
This post is licensed under CC BY 4.0 by the author.