알고리즘 기법 [DP vs 다익스트라 vs 완전탐색]

주제

대표적인 알고리즘 기법(DP vs 다익스트라 vs 완전탐색) 구분하기

 

✅ 알고리즘 세 가지 분류

분류	대표 기법	주로 사용하는 상황
완전탐색 (Brute Force)	백트래킹, DFS, BFS	가능한 모든 경우를 직접 탐색해야 할 때 (최대값, 조합 등)
동적 계획법 (DP)	Memoization, Tabulation	중복된 하위 문제가 있고, 최적해를 저장하여 재활용 가능할 때
다익스트라 (Dijkstra)	우선순위 큐 기반 최단 경로	가중치가 있는 그래프에서 최소 거리, 최소 비용 계산 시

 

✅  각 기법의 특징 비교

항목	완전탐색	동적 계획법 (DP)	다익스트라
시간 효율성	가장 낮음 (보통 O(2ⁿ), O(n!))	중간 (O(N²) ~ O(N×M))	높음 (O(E log V))
공간 효율성	낮거나 중간	중간 (DP 테이블 필요)	중간 (거리 배열 + 우선순위 큐 필요)
핵심 아이디어	가능한 경우를 전부 시도	작은 문제의 답을 저장해 큰 문제 해결	최소 거리부터 탐색해 최단 경로 구성
대표 예시	N과 M 시리즈, 조합 문제	피보나치, 배낭 문제, 등굣길	그래프에서 A → B 최소 비용

 

✅ 기본 판단 기준

구조	기존 추천 알고리즘
2차원 좌표(격자)	✅ DP or BFS (경로 수, 거리 등)
그래프(정점+간선)	✅ 다익스트라 (최단거리), DFS/BFS (탐색)

 

✅  정확한 판단을 위한 기준

조건	추천 알고리즘	설명
격자(좌표) + 모든 경로 수 구하기	✅ DP	예: 등굣길 문제 (왼쪽/위쪽에서 누적)
격자(좌표) + 최단 거리 구하기	✅ BFS (가중치 없음), 다익스트라 (가중치 있음)	예: 미로, 게임 맵, 최소 이동 거리
그래프 + 최단 거리	✅ 다익스트라	예: 도시 간 이동 비용
그래프 + 간선에 음수 존재	✅ 벨만포드	다익스트라는 음수 간선에 부적합
작은 입력 + 모든 경우 탐색	✅ 완전탐색, 백트래킹	예: 순열, 조합, 경로 전부 시도