algo_lec11

 

Today’s Topics

1. Optimality Principle
   최적 부분 구조 (Principle of Optimality)
2. Example 7: Floyd-Warshall’s Algorithm
   모든 쌍 최단 경로 문제 (All-Pair Shortest Path Problem)
3. Example 8: 0-1 Knapsack Problem
   0-1 배낭 문제 (0-1 Knapsack)

---

Optimality Principle

• 어떤 문제의 최적해(optimal solution) 가 존재할 때,
  그 문제의 모든 부분 문제(subproblem) 에 대해서도 최적해가 포함되어야 한다는 성질을 의미합니다.

즉, 전체 문제의 최적 해결 방법은 각 부분 문제들의 최적 해결 방법을 포함해야 한다.

*최장 경로 문제에서는 최적 부분 구조가 항상 성립하지 않는다.

 

Example7: Floyd-Warshall Algorithm (모든 쌍 최단 경로)

- Find the shortest paths between all pairs of vertices in a graph using dynamic programming.
- 점화식 (Recursive formula): D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])

# D[i][j] = i에서 j까지 바로 가는 기존 거리와 i → k → j로 우회하는 거리 중 더 짧은 것을 선택.

# Python Pseudo-code
def floyd_warshall(dist, length):
    for k in range(length):
        for i in range(length):
            for j in range(length):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

모든 정점 쌍 (i, j)에 대해 최단 경로의 거리를 구하는 알고리즘.
그래프에 음의 가중치가 있어도 사용 가능하며, 동적 계획법(DP)을 사용한 대표적인 알고리즘 중 하나.

 

언제 쓰이는가?

• 입력: 가중치가 있는 방향 그래프 (음수 가능, 음의 사이클은 없어야 함)
• 목적: 모든 쌍 정점 간의 최단 거리를 구하고 싶을 때

D[k][i][j]: 정점 i에서 j로 가는 최단 거리인데, 중간 정점으로 1~k번 정점까지만 허용할 때의 최단 거리

 

 

• 초기화
  • dist[i][j]는 i → j의 직접 경로 거리로 설정 (없으면 무한대)
  • dist[i][i] = 0 (자기 자신으로 가는 거리)
• 중간 정점 k를 하나씩 증가시키며 업데이트

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]​

 

Step 0: 초기값

• D⁽⁰⁾[2][5] = ∞
  (v₂에서 v₅로 가는 직접 경로가 없으므로 무한대)

Step 1: 중간 정점으로 v₁만 허용

• 시도: v₂ → v₁ → v₅
  • 거리 = v₂→v₁ (9) + v₁→v₅ (5) = 14

Step 2, 3: v₂, v₃ 허용

• 중간 정점이 v₂(v₂→v₂→v₅), v₃ → 의미 없음 (자기자신이거나 무효경로)
• 그대로 유지: D⁽²⁾[2][5] = D⁽¹⁾[2][5] = 14, D⁽³⁾[2][5] = 14

Step 4: v₄를 중간 정점으로 추가

• 후보 경로 3가지:
  1. D⁽³⁾[2][5] = 14 (이전 값 유지)
  2. v₂ → v₄ → v₅ → 2 + 3 = 5
  3. v₂ → v₁ → v₄ → v₅ → 9 + 1 + 3 = 13
  4. v₂ → v₃ → v₄ → v₅ → 3 + 4 + 3 = 10

Step 5: 모든 정점 허용

• 추가 정보 없음 → 최단 거리 그대로 유지

- Time complexity: O(n^3)

- Space complexity: O(n^2) #가능한 모든 정점 쌍은 n × n = n²개, 즉 2차원 행렬이 필요.

---

Example 8. 0-1 Knapsack Problem (배낭 문제)

- Given weights and profits of items, find the maximum profit we can carry without exceeding the weight limit.

- 무게 제한이 있는 배낭에, 가치(value) 와 무게(weight) 가 정해진 물건들을 최대한 가치 있게 넣는 방법을 찾는 문제.

