Skip to main content
동호의 블로그

다이나믹 프로그래밍(DP) 알고리즘 [심화]

•2 min•340 words

1. DP 알고리즘

  • DP 알고리즘은 재귀적인 구조(관계식)를 찾아 문제를 효율적으로 해결하는 알고리즘

  • 따라서, DP 알고리즘에 있어 중요한 것은 재귀적인 구조(관계식)를 찾는 것

  • 내가 생각한 DP 알고리즘이 타당한지 판단하는 법

    • DP 관계식이 타당한가?

      : DP 테이블의 정의에 대해 DP 관계식이 논리에 오류가 없어야 한다.

    • 초기값을 구할 수 있는가?

      : DP 테이블의 초기값을 구할 수 있어야 한다.

  • DP 알고리즘의 시간 복잡도 계산

    ⇒ DP 테이블의 크기 x 한 번 갱신하는 데 걸리는 연산

  • 예제) 백준 11048

2. DP 알고리즘을 구현하는 방법

  • 재귀적인 구조를 찾았다면, 찾은 구조에 알맞는 DP Table을 완성하면 된다.

  • DP Table을 완성하면 답을 구할 수 있으며, DP Table을 완성하는 방법은 크게 두 가지로 나뉜다.

    1. Bottom-Up 방식

      : 작은 부분부터 완성하는 방식으로, 보통 반복문을 이용하여 DP Table을 완성한다.

    2. Top-Down 방식

      : 큰 부분(구하고자 하는 값)을 기준으로 DP Table의 필요한 부분만 구하는 방식으로, 재귀함수를 이용한다.

  • Bottom-Up 방식과 Top-Down 방식 중에 뭐가 더 좋은가요?

    • 대부분의 문제는 두 가지 방식 모두 사용할 수 있으므로 선호하는 방식으로 풀면 된다.
    • DP Table 전체를 완성해야 하는 경우에는 Bottom-Up 방식의 풀이가 더 좋다.
    • DP Table의 일부만 완성해도 되는 경우에는 Top-Down 방식의 풀이가 더 좋을 수 있다.
    • Bottom-Up
      • 반복문을 이용하여 갱신하므로 초보자 입장에서 코드를 이해하기 쉽다.
      • DP Table의 값을 갱신하는 과정에서 접근하는 순서에 유의할 필요가 있다.
        (즉, 아직 갱신되지 않은 부분의 값을 사용하면 안 된다.)
    • Top-Down
      • 재귀함수 구현이 익숙하지 않다면, 코딩을 하는 데에 어려움이 있을 수 있다.
      • DP Table의 값은 재귀적인 과정을 거치며 필요한 부분만 접근하기 때문에 순서를 따로 고려할 필요는 없다.

3. DP 문제를 잘 풀려면 어떻게 해야 할까?

  • DP 문제가 어려운 이유

    • DP를 이용하여 문제를 해결하려면 문제의 재귀적인 구조(관계식)를 찾아야 하기 때문이다.

      (= 적절한 형태의 DP Table 구조를 설계하는 과정이 DP를 처음 배울 때는 쉽지 않음)

  • DP 문제를 푸는 실력 키우기

    • 문제를 DP로 해석하는 능력을 키워야 함.
    • 따라서, 다음과 같은 과정을 여러번 연습하는 것이 필요함.
      1. 문제에서 적절한 DP Table 구조를 설계
      2. DP 식을 정의하고 타당한지 판단
      3. DP 식의 초기값을 구할 수 있는지 판단
    • DP는 최적해를 구하는 알고리즘이므로 다음과 같은 경우에 많이 사용된다.
      • ~한 경우의 수``를 구하시오.
      • ~의 최소값``을 구하시오.
      • ~의 최대값``을 구하시오.