동적계획법 : 동적계획법 이론과 문제
I. 들어가며 모든 알고리즘은 사실 완전탐색(DFS, BFS)를 이용해서 정답을 도출할 수 있다 그럼에도 불구하고 알고리즘 기법이 탄생한 이유는 비효율적인 연산과 시간을 없애고 답을 효율적으로 도출하기 위함이다. 동적계획법(이하 'DP')은 가장 다양한 유형의 문제들을 논리적 사고로 효율적으로 풀 수 있는 알고리즘이다. II. 동적계획법 알아보기 1. 정의 동적계획법(Dynamic programming : DP) 는 1) 복잡한 여러문제를 간단한 문제로 분리하여 2) 부분의 문제를 해결함으로써 3) 최종적으로 복잡한 문제의 답을 구하는 방법을 의미한다. 2. 핵심이론 (1) 원리와 구현방식 [예 : 피보나치 수열] 1) 큰 문제를 작은문제로 나눌 수 있어야한다 (분리) [6번 수열 구하는 문제는 5번과 ..
