Dynamic Programming(동적 계획법)이란?
- 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말
- 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법
- 구체적 알고리즘보다는 문제해결 패러다임에 가까움
cf) Divide and Conquer(분할정복)과 비슷?
- 분할정복 -> 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법 => 작은 문제에서 반복이 일어나는 부분이 없음
- 동적 계회법 -> 작은 부분 문제들의 반복(답이 바뀌지 않음)을 이용해 풀어가는 방법
- 차이법 => 작은 문제가 중복이 일어나는지 안일어나는지
Dynamic Programming 방법
- 모든 작은 문제들은 한번만 푼다
- 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 그 결과값을 이용
Dynamic Programming 조건
- 작은 문제의 반복이 일어나는 경우
- 같은 문제의 정답이 구할때마다 같은 경우
피보나치
- 동적 계획법의 대표적인 예시
① [재귀함수 형태의 피보나치 수열]
- 피보나치 수열은 재귀함수의 형태로 표현된다
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) when n > 2
- 실제로 컴퓨터가 계산하기에는 매우 부적합한 형태 ->프로그램 메모리의 스택에 데이터가 쌓여 함수가 계속 호출되면 메모리에 쌓이는 것들이 증가 => 숫자가 조금만 커져도 시간/공간 복잡도가 지수 스케일로 증가!(Exponentioal Explosion) (공간 복잡도의 경우 스택 오버플로우가 발생해 프로그램이 튕귈 수 있음)
② [동적 계획법 형태의 피보나치 수열]
-반복계산을 막기 위해 이전에 계산했던 값들을 배열에 저장(Top-down, Bottom-up ...)
ⓐTop-down
- 위에서 내려오는 것 = 큰 문제부터 시작해 계속 작은 문제로 분할해 가면서 푸는 것
- 장점 : 코드의 가독성 증가
- 단점 : 작성이 어려움
int memo[100]; //메모이제이션 공간. 전역 변수이므로 0으로 초기화
int fibonacci(int n)
{
if (n<=1) //0번째, 1번째 피보나치 수
return n;
if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
return memo[n]; //메모 리턴
memo[n]=fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
return memo[n];
}
ⓑBottom-up
- 바닥에서 올라오는 것
- 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것
- 장점 : 풀기 쉬움
- 단점 : 코드의 가독성 저하
int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점. 이 코드에선 이미 f_data[1]까지 정의되어있기 때문에 1로 초기화한다.
int f(int n) //피보나치 수열의 제 n항을 구한다. 배열의 관점에서는 n-1번째 요소를 구하는 것.
{
int i;
if(f_data[n-1] == 0) // 아직 구한 적이 없으면 구한다
{
for(i=last_pos+1; i<n; ++i)
{
f_data[i] = f_data[i-1] + f_data[i-2];
}
last_pos = n-1;
}
return f_data[n-1];
}
=> 숫자를 저장하는 공간이 필요한 대신 O(n)의 시간 복잡도로 구현할 수 있음
'자료구조' 카테고리의 다른 글
링크드 리스트 (0) | 2022.03.04 |
---|---|
큐(Queue)란? (0) | 2020.04.21 |
스택(stack)이란? (0) | 2020.04.21 |
댓글