[Algorithm] 동적계획법(DP - Dynamic Programming)
·
Algorithm/Study
알고리즘 스터디 첫 주차 주제로 DP가 선정되었다.악명 높은 DP,, 이번 기회에 부셔버릴테다,, 😠📌 동적계획법(DP - Dynamic Programming)이란?전체 문제를 해결하기 위해서 큰 문제를 작은 문제로 쪼개고, 작은 문제들의 답을 가지고 큰 문제를 해결하는 방식이다.공간 복잡도를 늘리고 시간 복잡도를 줄이는 방법이라고 한다.=> 시간은 줄이고 메모리 사용은 늘어나는 특징을 가진다. 🤔 왜 DP를 사용할까?피보나치 수열을 예시로 살펴보자.피보나치 수열을 구하는 방법은 간단하다.F(n) = F(n-1) + F(n-2)의 공식대로 계산하면 된다. 이를 재귀방식으로 구현한다면 한다고 해보자.F(10)을 구하기 위해서는,1. F(10)을 호출 => 1번2. F(10)이 F(9), F(8)을 호..