DP 점화식 세우는 법: 상태 정의가 먼저이고 공식은 그 다음인 이유
DP 점화식을 외우기보다 상태 정의, 선택지, 이전 상태, 초기값, 순회 방향으로 세우는 방법을 코딩테스트 예제로 정리합니다.
-
-
greedy 반례부터 봐야 하는 이유
greedy 알고리즘에서 반례가 중요한 이유를 정리합니다. 정렬 기준, 동률 처리, 교환 논증, 회의실 배정과 동전 예시로 선택 기준 검증법, 실수 패턴, DP와 구분하는 신호, 연습 루틴까지 쉽게 단계별로 설명합니다.
-
누적합(prefix sum)은 언제 떠올려야 할까: 구간 합을 매번 다시 계산하지 않는 법
누적합을 떠올려야 하는 문제 신호와 1차원/2차원 prefix sum, off-by-one 실수를 예제로 설명합니다. 구간 합을 매번 다시 계산하지 않고 빠르게 구하는 기준과 실전 실수를 정리합니다.
-
DP 점화식은 어떻게 세워야 할까: 문제를 상태와 선택으로 나누는 법
DP 점화식을 세울 때 상태 정의, 선택, 초기값, 계산 순서를 어떻게 잡아야 하는지 코딩테스트 관점에서 설명합니다.
-
다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가도 되는 이유
다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가는 이유를 stale entry, dist 배열, continue 조건으로 설명합니다.
-
BFS visited는 큐에 넣을 때 체크해야 할까, 꺼낼 때 체크해야 할까
BFS visited를 큐에 넣을 때 체크하는 이유와 꺼낼 때 체크할 때 생기는 중복 enqueue 문제를 예제로 설명합니다.
