DP 이론

1. DP 이론 개요

https://youtu.be/5dRGRueKU3M?si=Uo3Ki-LDdKyD9QRc

 

2. Multi-stage Graph

https://youtu.be/9iE9Mj4m8jk?si=HOFYjoNjMZuLklpW

https://youtu.be/FcScLYJI42E?si=z2_05CCqWl_bXZCN

 

3. All Pairs Shortest Path (Floyd-Warshall) 최단 경로: 두 정점 사이의 최단 거리 찾기 문제

https://youtu.be/oNI0rf2P9gE?si=rgh9UYMb4a0tLQY7

 

3. Bellman Ford Algorithm : 음수 가중치가 있는 그래프에서 최단 경로 찾기, 

1. 음수 가중치(negative weight)가 있는 그래프에서도 최단 경로를 구하고 싶을 때
   (Dijkstra는 음수 가중치가 있으면 못 써요.)
2. 음수 사이클(negative cycle)이 있는지 검출하고 싶을 때
   1. 원래는 최대 V-1 번 돌리면, 끝나야 하는데, 그 이후에도 계속 값이 바뀌면.. 싸이클이 있는 것임.!!

---

쉽게 정리하면

상황	어떤 알고리즘 써야 하나
모든 가중치가 0 이상 (음수 없음)	Dijkstra
가중치에 음수가 있을 수 있음 (음수 사이클은 없음)	Bellman-Ford
음수 사이클 존재 여부도 검사하고 싶음	Bellman-Ford

---

✅ 핵심 요약

• 음수 가중치가 있을 때도 동작하는 최단 경로 알고리즘
• 음수 사이클이 있는지 찾을 수도 있음
• 시간 복잡도는 O(V × E) (V=정점 수, E=간선 수) → 느린 편임

---

🔥 정말 쉽게 한 줄로 말하면

"음수 간선 있거나, 음수 사이클 확인할 때는 Bellman-Ford."

 

✅ Bellman-Ford에서 사이클 감지하는 방법

1. V-1번 동안 모든 간선을 Relax(업데이트) 합니다.
   (V = 정점 수)
2. 그 다음 1번 더 모든 간선을 검사합니다.
3. 만약 이 추가 검사에서 거리가 또 줄어든다면,
   👉 음수 사이클(negative cycle)이 존재한다는 뜻입니다.

---

왜 이렇게 하냐?

• 최단 경로는 최대 V-1개의 간선만 거칠 수 있어요.
  (정점이 V개면, V-1개를 넘어가면 순환(=사이클) 이 생기기 때문)
• 그래서 정상 그래프라면 V-1번만 돌면 최단 경로가 고정돼야 합니다.
• 그런데 V-1번 다 돌고도 또 거리가 줄어든다? → 무한히 줄어드는 루프(=음수 사이클)가 있다!

---

🔥 쉽게 요약

단계	설명
1~V-1번	정상 최단 거리 계산
V번째	또 줄어드는 거 있으면 → 음수 사이클 있음

---

✅ 코드 감지 부분만 간단히 보여드리면

for i in range(V-1):
    for u, v, cost in edges:
        if dist[u] + cost < dist[v]:
            dist[v] = dist[u] + cost

# 사이클 감지
for u, v, cost in edges:
    if dist[u] + cost < dist[v]:
        # 음수 사이클 발견
        return True

# 사이클 없으면
return False

---

✅ 한 문장 정리

"Bellman-Ford에서는 V-1번 돌리고, 마지막에 간선 한번 더 검사해서 거리가 줄어들면 음수 사이클이 있는 걸 감지한다."

 

• 정점을 하나씩 지나가는 경로는 최대 V개입니다.
• 그런데 시작 정점 빼고 나머지 연결만 보면 간선은 V-1개만 필요합니다.

👉 즉, 최단 경로 상에서는 간선을 V-1개 넘을 수 없다.

---

예를 들어

• 정점이 A, B, C, D 4개 있으면
• A → B → C → D 이렇게 이동할 수 있음 (간선 3개)

4개 정점 = 3개 간선

---

✅ 왜 Bellman-Ford는 V-1번만 반복해도 충분한가?

• 첫 번째 루프: 거쳐야 하는 간선이 1개인 최단 경로를 찾음.
• 두 번째 루프: 거쳐야 하는 간선이 2개인 최단 경로를 업데이트.
• 세 번째 루프: 거쳐야 하는 간선이 3개인 최단 경로를 업데이트.
• ...
• V-1번째 루프까지 하면 모든 정점을 연결하는 최단 경로까지 다 고려됨.

✅ 그래서 V-1번 돌면 모든 최단 경로가 완성됩니다.

---

🔥 진짜 쉽게 요약

질문	답변
최단 경로에 최대 몇 개 간선?	V-1개
그래서 Bellman-Ford 몇 번 반복?	V-1번

---

✅ 마지막 핵심정리 문장

"최단 경로는 정점을 중복 없이 지나야 하므로 최대 V-1개의 간선만 사용하고,
Bellman-Ford는 V-1번만 돌면 모든 최단 경로를 구할 수 있다."

---

💬 추가 덤

• V-1번 다 돌고도 거리가 또 줄어들면?
  👉 사이클(특히 음수 사이클)이 있는 것
  👉 그래서 마지막에 한 번 더 검사하는 것!

 

4. 0/1 Knapsack

https://youtu.be/nLmhmB6NzcM?si=0_pQeUzi7mEsK7Vt

https://youtu.be/zRza99HPvkQ?si=QWUlU3XTsf4FzXYd