태그: 동적프로그래밍
3편
-
동적 프로그래밍(DP): 메모이제이션과 타뷸레이션, 점화식 세우는 법
피보나치 수열로 중복 계산 문제를 확인한 뒤, 메모이제이션(Top-Down)과 타뷸레이션(Bottom-Up)으로 같은 문제를 풀어 보고 1차원·2차원 DP와 배낭 문제에서 상태 정의, 점화식, 초기값을 세우는 순서를 설명합니다.
-
DP 패턴 정리: 1차원·2차원 DP, 배낭 문제, LIS 점화식 세우는 법
계단 오르기 같은 1차원 DP, 격자 경로와 LCS 같은 2차원 DP, 0-1 배낭과 무한 배낭, LIS의 O(n²)·O(n log n) 풀이까지 자주 나오는 DP 유형을 점화식과 Python 코드로 비교합니다.
-
DP 실전 문제 풀이: 1로 만들기·편집 거리·동전·LIS·배낭으로 점화식 연습
1로 만들기, 편집 거리, 동전 문제, LIS, 배낭 문제를 Bottom-Up과 Top-Down으로 직접 풀면서 상태 정의와 점화식 세우는 연습을 하고, 동전 문제에서 최소 개수뿐 아니라 사용한 동전까지 역추적하는 방법도 보여 줍니다.