코딩테스트 합격의 마지막 관문, 다익스트라와 동적계획법(DP) 한 번에 끝내기

트리와 그래프 탐색을 어느 정도 익히고 나면 이제 다 됐겠지 싶다가도, 막상 실전 문제를 풀다 보면 '최단 경로'나 '점화식'이라는 벽에 부딪히곤 합니다. 사실 이 부분이 공부할 때 가장 번거로우시죠? 개념을 이해했다고 생각했는데 막상 코드를 짜려고 하면 손이 안 움직이는 경우가 허다합니다. 인터넷을 찾아봐도 용어가 너무 수학적으로만 적혀 있어서 오히려 더 헷갈리기도 하고요.
 
저도 처음 공부할 때는 "이걸 사람이 어떻게 실시간으로 생각해내지?"라며 좌절했던 기억이 납니다. 하지만 알고리즘에도 일정한 '패턴'과 '암기 구역'이 분명히 존재합니다. 오늘은 2026년 채용 트렌드에 맞춰 기업들이 가장 선호하는 유형인 다익스트라(Dijkstra)와 동적계획법(DP)을 아주 쉽게, 마치 옆에서 과외하듯 풀어내 보겠습니다.
 

최단 경로의 핵심, 다익스트라(Dijkstra) 알고리즘

다익스트라는 쉽게 말해 '네비게이션'의 원리라고 보시면 됩니다. 출발지에서 목적지까지 가장 빠른 길을 찾는 건데, 여기서 핵심은 "이미 확인한 길은 다시 계산하지 않는다"는 점입니다. 마치 우리가 이미 아는 지름길을 두고 굳이 먼 길을 돌아가지 않는 것과 비슷하죠.

• 작동 원리: 미방문 노드 중 비용이 가장 적은 노드를 선택하고, 그 노드를 거쳐가는 경우를 계산해 기존 비용을 갱신합니다.
• 필수 도구: 우선순위 큐(Priority Queue)를 사용해야 시간 복잡도를 O(E \log V) 수준으로 낮출 수 있습니다.
• 적용 조건: 반드시 간선의 가중치가 '양수'여야만 합니다. 음수 가중치가 있다면 벨만-포드 같은 다른 방식을 써야 하죠.

개인적으로 이 부분이 가장 핵심이라고 생각합니다. 다익스트라 문제를 풀 때 많은 분이 단순히 구현에만 집착하시는데, 사실 '우선순위 큐'에 넣는 기준을 무엇으로 잡느냐가 문제의 성패를 가릅니다. 솔직히 말씀드리면, 실전에서는 다익스트라 변형 문제가 훨씬 많이 나와요. 단순히 거리뿐만 아니라 '남은 연료'나 '통행료' 같은 조건을 섞어서 내기 때문입니다.

구분	일반 구현(배열)	우선순위 큐 활용
시간 복잡도	O(V^2)	O(E \log V)
추천 상황	노드 수가 적을 때	대부분의 실전 코딩테스트
주요 장점	구현이 단순함	대규모 데이터 처리에 유리

 
혹시 다익스트라를 구현하면서 '방문 처리'를 빼먹어서 무한 루프에 빠져본 적 있으신가요? 저도 처음에 그 실수 때문에 한참을 헤맸던 기억이 나네요.

막막함의 끝판왕, 동적계획법(DP) 정복하기

DP는 이름부터가 참 위협적입니다. 'Dynamic Programming'이라니, 뭔가 엄청난 실시간 시스템 같지만 사실은 "기억하며 풀기"에 불과합니다. 복잡한 문제를 작은 조각으로 나누고, 그 조각의 답을 어딘가(메모장)에 적어두는 거예요. 나중에 똑같은 조각이 나오면 계산하지 않고 메모장을 보고 베끼는 거죠.

• Top-Down (재귀): 큰 문제부터 시작해서 작은 문제로 내려가는 방식입니다. '메모이제이션'이 필수입니다.
• Bottom-Up (반복문): 작은 문제부터 차근차근 답을 쌓아 올려서 최종 목적지에 도달하는 방식입니다. 보통 코테에서는 이 방식을 더 선호합니다.
• 점화식 세우기: f(n) = f(n-1) + f(n-2) 같은 규칙을 찾아내는 것이 실력의 척도입니다.

