[Algorithm] 다이나믹 프로그래밍(DP) 개념 및 적용

목 차 개요 DP를 사용하는 이유 DP 적용하기 DP 체감하기 개요 Dynamic Programmin(DP) 또는 동적 프로그래밍이라고도 하는데, DP는 복잡한 문제를 간단한 여러개의 문제로 나눠서 푸는 방식이다. DP는 작은 문제가 반복하여 발생하고 이에 대한 해답을 저장해두고 재사용 하는 특징이 있다. 이렇게 함으로써 계산 속도를 크게 향상시킬 수 있다. DP를 사용하는 이유 DP는 주로 다음 두 가지 속성을 가진 문제에 적용된다. 1. 중복되는 문제 해결: 대표적으로 피보나치 수열의 예시가 있는데, 이 피보나치 수열을 재귀함수로 풀어본다면 코드는 아래 코드와 비슷할 것이다. Fn 을 계산하기 위해서 F(n-1) 과 F(n-2)을 계산해야 하지만, 이들 역시 F(n-3)과 F(n-4)를 필요로 한다...

Algorithm 2023.07.29