동적 계획법 (Dynamic Programming)

동적 계획법의 정의

- 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. (위키백과)

- 그리디 알고리즘은 최적해를 구해주지 않지만, 동적 계획법은 모든 방법을 일일히 검토하여 그 중 최적해를 찾아내는 방법이다.
- 분할정복은 동적계획법과 달리 부분문제를 한번만 쓰고 더 이상 쓰지 않기 때문에 메모이제이션이 필요하지 않다.

 

동적 계획법이란 이해하기 어려운 이름을 가지게 된 배경 (수학자 리처드 벨만의 자서전)

나는 RAND 코퍼레이션에서 1950년의 가을을 보냈다.
여기에서 내게 주어진 첫 과제는 다단계(multistage) 의사 결정 프로세스 (원래 이름) 에 대해 적절한 용어를 명명하는 것이었다.
'동적 계획법'이라는 이름이 어디에서 왔는지 궁금하지 않은가?
1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다.
우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다.
윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다.
사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다.
그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다.
그래서 내가 RAND 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다.
처음 올 때는 나는 위의 문제에 대해 '의사 결정 프로세스'라는 이름을 사용했지만,
여기에서 '프로세스(Process)'라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다.
그래서 나는 사람들이 알지 못하게 '계획법(Programming)'이라는 단어를 붙였다.
또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다.
이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고,
게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.

 

동적 계획법의 중요한 요소들

- 메모이제이션: 중복된 계산을 막기 위해 저장된 결과를 배열에 저장한 뒤, 다음에 계산이 필요할 때 저장된 값을 불러와서 중복을 없앤다.
- Top-down (재귀를 이용하여 마지막 값에서 처음 값으로 들어가는 방법) vs. bottom-up (for문을 이용해서 처음값부터 다음값을 계산해나가는 방법)

Recursive dynamic programming (재귀적 동적 계획법) vs. iterative dynamic programming (반복적 동적 계획법)

- 이미 계산한 것을 다시 계산하지 않기 위해 계산한 것과 계산하지 않은 것의 차이가 있어야한다. 계산된 값이 0일 수 있는 경우에는 보통 -1 또는 int_max (무한대) 값을 사용한다.

 

출처: https://coding-all.tistory.com/2

 

동적 계획법 문제 - 백준 2579 계단 오르기

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

 

각 계단에 쓰여 있는 점수가 주어질 때

이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

★★★ 동적 계획법을 이해할 때 해답을 보지 않고 직접 점화식을 세우는 것이 큰 도움이 되었다!!!

 

백준 2579 문제 내 풀이

 

동적 계획법 문제 - 백준 17069 파이프 옮기기

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

백준 17069 문제 내 풀이

동적 계획법과 관련된 다른 알고리즘

- 최장 공통 부분 수열
- 벨만-포드 알고리즘
- 플로이드-워셜 알고리즘
- 다익스트라 알고리즘
- 부분집합 합 알고리즘
- 배낭 문제
…

 

동일한 내용 ppt 정리

위의 문제를 풀면서 작은 문제의 해답이 큰 문제의 해답이 되어가는 과정을 만들 수 있었다.

Dynamic Programming 정리.pptx

0.15MB