[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용
  : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍'
  : 'Jinhan's Note' 중 'Theme 06. 다이나믹 프로그래밍 - 기초'

1. 다이나믹 프로그래밍
2. Q&A
3. 마치며

1. 다이나믹 프로그래밍(Dynamic Programming, DP)

• 다이나믹 프로그래밍(Dynamic Programming, DP)
  : 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

예를 들어, 피보나치 수열의 경우

1. 재귀적으로 해결
2. DP로 해결

하는 방법이 있음.

// 1. 재귀적으로 해결
if(n <= 1) return 1;
return fibo(n-1) + fibo(n-2);

// 2. DP로 해결
f[0] = f[1] = 1;
for(int i = 2; i <= n; i++)
	f[i] = f[i-1] + f[i-2];
return f[n];

1번 방법은 O(1.618^N)의 시간복잡도를 가짐
반면 2번 방법은 O(N)의 시간복잡도를 가지므로 꽤나 극단적인 차이가 발생.

1) DP를 푸는 과정

DP 문제는 어렵게 하고자 하면 끝도 없이 어려워지지만, 코테 수준에서는 다음 3가지 과정만 지키면 크게 어렵지 않음.

(1) 테이블 정의하기

특별한 방법이 있는 것이 아닌, 경험적으로 익힘.

(2) 점화식 찾기

(3) 초기값 정하기

2. Q&A

-

3. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용
  : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍'
  : 'Jinhan's Note' 중 'Theme 06. 다이나믹 프로그래밍 - 기초'