동적 계획법(Dynamic Programming)

동적 계획법은 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식입니다.
메모리를 많이 사용하는 대신 빠른 성능을 자랑하고 두 가지 방법론이 있습니다.

• 메모이제이션(Memoization)
• 타뷸레이션(Tabulation)

메모이제이션

• 하향식 접근법
• 동적 계획법에서 작은 문제들의 결과는 항상 같다.
• 이 결과들을 메모리에 저장해 필요할때 꺼내 쓴다.
  이처럼 작은 문제로 큰 문제를 해결하기 위해서는 규칙이 존재해야 합니다.

대표적으로 피보나치 수열이 있습니다. 피보나치 수열의 가장 작은 문제는
fibonacci(1) = 1
fibonacci(2) = 1
이며 fibonacci(5)를 구해봅시다.

fibonacci(1) = 1
fibonacci(2) = fibonacci(1) + 0 = 1
fibonacci(3) = fibonacci(2) + fibonacci(1) = 2 => 기록
fibonacci(4) = fibonacci(3) + fibonacci(2) = 3 => 기록
fibonacci(5) = fibonacci(4) + fibonacci(3) = 5

타뷸레이션

• 상향식 접근법
• 필요한 값들을 미리 계산해둔다.
• 메모이제이션은 필요할 때 계산한다면(Lazy evaluation)
  타뷸레이션은 미리 계산해둔다(Earger evaluation)
• 보통 코딩 테스트에선 메모이제이션을 쓰는 경우가 대부분이다.

접근법

동적 계획법 유형은 키워드만으로 동적 계획법 문제임을 알기 어렵습니다.
그렇기때문에 문제 유형을 알 수 없다면 다음과 같은 절차를 진행합니다.

• 가장 작은 문제를 정의할 수 있는가?
• 작은 문제를 통해 큰 문제를 해결할 규칙이 있는가?

위 두가지가 가능하다면 동적 계획법 문제입니다.
간혹 메모리를 너무 사용하여 효율성 테스트에서 떨어지는 경우도 있기때문에 주의해야 합니다.