DP 점화식 세우는 법: 상태 정의가 먼저이고 공식은 그 다음인 이유
DP 점화식을 외우기보다 상태 정의, 선택지, 이전 상태, 초기값, 순회 방향으로 세우는 방법을 코딩테스트 예제로 정리합니다.
-
-
DP에서 메모이제이션과 테이블 방식은 무엇이 다를까: top-down과 bottom-up 선택 기준
동적 계획법에서 메모이제이션과 테이블 방식의 차이를 top-down, bottom-up 관점으로 설명합니다. 재귀, 반복문, 초기값, 순회 방향, 코딩테스트 선택 기준을 Python 예제로 정리합니다.
-
DP 점화식은 어떻게 세워야 할까: 문제를 상태와 선택으로 나누는 법
DP 점화식을 세울 때 상태 정의, 선택, 초기값, 계산 순서를 어떻게 잡아야 하는지 코딩테스트 관점에서 설명합니다.
-
DP 테이블을 2차원에서 1차원으로 줄여도 되는 기준
DP 테이블을 1차원으로 줄여도 되는 기준을 순회 방향과 knapsack 예제로 설명합니다.
-
DAG DP 쉽게 이해하기
DAG DP를 쉽게 설명합니다. 위상 정렬 뒤에 DP가 붙는 순간 왜 막히는지, 상태 정의를 어떻게 잡아야 하는지, 값 전파와 최장 경로 예시를 코딩테스트 기준으로 단계적으로 정리합니다.
-
배낭 문제, 왜 대표 DP일까
배낭 문제가 왜 대표 DP 예제인지 쉽게 설명합니다. 0/1 Knapsack에서 상태 정의, 점화식, 1차원 최적화와 완전 배낭과의 차이까지 코딩테스트 기준으로 정리합니다.
