CodeAngie

동적프로그래밍동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 방법이다.분할 정복과는 다르게 작은 문제를 푸는데서 답이 같은 문제가 중복적으로 일어날 경우 사용한다.보통 점화식을 만들 수 있다.1. 동적프로그래밍의 조건큰 문제는 작은 문제로 나눌 수 있고 작은 문제가 반복해서 나타난다.같은 문제라면 계산할 때마다 같은 답이 도출된다.2. 메모이제이션 (Memoization)메모이제이션은 한번 풀었던 작은 문제를 다시 반복해서 풀지 않기 위해 메모해두고 필요할 때 답만 꺼내 보는 것이다.담아 놓는 것이기 때문에 캐싱 (caching) 이라고도 불린다.메모이제이션을 통해 먼저 구한 결과를 담아 두면, 아래 피보나치 예시에서 점선으로 표시된 노드는 먼저 먼저 계산된 값을 사용하면 되기 때문에 반복해서 계산..