태그: DP
5편
-
동적 프로그래밍(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으로 직접 풀면서 상태 정의와 점화식 세우는 연습을 하고, 동전 문제에서 최소 개수뿐 아니라 사용한 동전까지 역추적하는 방법도 보여 줍니다.
-
C++ 알고리즘 최적화: Big-O로 병목 찾기, 공간-시간 트레이드오프, 메모이제이션
데이터가 늘자 응답이 느려질 때 Big-O로 병목을 찾고, 메모이제이션·슬라이딩 윈도우·해시 테이블로 공간을 내주고 시간을 줄이는 방법을 C++ 예제로 봅니다. Kadane, 투 포인터, partial_sort와 nth_element 비교도 포함합니다.
-
C++ 동적 계획법: 메모이제이션 vs 타뷸레이션, 2D→1D 공간 최적화, 배낭·LCS·Bitmask DP
fib(40)이 느린 이유에서 출발해 메모이제이션과 타뷸레이션의 차이, 2D 테이블을 1D rolling array로 줄이는 방법을 설명합니다. 0/1 배낭, LCS, LIS, 편집 거리, Bitmask DP를 C++로 풀고 재귀 스택 오버플로를 피하는 법도 봅니다.