[동적계획법 1일차] 다이나믹프로그래밍 기초 - 7문제

-

3-1 동적 계획법(다이나믹 프로그래밍)을 하기 위한 준비단계

  기본적으로 동적 계획법은 1차원 혹은 2차원 배열에 대한 이해를 바탕으로 하며, 배열을 이용해 동적 계획법을 다룰 것이다. 문제에 따라서는 3차원 이상의 복잡한 배열을 이용하기도 하므로, 배열에 대한 거부값 없이 자유로이 활용할 수 있는 실력을 기본적으로 갖추어야 한다.

  재귀호출에 대한 이해가 있다면 좀더 간결한 프로그램 소스코드를 작성할 수 있다. 물론 비재귀호출을 이용한 방법도 있지만 프로그램 소스코드를 작성할 때 좀 더 길어지거나 지저분해지는 경향이 있기 때문에 일부 프로그램 소스코드에 재귀호출을 이용하고 있다. 재귀호출을 이용하여 작성된 프로그램은 읽기가 수월하다는 장점도 있으니, 처음 공부를 할 때에는 이와 같은 소스코드를 이용하여 공부하는 것이 이해하기쉽다.

  동적 계획법은 대부분 배열을 이용해서 표를 작성하기 때문에 설명이 길어질 수도 있다. 차분히 읽어 내려가면서 표가 변화되는 과정을 눈여겨 보고 프로그램이 어떻게 진행되가는가를 머릿속으로 그려보기 바란다.

 

3-2 동적 계획법의 정의

  작은 문제들의 해를 먼저 구하여 저장하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것을 말한다. 즉, 큰 문제를 해결하기 위해 작은 부분 문제로 분할한 뒤 하나의 부분 문제에 대한 답을 구한다. 이후의 부분 문제애 댜한 답을구하기 위해서 이전에 구한 부분 문제의 답을 참조한다. 이러한 과정을 진행할 때 이전에 해결한 부분 문제를 참조해서 다음 부분 문제의 답을 구할 수 있다. 이처럼 작은 부분 문제들의 해를 먼저 구하여 저장하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것을 말한다.

  예를 들어 서울에서 부산까지 가장 빠르게 이동하는 방법을 찾는 경우를 생각해보자. 이때 중간에 대구를 들러서 이동해야 한다고 하자. 그렇다면 서울에서 대구 대구에서 부산까지 가장 빠르게 이동하는 방법을 찾는 부분문제로 원래의 문제를 나눌 수 있다. 이와 같이 서울에서 대구까지 가장 빠르게 이동하는 방법을 찾고, 대구에서 부산까지 가장 빠르게 이동하는 방법을 찾아서 이둘을 합쳐주면 서울에서 대구를 들러서 부산까지 가장 빠르게 이동하는 방법이 된다.

 

3-3 동적 계획법의 특징

  동적 계획법은 상향식(bottom-up)이다. 이 말은 하나의 작은 해에서 큰 해를 구해 나가는 방향이기 때문이다.

  동적 계획법 방법론을 개발하기 위해서 다음의 단계가 필요하다.

  (1) 주어진 문제의 해를 구하기 위한 순환적인 성질(recursive property)을 구성하여야 한다.

  (2) 상향식으로 작은 부분 문제부터 해를 구해여야 한다.

  이 두 가지를 구성하였다면 효율적인 프로그래밍과 최적화는 보장된다.

 

3-4 동적 계획법의 장단점

[장점]

  : 프로그램을 구현할 때에는 필요한 모든 가능성을 고려해서 구현하게 된다. 따라서 동적 계획법을 이용하여 항상 최적의 결과를 얻을 수 있다.

[단점]

  : 모든 가능성에 대한 고려가 불충분한 경우 최적의 결과를 보장할 수 없다. 동적 계획법을 구현하기 위해서는 충분히 많은 가능성에 대한 고려를 해야만 한다. 또한 다른 방법론에 대해 많은 표(배열)를 이용하므로 메모리를 많이 요구한다.

 