이건 모르면 손해 보는 꿀팁인데, DP 문제를 마주했을 때 도저히 점화식이 안 떠오른다면 일단 n=1, 2, 3, 4 정도까지 손으로 직접 써보세요. 의외로 고등학교 때 배웠던 수열의 규칙이 보이는 경우가 많습니다. 제가 볼 때 DP는 수학 능력이 아니라 '관찰력' 싸움입니다.
 

실전에서 주의해야 할 오답 포인트

공부를 열심히 해도 실전에서 떨어지는 분들은 보통 '도구 선택'에서 실수를 합니다. 모든 최단 경로 문제를 다익스트라로 풀려고 하거나, 모든 최적화 문제를 DP로 풀려고 고집부리는 경우죠. 하지만 이런 방식은 때로는 문제를 더 어렵게 만들 수 있습니다.

• 다익스트라 주의점: 가중치가 없는 그래프(모든 길의 값이 1인 경우)라면 굳이 다익스트라를 쓸 필요가 없습니다. BFS가 훨씬 빠르고 간결하거든요.
• DP 주의점: 모든 상황을 다 저장하려고 하면 메모리 초과(Memory Limit Exceeded)가 발생합니다. 꼭 필요한 상태값만 변수로 관리하는 센스가 필요해요.
• 2026년 기준 업데이트: 최근 IT 대기업 코테에서는 단순히 알고리즘을 아는지를 넘어, '공간 복잡도'를 얼마나 효율적으로 관리하는지를 더 중요하게 봅니다. 반드시 효율성을 체크하세요.

하지만 이런 방법들이 누구에게나 정답은 아닙니다. 어떤 분들은 정교한 점화식을 세우는 것보다 차라리 완전 탐색에 백트래킹을 섞는 게 훨씬 손에 잘 익을 수도 있거든요. 본인의 성향에 맞지 않는 알고리즘을 억지로 끼워 맞추기보다, 내가 가장 실수 없이 구현할 수 있는 최선의 방법을 찾는 게 중요합니다.

코딩테스트 합격을 위한 학습 로드맵

공부 순서가 엉키면 머릿속만 복잡해집니다. 제가 추천하는 흐름은 다음과 같습니다. 먼저 그리디(Greedy)로 "지금 당장 최선인 것"을 찾는 감각을 익히세요. 그 다음 다익스트라로 넘어가서 "누적된 최선"을 찾는 법을 배우고, 마지막에 DP로 "과거를 활용한 최선"을 마스터하는 겁니다.
 
기술 블로그나 공식 문서를 참고할 때 주의할 점도 있습니다. 2025년 이후로 라이브러리 버전이나 언어별 성능 차이가 미세하게 변하고 있으니, 반드시 본인이 사용하는 언어(Python, Java, C++ 등)의 최신 공식 레퍼런스를 확인하시는 과정이 꼭 필요합니다.

단계	학습 주제	핵심 키워드
1단계	기초 그래프	DFS, BFS, 인접 리스트
2단계	최단 경로	다익스트라, 플로이드-워셜
3단계	최적화	DP 점화식, 배낭 문제(Knapsack)

 
여러분은 평소에 문제를 풀 때 어떤 알고리즘이 가장 어렵게 느껴지시나요? 혹은 본인만의 점화식 세우는 노하우가 따로 있으신가요?

결국 코딩테스트 합격의 핵심은 얼마나 많은 알고리즘을 외우느냐가 아니라, 문제를 보고 어떤 도구를 꺼낼지 결정하는 '판단력'에 있는 것 같습니다. 다익스트라든 DP든 본질은 복잡한 세상을 단순한 규칙으로 쪼개는 과정이니까요.
 
제 생각에는 너무 어려운 문제에 매몰되어 하루를 다 쓰기보다는, 쉬운 문제를 여러 번 반복하며 손에 익히는 게 실전에서 훨씬 유리해 보입니다. 당장 내일 시험이라도 이 두 가지만 확실히 잡고 가면, 적어도 손도 못 대고 나오는 일은 없을 거예요. 오늘 정리해 드린 내용이 여러분의 합격 통보에 작은 보탬이 되었으면 좋겠습니다.

입사 코딩테스트 트리와 그래프 완벽 이해: DFS BFS 탐색부터 이진트리까지