재귀 (1) 썸네일형 리스트형 Chap 5. 동적 계획 알고리즘 Dynamic Programming(DP) 알고리즘 -입력 크기가 작은 부분 문제들을 해결한 후에 -그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해어 -최종적으로 원래 주어진 입력의 문제를 해결 [문제] n개의 원소를 갖는 문제 같은 형태로 문제를 해결해나가지만 n개보다 작은 값으로 (작은 문제로 ) 만들어서 푸는 방법 (1) 최적의 하위구조 특성 k < n 인 k개의 원소를 갖는 문제를 정의하고 문제를 풀었더니 그것이 최적의 풀이법이고 점점점 작은 문제들을 결합해서 최종 풀이법이 완성되어지는 형태의 특성을 갖는 문제를 “최적의 하위구조 특성을 갖는 문제”라고 부른다. 예시) 두 도시를 자동차로 갈 수 있는 최단 경로 A도시 B도시 C도시가 있는데 A에서 C로 가기 위해서는 A-B의 최단 경로를.. 이전 1 다음