🧠패러다임
Dynamic Programming Algorithms
Stack answers to small problems into big ones. Learn the 2 topics below step by step with interactive visualizations.
🧠피보나치 수열 (DP)
동적 계획법(Dynamic Programming)으로 이전 부분해(subsolution)를 테이블에 저장하고 재사용해 중복 계산을 제거합니다. 단순 재귀 O(2^n)을 O(n)으로 끌어내리는 가장 대표적인 메모이제이션 예시입니다.
O(n)🧠최장 증가 부분 수열 (LIS)
수열에서 순서를 유지한 채 고를 수 있는 가장 긴 증가 부분 수열의 길이를 구합니다. dp[i]는 'i번째 원소로 끝나는 LIS 길이'라는 부분해로 정의되며, 앞쪽 작은 원소들의 부분해를 재사용해 O(2ⁿ) 완전 탐색을 O(n²)로 끌어내립니다.
O(n²)