다이나믹 프로그래밍의 핵심 🔑 수열의 점화식을 구하는 것이 핵심! 중복되는 연산을 줄이자. 연산 속도와 메모리공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성 현재의 항들로 다음 항을 구할 수 있는 경우 다이나믹 프로그래밍을 쓴다. 대표적 예시 >> 피보나치 수열 재귀 함수(탑다운 방식) 구현하긴 간편하지만 숫자가 커지면 기하급수적으로 연산횟수가 늘어난다. f(100)을 구하기 위해서는 약 1,000,000,000,000,000,000,000,000,000,000번 연산을 해야한다. 시간으로 따지면 수백억년이 넘어가는 시간이 걸림. 다이나믹 프로그래밍 (보텀업 방식) 하지만 다이나믹으로 풀 경우, 같은 문제라면 한번 씩만 풀어 저장해 놓기 때문에 효율적으로 해결하게 된다. O(N)의 성질을 보임..