DP 점화식 세우는 법: 상태 정의가 먼저이고 공식은 그 다음인 이유
DP 점화식을 외우기보다 상태 정의, 선택지, 이전 상태, 초기값, 순회 방향으로 세우는 방법을 코딩테스트 예제로 정리합니다.
-
-
DP에서 메모이제이션과 테이블 방식은 무엇이 다를까: top-down과 bottom-up 선택 기준
동적 계획법에서 메모이제이션과 테이블 방식의 차이를 top-down, bottom-up 관점으로 설명합니다. 재귀, 반복문, 초기값, 순회 방향, 코딩테스트 선택 기준을 Python 예제로 정리합니다.
-
DP 테이블을 2차원에서 1차원으로 줄여도 되는 기준
DP 테이블을 1차원으로 줄여도 되는 기준을 순회 방향과 knapsack 예제로 설명합니다.
-
배낭 문제, 왜 대표 DP일까
배낭 문제가 왜 대표 DP 예제인지 쉽게 설명합니다. 0/1 Knapsack에서 상태 정의, 점화식, 1차원 최적화와 완전 배낭과의 차이까지 코딩테스트 기준으로 정리합니다.
-
LIS는 왜 이분 탐색으로 풀릴까: 가장 긴 증가 부분 수열을 DP보다 빠르게 이해하는 법
LIS를 쉽게 설명합니다. 가장 긴 증가 부분 수열 문제에서 왜 이분 탐색이 등장하는지, DP와 무엇이 다르고 tails 배열이 어떤 의미인지 코딩테스트 기준으로 정리합니다.
-
동적 계획법(DP) 쉽게 이해하기: 점화식은 아는데 왜 문제를 못 풀까
동적 계획법(DP)을 쉽게 설명합니다. 점화식은 알겠는데 문제에 적용이 안 되는 이유를 상태 정의, 중복 부분 문제, 점화식 설계 흐름 중심으로 정리합니다.
