동적 계획법(Dynamic Programming)
동적 계획법: 하나의 문제를 여러 작은 문제로 나누고, 작은 문제의 결과를 저장하여 큰 문제를 해결한다. 하나의 문제를 여러 개의 하위 문제로 나눈 다음, 결합하여 답을 도출한다. 하위 문제들의 결과를 저장한다.(Memoization, 메모이제이션) -> 동일한 문제가 나왔을 때 저장해둔 결과를 가져다 쓰며, 실행속도 빠르게 한다. 겹치는 부분 존재 DP는 작은 문제의 결과를 저장하고 재사용하여 문제를 푼다. 따라서, 동일한 작은 문제가 있을 때 사용한다. 최적 부분 구조 작은 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 작은 문제에서 구한 최적의 결과가 큰 문제에서도 동일하게 최적으로 적용되는 경우이다. 동적계획법의 가장 대표적인 피보나치 수를 구현해보자! 피보..
2023.03.10