[알고리즘] Dynamic programming - Fibonacci number, Floyd-Warshall algorithm

다이나믹 프로그래밍: 중복 계산을 피하는 지혜

다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장해두었다가 재활용하는 알고리즘 설계 기법이다. 분할 정복 알고리즘과 유사하지만, 중복되는 부분 문제들을 저장하고 재사용한다는 점에서 큰 차이가 있다. 이러한 특징을 가장 잘 보여주는 예시가 바로 피보나치 수열이다.

피보나치 수열 계산: 재귀 vs 다이나믹 프로그래밍

피보나치 수열은 다음과 같은 점화식으로 정의된다.

F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

재귀 함수를 이용한 구현

피보나치 수열을 재귀 함수로 구현하면 다음과 같다.

Python
def fibonacci(n):
  if n == 0 or n == 1:
    return 1
  return fibonacci(n-1) + fibonacci(n-2)

이 코드는 fibonacci(n)을 계산하기 위해 fibonacci(n-1)과 fibonacci(n-2)를 호출하는 방식으로 작동한다. 하지만 이러한 방식은 중복 계산을 야기한다. 예를 들어, fibonacci(4)를 계산하기 위해 fibonacci(3)과 fibonacci(2)를 호출하고, fibonacci(3)을 계산하기 위해 다시 fibonacci(2)를 호출하게 된다.

이러한 중복 계산으로 인해 시간 복잡도는 지수적으로 증가하게 된다. fibonacci(n)을 계산하기 위한 호출 횟수는 대략 $O (ϕ^{n})$ 에 비례하며, 여기서 $ϕ=$(1+sqrt(5))/2$$ 는 황금비이다.

Recursive function for computing Fibonacci Number

위 그래프에서 볼 수 있듯이, n이 커짐에 따라 계산 시간이 급격하게 증가하는 것을 확인할 수 있다.

다이나믹 프로그래밍을 이용한 구현

다이나믹 프로그래밍을 이용하면 이러한 중복 계산을 피할 수 있다. 메모이제이션 (memoization)이라는 기법을 사용하여 이미 계산된 결과를 저장해두고 재활용하는 것이다.

Python
def faster_fibonacci(n):
  F = [1, 1] + [None] * (n - 1)  # 길이 n의 리스트 F 생성
  for i in range(2, n + 1):
    F[i] = F[i-1] + F[i-2]
  return F[n]

이 코드는 길이 n + 1의 리스트 F를 생성하고, F[i]에 fibonacci(i)의 값을 저장한다. F[0]과 F[1]은 1로 초기화하고, i = 2부터 n까지 반복문을 통해 F[i]를 계산한다. 이때, F[i-1]과 F[i-2]는 이미 계산되어 리스트 F에 저장되어 있으므로, 중복 계산 없이 F[i]를 구할 수 있다.

이러한 방식을 사용하면 시간 복잡도는 $O (n)$ 으로 줄어든다. 반복문을 통해 F[2]부터 F[n]까지 n - 1번의 계산만 수행하면 되기 때문이다.

DP for computing Fibonacci Number

위 그래프에서 볼 수 있듯이, 다이나믹 프로그래밍을 사용하면 n이 커지더라도 계산 시간이 선형적으로 증가하는 것을 확인할 수 있다.

피보나치 수열 계산 예시를 통해 다이나믹 프로그래밍이 중복 계산을 효과적으로 줄여 알고리즘의 성능을 향상시키는 것을 확인하였다. 이제, 다이나믹 프로그래밍을 활용한 구체적인 알고리즘에 대해 자세히 알아보며 이해해보자.

Floyd-Warshall 알고리즘: 모든 지점 간 최단 경로 구하기

Floyd-Warshall 알고리즘은 모든 쌍 최단 경로 (All Pairs Shortest Paths, APSP) 문제를 해결하는 다이나믹 프로그래밍 알고리즘이다. 즉, 그래프 내의 모든 정점 쌍 $(u, v)$ 에 대해 $u$ 에서 $v$ 까지의 최단 경로를 찾아낸다. 이전에 살펴본 Dijkstra 알고리즘이나 Bellman-Ford 알고리즘이 특정 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 것과는 차이가 있다.

APSP를 위한 효율적인 접근

