동적 프로그래밍이란?
- 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법
- 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생기는데, 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법
전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식
여기서 중요한 개념!
메모이제이션(Memoization)
함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식입니다. 이러한 메모이제이션은 필요한 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져올 수 있습니다.
이 블로그에 예시로 나와있는 문제를 보면 이해가 될것이다.
블로그를 보면서 값이 어떻게 변화하는지 그려봤다.
이 문제에서는 sum 배열을 메모이제이션을 하기 위해 사용했다!
메모이제이션을 했기때문에 각 자리의 최종합?을 매번 [0,0] 부터 더해줄 필요가 없는것이다!
참고
