Ahn9807: /* 개요 */

2023-02-26T10:16:27Z

개요

← 이전 판		2023년 2월 26일 (일) 10:16 판
7번째 줄:		7번째 줄:
	동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.		동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.
	답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.		답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.
	동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 이에 대해 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다.		동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 사실 동적 계획법은 다른 널리 알려진 이름으로는 Memoization즉 메모이제이션이라는 이름으로 불리기도 한다.

	== 구현 ==		== 구현 ==
53번째 줄:		53번째 줄:

	은 모두 길이가 4인 LIS이다.		은 모두 길이가 4인 LIS이다.
			<syntaxhighlight lang="c">
	#include <iostream>		#include <iostream>
	#include <algorithm>		#include <algorithm>
87번째 줄:		88번째 줄:
	return 0;		return 0;
	}		}
			</syntaxhighlight>

Ahn9807: Ahn9807님이 Dynamic programming 문서를 동적 계획법 문서로 이동했습니다

2023-02-25T11:07:00Z

Ahn9807님이 Dynamic programming 문서를 동적 계획법 문서로 이동했습니다

← 이전 판	2023년 2월 25일 (토) 11:07 판
(차이 없음)

Ahn9807: 새 문서: 분류: 알고리즘 패러다임 == 개요 == Dynamic Programming; DP 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 답을 구하기 위해서 했던 계산...

2023-02-25T11:06:42Z

새 문서: 분류: 알고리즘 패러다임 == 개요 == Dynamic Programming; DP 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 답을 구하기 위해서 했던 계산...

새 문서

[[분류: 알고리즘 패러다임]]

== 개요 ==
Dynamic Programming; DP

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.
동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.
답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.
동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 이에 대해 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다.

== 구현 ==
동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

== 예 ==
=== 접근 ===
동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

* f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
* f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 5번의 연산을 거쳐야한다. 이 때 중복되는 부분 문제[* overlapping subproblems - 두 번 이상 계산되는 부분 문제]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 4번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나 뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a,b의 값이 커질 수록 속도 면에서 엄청난 이득을 볼 수 있다. 실제로 a,b가 1증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이 때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.

== 예 ==
=== LIS ===
LIS 란 최장 증가 부분수열을 구하는 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.
이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.
예를 들어 다음 수열이 주어졌다고 하자.

3 5 7 9 2 1 4 8

위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.

3 7 9 1 4 8 (5, 2 제거)
7 9 1 8 (3, 5, 2, 4 제거)
3 5 7 8 (9, 2, 1, 4 제거)
1 4 8 (3, 5, 7, 9, 2 제거)

이들 중 세번째, 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다.

그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.
부분수열 3 5 7 8은 LIS이다.

한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열

5 1 6 2 7 3 8

에서 부분수열

1 2 3 8
5 6 7 8

은 모두 길이가 4인 LIS이다.
#include <iostream>
#include <algorithm>

using namespace std;

int N;

int main(void) {

cin >> N;

int* arr = new int[N];
int* mem = new int[N];

for(int i=0;i<N;i++) {
cin >> arr[i];
mem[i] = 1;
}

for(int i=1;i<N;i++) {
for(int j=0;j<i;j++) {
if(arr[j] < arr[i] && mem[i] <= mem[j]) {
mem[i] = mem[j] + 1;
}
}
}

sort(mem,mem + N);

printf("%d\n",mem[N-1]);

delete[] arr;
return 0;
}

동적 계획법 - 편집 역사

Ahn9807: /* 개요 */

Ahn9807: Ahn9807님이 Dynamic programming 문서를 동적 계획법 문서로 이동했습니다