44번

동적 계획 알고리즘

동적 계획법이란? - 복잡한 문제를 푸는 알고리즘의 한 종류 - 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결한 뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다. - 이 때 계산한 작은 문제의 값을 저장해 두는 메모리를 캐시(cache)라고 부른다. 동적 계획법의 조건 Overlapping Subproblem : 겹치는 부분(작은) 문제 (중복되는 부분문제) 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있음 재귀 알고리즘 피보나치 수열이 대표적인 예시 Optimal Substructure : 최적 부분구조 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 설계될 수 있음 문제의 정답을 작은 문제의 정답에서부터 구할 수 있다. 그리디 알고리즘의 유용성을 판별하는데 사용되기도 한다...