그래프 문제는 입력부터 다르다: 인접 리스트와 인접 행렬은 언제 무엇을 써야 할까
그래프 입력을 인접 리스트와 인접 행렬로 바꾸는 기준을 시간복잡도, 메모리, BFS/DFS 예제로 정리합니다. 간선 수와 연결 확인 방식에 따라 어떤 구조가 더 자연스러운지 단계적으로 설명하고 입력 실수까지 짚습니다.
-
-
DP 점화식은 어떻게 세워야 할까: 문제를 상태와 선택으로 나누는 법
DP 점화식을 세울 때 상태 정의, 선택, 초기값, 계산 순서를 어떻게 잡아야 하는지 코딩테스트 관점에서 설명합니다.
-
KMP 알고리즘의 pi 배열은 왜 필요한가: 문자열 매칭에서 다시 비교하지 않는 법
KMP 알고리즘에서 pi 배열이 왜 필요한지, prefix와 suffix를 이용해 불일치 후 다시 비교하지 않는 원리를 예제로 설명합니다.
-
0-1 BFS는 다익스트라와 무엇이 다를까: 가중치가 0과 1일 때 deque를 쓰는 이유
0-1 BFS가 다익스트라와 어떻게 다르고, 간선 가중치가 0과 1일 때 deque로 최단거리를 구할 수 있는 이유를 설명합니다.
-
DP 테이블을 2차원에서 1차원으로 줄여도 되는 기준
DP 테이블을 1차원으로 줄여도 되는 기준을 순회 방향과 knapsack 예제로 설명합니다.
-
다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가도 되는 이유
다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가는 이유를 stale entry, dist 배열, continue 조건으로 설명합니다.