모든 정점 쌍에 대한 최단 경로를 찾기 위해 모든 정점에 대해 Bellman-Ford 알고리즘을 적용하는 방법을 생각해 볼 수 있다. 하지만 이 경우 시간 복잡도는 $ $O(n^2m)$$ 이 되며, 최악의 경우 $( $m = n^^{2}$ )$에는 $ $O(n^4)$$ 까지 증가할 수 있다. Floyd-Warshall 알고리즘은 이러한 문제를 해결하기 위해 고안된 더 효율적인 알고리즘이다.

Floyd-Warshall 알고리즘의 작동 방식

Floyd-Warshall 알고리즘은 다음과 같은 점화식을 기반으로 작동한다.

Floyd-Warshall recurrence relation

여기서 $D^{(} k) [u, v]$ 는 정점 $u$ 에서 $v$ 까지의 경로 중 $1$ 부터 $k$ 까지의 정점만을 사용하는 최단 경로의 비용을 나타낸다. 즉, $k$ 를 증가시키면서 점차적으로 더 많은 정점을 경유지로 허용하면서 최단 경로를 갱신해 나가는 것이다.

초기 조건: $D^{(} 0) [u, v]$ 는 $u$ 와 $v$ 사이의 간선 가중치 (존재하지 않는 경우 무한대)로 초기화한다.
점화식: 위의 점화식을 이용하여 $k = 1$ 부터 $n$ 까지 반복적으로 $D^{(} k)$ 를 계산한다.
결과: 최종적으로 $D^{(} n)$ 이 모든 정점 쌍에 대한 최단 경로 비용을 담고 있는 행렬이 된다.

다이나믹 프로그래밍: 중복 계산 방지

Floyd-Warshall 알고리즘은 다이나믹 프로그래밍의 핵심 요소인 중복되는 부분 문제와 최적 부분 구조를 활용한다.

$D^{(} k) [u, v]$ 를 계산하기 위해 이전 단계에서 계산된 $D^{(} k - 1)$ 값들을 재사용한다. 이는 중복되는 부분 문제를 효율적으로 처리하는 방법이다.
$u$ 에서 $v$ 까지의 최단 경로는 $u$ 에서 $k$ 까지의 최단 경로와 $k$ 에서 $v$ 까지의 최단 경로를 합쳐서 구할 수 있다. 이는 최적 부분 구조를 활용하는 것이다.

또한, 각 부분 문제는 서로 독립적이다. 즉, 하나의 부분 문제의 해답이 다른 부분 문제의 해답에 영향을 미치지 않는다. 이러한 독립성은 다이나믹 프로그래밍을 적용하기 위한 중요한 조건이다.

결과적으로 Floyd-Warshall 알고리즘은 3중 반복문을 사용하여 $D^{(} k)$ 를 계산하기 때문에 시간 복잡도는 $ $O(n^3)$$ 이다. 이는 모든 정점에 대해 Bellman-Ford 알고리즘을 수행하는 것보다 훨씬 효율적이다.

마무리

오늘은 다이나믹 프로그래밍(DP)이라는 새로운 개념에 대해 배워보았다. 그리고 피보나치 수를 계산하는 사례, Floyd-Warshall 알고리즘을 통해 DP의 효율성을 이해할 수 있었다. DP는 메모이제이션이라는 핵심 기법을 통해 중복되는 부분 문제를 효과적으로 처리하고, 최적 부분 구조를 활용하여 재귀 함수보다 훨씬 효율적으로 계산할 수 있다. 하지만 점화식을 찾는 과정이 까다롭기에, 다음 시간에도 이어서 DP 알고리즘에 대해 알아보고자 한다.

추천글:

[알고리즘] Bellman-Ford algorithm의 모든 것 - definition, example, correctness, time complexity
(https://hyeondev.blogspot.com/2024/11/bellman-ford-algorithm-definition.html)

[알고리즘] Dijkstra algorithm의 모든 것 - definition, example, correctness, time complexity
(https://hyeondev.blogspot.com/2024/11/dijkstra-algorithm-definition-example.html)

[알고리즘] Graph algorithm - Breadth First Search

(https://hyeondev.blogspot.com/2024/10/graph-algorithm-breadth-first-search.html)