[CS지식] 동적 계획법(Dynamic Programming)

복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법

흔히 말하는 DP가 바로 ‘동적 계획법’ → 한가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘

즉, 똑같은 연산을 반복하지 않도록 만들어줌.

실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이라고 할 수 있다.

동적 계획법은 Optimal Substructure에서 효과를 발휘한다.

→ Optimal Substructure : 답을 구하기 위해 이미 했던 똑같은 계산을 계속 반복하는 문제 구조

접근 방식

커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하다. 하지만 간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점이 존재한다.

즉, 동적 계획법은 간단한 작은 문제들 속에서 ‘계속 반복되는 연산’을 활용하여 빠르게 풀수 있는 것이 핵심이다.

조건

• 작은 문제에서 반복이 일어남
• 같은 문제는 항ㅇ상 정답이 같음

이 두 가지 조건이 충족한다면, 동적 계획법을 이용하여 문제를 풀 수 있다.

쓰는이유

일반적인 재귀 방식 또한 DP와 매우 유사하다. 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다.

예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다.1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  144 ...

피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 어떻게 될까? 단순하다.

return f(n) = f(n-1) + f(n-2)

그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가한다.(약 7해, #,###경 #,###조 ... 번 이상 함수 호출, 컴퓨터도 죽는다.)

그러나 한 번 작은 문제의 결과 값을 저장해두고 재사용한다면, 앞에서 계산된 값을 다시 반복할 필요가 없어 약 200회 내에 계산이 가능해진다.

매우 효율적으로 시간복잡도도 O(N^2) → O(N)으로 해결 할 수 있다.

구현 방식

• Bottom-up : 작은 문제부터 차근차근 구하는 방법

→ 해결이 용이하지만, 가독성은 떨어짐

• Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법(재귀 방식)

→ 가독성이 좋지만, 코드 작성이 힘듬

동적 계획법으로 문제를 풀 때는, 우선 작은 문제부터 해결해 나가보는 것이 좋다.

작은 문제들을 풀어나가다보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 점화식을 도출해내어 동적 계획법을 적용시키자.

 

 

면접질문

1. 복잡한 문제를 더 간단한 하위 문제로 한번만 풀고 데이터 구조를 사용해 문제를 해결하는 방법은 무엇인가요? → 동적 프로그래밍 : DP
2. 구현 방식에는 Bottom-up과 Top-dow 방식이 있습니다. 이 두 가지를 설명해주세요
3. →바텀업 방식은 작은 문제부터 차근차근 구하는 방법이고 탑다운 방식은 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법입니다. 동적 계획법으로 문제를 풀 때는 우선 작은 문제부터 해결해 나가보는 것이 좋습니다.