( 단, 각 물건은 한 번만 넣을 수 있고(0 또는 1), 반쯤 자르거나 나눠서 넣을 수는 없습니다. )

 

1. DP 테이블 만들기

• 행: 물건 개수 + 1
• 열: 가능한 배낭 무게 0부터 W까지

K[i][w] = 앞에서 i번째 물건까지 고려했을 때,
          무게가 w일 때 만들 수 있는 최대 가치

2. 점화식 (Recurrence Relation)

if wt[i-1] <= w:
    K[i][w] = max(
        K[i-1][w],                    # 현재 물건을 안 넣음
        K[i-1][w - wt[i-1]] + val[i-1]  # 현재 물건을 넣음
    )
else:
    K[i][w] = K[i-1][w]  # 무게 초과라서 못 넣음

3. pack 과정: 실제 물건 넣는 순서 구하기

DP 테이블이 다 채워졌다면, 역추적을 통해 무엇을 넣었는지 확인:

1. i = n, w = W부터 시작
2. 아래 조건을 만족하면, i번째 물건을 넣었다고 판단
3. 물건을 넣었다면:
   • w = w - wt[i-1] 로 줄여줌 (남은 공간 계산)
   • i = i - 1
4. 반복

K[i][w] ≠ K[i-1][w]  
→ 무언가 바뀐 경우 = 물건 i가 포함됨

 

---

• 행(i): 물건 번호 (0부터 시작)
  • i = 0: 아직 아무 물건도 고려하지 않은 상태 → 모든 값은 0
  • i = 1: 1번 물건(5kg, 10만원)을 고려
  • i = 2: 1번, 2번 물건까지 고려 (4kg, 40만원 포함)
  • i = 3: 1~3번 물건까지 고려 (6kg, 30만원 포함)
  • i = 4: 모든 물건 고려 완료 (4번: 3kg, 50만원)
• 열(w): 배낭의 현재 무게 한도 (0kg부터 10kg까지)
  • w = 0: 배낭이 아무것도 담을 수 없음 → 항상 0
  • w = 5: 최대 5kg까지 물건을 담을 수 있음
  • w = 10: 배낭 최대 용량 → 우리가 구하고자 하는 해답

각 칸 K[i][w]의 의미
i번째 물건까지 고려했을 때, 배낭 무게가 w일 경우 가능한 최대 총 가치

i = 1 (1번 물건만 고려) 의 경우
물건 1: 무게 5kg, 가치 10
- w < 5 담을 수 없음
- w ≥ 5 담을 수 있으므로 가치 10

i = 2 (물건 1, 2 고려) 의 경우
물건 2: 무게 4kg, 가치 40 예: K[2][9] = max(K[1][9], K[1][5] + 40) = max(10, 10 + 40) = 50
→ 이 칸은 물건 1(5kg, 10)과 물건 2(4kg, 40)를 둘 다 넣을 수 있는 조합임

i = 3 (물건 1~3 고려) 의 경우
물건 3: 무게 6kg, 가치 30 예: K[3][10] = max(K[2][10], K[2][4] + 30) = max(50, 40 + 30) = 70
→ 무게 10kg에 2번(4kg, 40) + 3번(6kg, 30) 넣은 조합이 최적

i = 4 (모든 물건 고려) 의 경우
물건 4: 무게 3kg, 가치 50 예: K[4][10] = max(K[3][10], K[3][7] + 50) = max(70, 40 + 50) = 90
→ 최종 해답: 배낭에 무게 10kg 채우면 최대 가치 90

K[4][7]: 4번 물건(3kg, 50)을 넣고, 남은 공간 4kg에 2번 물건(4kg, 40) 을 함께 넣음.

 

#Pseudo-code

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    return K[n][W]

 

- Time complexity: O(nW)

- Space complexity: O(nW)

• n: 물건의 개수
• W: 배낭이 수용할 수 있는 최대 무게 (정수값)

---