다이나믹 프로그래믹1 [알고리즘] Dynamic Programming (DP, 동적 계획법) (c++) 이번 글에서는 알고리즘 보다는 계산 효율성을 증가시키는 방법 중 하나라고 할 수 있는 DP에 대해 알아보도록 하겠다. DP 정의 DP 사용이유 DP 예시, 구현 DP 정의 DP는 Dynamic Programming의 약자고 한글로는 다이나믹 프로그래밍, 동적 계획법 등등으로 부른다. DP는 큰 문제를 여러 개의 작은 문제로 나누어 풀고, 결합하여 문제를 해결한다. 이렇게만 보면 분할 정복과 비슷하다고 볼 수 있지만, DP는 메모이제이션(memoization) 방식을 사용한다는 것이 다르다. 메모이제이션은 연산 중 이미 계산한 값을 배열에 저장해두고 이후에 그 연산을 하게 되면 저장된 값을 배열에서 가져와 사용하여 중복된 연산을 하지 않는 것이다. DP 사용이유 재귀 함수만을 사용하여 어떤 문제(아래 예시.. 2023. 1. 16. 이전 1 다음
