고양이 두 잔

동적 계획법이란 미리 구해뒀던 답을 이용해 하나의 연산은 한 번만 하도록 하는 프로그래밍 패러다임이다. 지난 글에서 알아본 그리디 알고리즘이 그때그때 최적의 값을 찾아가는 방법이라면, 동적 계획법은 문제를 쪼개 모든 경우의 수를 살펴본 뒤 답을 구한다. 다만 연산 속도의 향상을 위해 이미 계산한 값을 저장해두는데, 이때 사용되는 메모리를 캐시(Cache)라고 한다. 동적 계획법이 적용될 수 있는 조건은 두 가지가 있는데, Overlapping Subproblem - 큰 문제를 중복되는 작은 문제로 나눌 수 있다. Optimal Substructure - 나눠진 작은 문제에서 구한 답을 이용해 전체 문제의 답을 구할 수 있다. 가 그것이다. 가장 쉬운 예로 피보나치수열을 들 수 있는데, 재귀 함수만을 이용..