3-5 다이나믹 프로그래밍 점화식을 세우는 방법

  1) 주어진 문제의 해를 구하기 위한 순환적인 성질을 구성하여야 한다.

  2) 전체 문제도 부분 문제 형태로 표현할 수 있어야 한다.

  3) 문제를 어떻게 부분 문제로 분할할 것인지 생각해야 한다.

  4) 일반적으로 동적 계획법 문제는 일정 회수의 선택을 반복하는 구조로 이루어져 있다.

  5) 그 상태에서의 선택과 그 선택 전의 상태를 고려하라.

  6) 한 번의 선택에서는 생길 수 있는 모든 가능성을 고려하라.

  7) 최적해를 찾는 문제라면, 그 가능성 중에서 가장 좋은 선택을 찾아라.

 

다이나믹 프로그래밍 문제풀기 1번

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

[풀이]

  9개의 데이터가 아래와 같이 주어져 있다고 하자.

data	11	17	5	8	6	4	7	12	3
dy	1	1	1	1	1	1	1	1	1

  각각의 배열의 정의는 다음과 같다.   입력 데이터는 data배열이다.

  dy[i]배열은 첫 번째수(data[0])부터 i번째 수(data[i])까지만 있다고 했을 때, i번째 수를 맨 마지막 수로 갖는 부분 증가수열의 최대 길이가 된다.

 

▶ 입력 데이터가 {11, 17, 5, 8, 6, 4, 7}까지 있다고 하자

data	11	17	5	8	6	4	7	12	3
dy	1	2	1	2	2	1	1	1	1

- 11과 7를 비교했을 때 7이 더 작으므로 증가수열이 될 수 없다.

- 17과 7을 비교했을 때 7이 더 작으므로 증가수열이 될 수 없다.

- 5과 7을 비교했을 때 7이 더 큰 수이므로 증가수열에 해당된다. 그러므로 5의 dy배열에 있는 값 +1과 7의 dy배열에 있는 값을 비교해 본다.  5의 dy배열에 있는 값 +1이 7의 dy배열에 있는 값보다 더 크므로 5의 dy배열에 있는 값 +1을 7의 dy 배열에 넣는다.

- 8과 7을 비교했을 때 7이 작으므로 증가수열이 될 수 없다.

- 6과 7을 비교했을 때 7이 더 크므로 증가수열에 해당된다. 그러므로 6의 dy배열에 있는 값 + 1과 7의 dy배열에 있는 값을 배교해 본다. 6의 dy + 1 = 3이고 7의 dy배열의 값은 2이다 6의 dy배열의 값이 더 크므로 7배열의 값을 3으로 저장한다.

- 4와 7을 비고했을 때 7이 더 크므로 증가수열에 해당된다. 4의 dy배열의 값은 + 1 = 2이다. 7의 dy의 값은 3이므로 7의 dy값을 그대로 유지한다.

최종 처리 결과는 아래 표와 같다.

data	11	17	5	8	6	4	7	12	3
dy	1	2	1	2	2	1	3	4	1

 

★ 결국, 우리는 이런 결과를 통해서 다음과 같은 점화식을 세울 수 있다.

data[j]가 data[i]보다 작을 경우에 한해서 dy[j] + 1의 값이 dy[i]보다 더 큰 값일 경우, dy[i]는 dy[j] + 1의 값을 갖는다.

 

[ 문제2번 ] 가장 긴 증가하는 부분 수열4 -  www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

[ 문제3번 ] 가장 큰 증가하는 부분 수열 - www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

[ 문제4번 ] 가장 긴 감소하는 부분 수열 - www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

[ 문제5번 ] 가장 긴 바이토닉 부분 수열 - www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

[ 문제6번 ] 줄세우기 - www.acmicpc.net/problem/2631

2631번: 줄세우기

 

[ 문제7번 ] 전깃줄 - www.acmicpc.net/problem/2565

2565번: 전깃줄