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

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

한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법

 

 

동적 계획법 알고리즘 핵심 이론

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.

 

2. 작은 문제들이 반복돼 나타나고 사용되며, 이 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일해야 한다.

[ 피보나치 수열 예시 ]

피보나치 수열 공식 : D[N] = D[N - 1] + D[N - 2]

 

3. 메모이제이션(Memoization) 기법

  : 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

⇒ 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있다.

 

[ 피보나치 수열 예시 ]

 

[ 피보나치 수열 예시 ]

메모이제이션으로 5번째 피보나치 수열의 수 구하기

 

4. 동적 계획법은 톱-다운(top-down) 방식과 바텀-업(bottom-up) 방식으로 구현할 수 있다. 

 

• 톱-다운 구현 방식

• 큰 문제를 해결하기 위해 작은 문제를 호출한다.
• 주로 재귀 함수를 이용하여 소스코드 작성
• 하향식

 

+ 코드의 가독성이 좋고, 이해하기 편함

- 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있음

 

[ 피보나치 수열 예시 ]

int fibo(int n)
{
  // 이미 계산한 적이 있는 문제라면 그대로 반환
  if(D[n] != -1)
  {
    return D[n];
  }
  // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
  return D[n] = fibo(n - 2) + fibo(n - 1);
}

 

• 바텀-업 구현 방식

• 작은 문제부터 차근차근 답은 도출한다.
• 주로 반복문을 이용하여 소스코드 작성
• 상향식
• DP 테이블 : 결과 저장용 리스트

 

[ 피보나치 수열 예시 ]

for(int i = 2; i <= N; i++)
{
  D[i] = D[i - 1] + D[i - 2];
}

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.