다이나믹 프로그래밍(DP, 동적계획법) 알고리즘

다이나믹 프로그래밍은 동적계획법, DP라고도 한다.

 

메모리 공간을 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 대표적인 방법 중 하나다.

다이나믹 프로그래밍은 구현의 특별한 코드가 있다기 보다는, 두 가지 방식(탑다운, 바텀업)이 존재한다.

 

 

1. 다이나믹 프로그래밍 사용 문제

DP 알고리즘을 적용해 풀어야 하는 문제는 대표적으로 피보나치 수열을 예시로 들 수 있다.

 

피보나치 수열은 이전 두 항의 합을 현재의 항으로 다시 설정한다. 다시 말해, 점화식으로 문제를 풀어야 하는 것이다.

 

피보나치 수열은 손쉽게 재귀 문제로 풀 수 있는데, 이렇게 되면 주어진 숫자 n이 커질수록, 기하급수적으로 수행시간이 늘어나게 된다. 따라서 이러한 문제는 다이나믹 프로그래밍으로 해결해야 한다.

 

2. 다이나믹 프로그래밍 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위의 두 조건을 만족할 때, 다이나믹 프로그래밍 알고리즘을 사용해 문제를 풀 수 있다.

 

 

3. 메모이제이션

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류다.

 

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

 

메모이제이션 값을 저장하는 방법이므로 캐싱이라고도 한다.

실제로 메모이제이션을 구현하는 방법은 간단하다. 리스트에 저장하면 된다. (혹은 딕셔너리)

 

4. 탑다운 VS 바텀업

탑다운 : 위에서 아래로 내려가는 방식 (Ex. 재귀 함수) - 하향식
바텀업 : 아래에서 위로 올라가는 방식(Ex. 반복문) - 상향식

 

다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다.

바텀업 방식에서 사용되는 결과 저장용 리스트는 ‘DP 테이블’이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

 

5. 코딩테스트에서의 DP

대체로 간단한 형태로 출제된다.

 

DP 문제를 빠르게 풀기 위해서는 “이 문제는 DP 알고리즘으로 풀어야 한다!”까지의 사고로 빠르게 도달해야 한다.

 

특정한 문제를 완전탐색했을 때 시간이 너무 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분문제들의 중복 여부를 확인해볼 필요가 있다.

 

일단, 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면(메모이제이션을 사용할 수 있으면) 코드를 개선하는 방법도 있다. 다시 말해, 재귀함수 작성 → 메모이제이션 적용해 코드 수정의 과정으로 문제를 풀어보자.

 

가능하다면 재귀함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것이 좋다.

 

또, rescursion depth 오류가 발생한다면, sys 라이브러리의 setrecursionlimit()을 사용해보는 것도 방법이다.

 

 

6. 연관 문제

이제 다이나믹 프로그래밍에 대한 개념 학습은 끝났다. 바로 실제 문제를 풀어보자!

[백준]

• 설탕배달(2839) - https://www.acmicpc.net/problem/2839
• 파도반수열(9461) - https://www.acmicpc.net/problem/9461

[프로그래머스]

• 정수 삼각형 - https://school.programmers.co.kr/learn/courses/30/lessons/43105

[SWEA]

• 타일 붙이기(5255) - https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do
• 이항 계수(5256) - https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do