Dynamic Programming vs Dijkstra's Algorithm

✅ 1. DP (동적 계획법, Dynamic Programming)

📌 개념

• 문제를 작은 부분 문제로 나누고, 그 결과를 저장하면서 중복 계산을 줄이는 기법
• 한 번 계산한 값을 저장해 두고, 이후 필요할 때 재사용
• 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)를 만족해야 적용 가능

📌 특징

• Bottom-Up 방식(반복문) 또는 Top-Down 방식(재귀 + 메모이제이션) 사용
• 2차원 DP 배열을 활용하여 문제 해결
• O(N²) 수준의 문제 해결 가능

📌 적용 예시

1. 최소 경로 합 문제 (예제 문제처럼, 오른쪽 & 아래로만 이동)
2. 피보나치 수열 (Top-Down or Bottom-Up)
3. 배낭 문제 (Knapsack Problem)
4. 최장 공통 부분 수열(LCS)
5. 동전 거스름돈 문제

---

✅ 2. 다익스트라 알고리즘 (Dijkstra’s Algorithm)

📌 개념

• 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘
• BFS(너비 우선 탐색)와 유사한 방식으로 최단 경로를 갱신하면서 진행
• 우선순위 큐(Heapq)를 사용하여 가장 작은 비용을 먼저 탐색

📌 특징

• 음의 가중치가 없는 경우에만 동작 (음수 가중치가 있으면 벨만-포드 알고리즘 사용)
• 우선순위 큐를 사용하면 O(E log V)의 시간 복잡도
• 그래프 기반 문제 해결에 적합

📌 적용 예시

1. 네비게이션(최단 거리 경로 탐색)
2. 인터넷 라우팅(패킷 최단 경로)
3. 게임 맵에서 최단 거리 찾기
4. 도시 간 최단 이동 시간 계산

---

✅ DP vs 다익스트라 차이점

비교 항목	DP (동적 계획법)	다익스트라
사용 목적	중복 계산을 줄이며 최적 해 구하기	최단 경로 찾기
사용 구조	2D 배열을 활용한 최적화	그래프와 우선순위 큐 활용
시간 복잡도	O(N²) (경로 문제), O(NM) (Knapsack 등)	O(E log V)
적용 문제	경로 문제, 문자열 문제, DP 최적화 문제	그래프에서 최단 거리 찾기

---

✅ 어떤 경우에 어떤 걸 써야 할까?

상황	DP 사용	다익스트라 사용
격자(grid)에서 최소 비용 경로 찾기	✅	❌
그래프에서 최단 경로 찾기	❌	✅
배낭 문제(물건을 담을 때 최적의 조합 찾기)	✅	❌
도시간 최단 경로 탐색(지도, 네비게이션 등)	❌	✅

---

✅ 결론

• DP: 중복 계산을 줄이며 최적의 해를 찾는 경우
• 다익스트라: 가중치 그래프에서 최단 경로를 찾는 경우