DP 점화식 세우는 법: 상태 정의가 먼저이고 공식은 그 다음인 이유
DP 점화식을 외우기보다 상태 정의, 선택지, 이전 상태, 초기값, 순회 방향으로 세우는 방법을 코딩테스트 예제로 정리합니다.
-
-
Dijkstra visited 사용 기준
다익스트라에서 visited가 꼭 필요한지, 우선순위 큐 구현에서 outdated entry를 어떻게 처리하는지 정리합니다. dist 배열, heap 중복 삽입, 음수 간선 불가 조건, 구현 실수까지 예제로 설명합니다.
-
greedy 반례부터 봐야 하는 이유
greedy 알고리즘에서 반례가 중요한 이유를 정리합니다. 정렬 기준, 동률 처리, 교환 논증, 회의실 배정과 동전 예시로 선택 기준 검증법, 실수 패턴, DP와 구분하는 신호, 연습 루틴까지 쉽게 단계별로 설명합니다.
-
DP에서 메모이제이션과 테이블 방식은 무엇이 다를까: top-down과 bottom-up 선택 기준
동적 계획법에서 메모이제이션과 테이블 방식의 차이를 top-down, bottom-up 관점으로 설명합니다. 재귀, 반복문, 초기값, 순회 방향, 코딩테스트 선택 기준을 Python 예제로 정리합니다.
-
누적합(prefix sum)은 언제 떠올려야 할까: 구간 합을 매번 다시 계산하지 않는 법
누적합을 떠올려야 하는 문제 신호와 1차원/2차원 prefix sum, off-by-one 실수를 예제로 설명합니다. 구간 합을 매번 다시 계산하지 않고 빠르게 구하는 기준과 실전 실수를 정리합니다.
-
그래프 문제는 입력부터 다르다: 인접 리스트와 인접 행렬은 언제 무엇을 써야 할까
그래프 입력을 인접 리스트와 인접 행렬로 바꾸는 기준을 시간복잡도, 메모리, BFS/DFS 예제로 정리합니다. 간선 수와 연결 확인 방식에 따라 어떤 구조가 더 자연스러운지 단계적으로 설명하고 입력 실수까지 짚습니다.
