1. Introduction
최단 경로를 구하는 문제는, 다양한 알고리즘 중에서도 단연 핵심적이고 중요하다. 차량용 네비게이션에서 목적지까지 가장 빠르게 도달할 수 있는 경로를 찾거나, 모바일 로봇의 모션 계획을 수립하는 등 다양한 애플리케이션에 활용될 수 있다. 본 글에서는 유형 별로 최단 경로를 구하는 다양한 알고리즘에 대해 살펴보고, 해당 알고리즘의 정합성과 효율성에 대해 고찰해보도록 하겠다.

2. 최단 경로의 정의 (Definition of Shortest Path)
(1) Edge-weight function
점(Vertices)들의 집합 V와 가중된 간선(Weighted Edges)들의 집합 E로 이루어진 유향 그래프(Directed Graph) G = (V, E)에서, k개의 점으로 이루어진 경로 p = v₁ → v₂ → ... → v_k의 Weight는 w(p)라고 정의하며, 이를 수식으로 표현하면 (2.1)과 같다.
예를 들어, Figure 2.1는 w(p) = -2인 경우이다.

(2) Shortest Path
점 u에서 v에 이르는 최단 경로는 w(p)가 최소인 경로 p이다. 이때, u에서 v에 이르는 최단 경로의 Weight를 (2.2)와 같이 정의한다. 단, u에서 v에 이르는 경로가 없을 경우에는, δ(u, v) = ∞로 정의한다.

(3) Optimal Substructure
Theorem. 특정 최단 경로 내에 포함된 부분 경로(Subpath)는 반드시 최단 경로이다.
Proof.
Figure 2.2에서 v₁에서 v₆에 이르는 실선의 간선들이 최단 경로를 이룬다고 가정하자. 만약, 사각형 안의 v₂에서 v₅에 이르는 최단 경로가 점선의 간선일 경우, 즉, 실선의 간선들이 최단 경로를 이루지 않는 경우, v₁에서 v₆에 이르는 실선의 간선들이 최단 경로를 이룬다는 가정에 모순된다.

(4) Triangle Inequality
Theorem. 그래프에 속한 모든 점 u, v, x에 대해, (2.3)이 성립한다.
Proof. δ(u, v) > δ(u, x) + δ(x, v)라고 가정하자. u에서 x를 거쳐 v로 가는 최단 경로의 Weight는 δ(u, x) + δ(u, v)이다. 그런데, 이는 δ(u, v)보다 작다. 즉, u에서 v로 가는 최단 경로의 Weight가 δ(u, v)보다 작으므로 모순이다.

(5) Well-definedness of Shortest Paths
그래프에 포함된 특정 점 v에서 출발하여 v로 다시 돌아오는 경로 p가 존재하고, 이때 w(p) < 0인 경우를 Negative-weight Cycle이라고 정의한다. 만약, 그래프 내에 Negative-weight Cycle이 한 개 이상 존재한다면, 최단 경로가 존재하지 않을 수도 있다. Negative-weight Cycle을 순회할 때마다 w(p)가 무한히 감소하기 때문이다.

3. 최단 경로 구하기 문제의 유형 (Shortest Path Variants)
출발점과 도착점의 개수에 따라 최단 경로 구하기 문제의 유형이 나뉘게 되고, 유형 별로 상이한 알고리즘들이 사용된다. 총 네 가지의 유형이 있는데, 이는 다음과 같다.

(1) Single-source: 하나의 점 s가 주어졌을 때, s에서 나머지 모든 점에 이르는 최단 경로를 구하는 것
(2) Single-destination: 임의의 여러 점으로부터 하나의 점 v에 이르는 최단 경로를 구하는 것
(3) Single-pair: 한 쌍의 점을 각각 출발점과 도착점으로 하는 최단 경로를 구하는 것
(4) All-pairs: 그래프 내의 가능한 모든 쌍의 점들에 대해 최단 경로를 구하는 것

이 중에서 Single-destination 문제는 Single-source 문제를 거꾸로 생각하면 같은 문제라고 할 수 있다. 또한 Single-pair 문제는 Single-source 문제의 일부에 해당한다. 따라서, Single-source와 All-pairs 문제를 중점적으로 다루도록 하겠다.

3-1. Single-source Shortest Paths
모든 점들의 집합 V에 속하는 한 점 s가 출발점으로 주어졌을 때, V에 속하는 모든 점 v에 대해 δ(s, v)를 구한다. 이때, 간선의 가중치는 양수일 수도 있고, 음수일 수도 있는데, 모든 간선의 가중치가 양수인 경우와 그렇지 않은 경우로 나누어서 살펴보도록 하자.

3-1-1. 모든 간선의 가중치가 양수인 경우
앞에서 언급했듯이, Negative-weight Cycle이 존재하지 않는다면 최단 경로는 반드시 존재한다. 따라서, 모든 간선의 가중치가 양수인 경우, 반드시 최단 경로를 구할 수 있다. 이때, 최단 경로를 구하는 방법에 대한 아이디어는 다음과 같이 Greedy Algorithm의 개념을 활용하는 것이다.

i. 출발점 s로부터 특정 점 v까지의 최단 경로를 안다고 가정할 때, v들의 집합을 S라고 한다.
ii. 매번 v ∈ V-S를 만족하면서 S에 인접한 점 v들 중에서, s에서 v에 이르는 경로가 가장 짧은 v를 채택하여 S에 포함시킨다.
iii. 채택된 v에 인접한 점들의 거리 정보를 갱신한다.

(1) Dijkstra's Algorithm
이 로직은 1956년에 Edsger Wybe Dijkstra가 고안한 알고리즘으로, Dijkstra's Algorithm이라고 불린다. s ∈ V를 만족하는 하나의 출발점 s에서 v ∈ V를 만족하는 모든 점 v에 이르는 각 최단 경로의 길이를 구한다. 이 알고리즘을 의사 코드(Pseudo Code)로 나타내면 다음과 같다.

d[s] ← 0
for each v ∈ V - {s}
  do d[v] ← ∞
S ← ∅
Q ← V
while Q ≠ ∅
  do u ← EXTRACT_MIN(Q)
    S ← S ∪ {u}
    for each v ∈ Adj[u]
      do if d[v] > d[u] + w(u, v)
        then d[v] ← d[u] + w(u, v)

이때, d[v] = δ(s, v)이고, Q는 V - S를 포함하는 우선순위 큐(Priority Queue)이며, Adj[u]는 점 u에 인접한 점들을 의미한다. 그리고 특정 점 u가 집합 S에 포함될 때 u에 인접한 점 v들의 d[v] 값들을 d[u] + w(u, v)와 비교하여 더 작은 값으로 갱신하게 되는데, 이 과정을 "간선 (u, v)를 Relax한다"고 표현한다.

(2) 정합성 검증 (Correctness)
Lemma. d[s]를 0으로, d[v]를 ∞로 초기화하는 것은 그래프 내의 모든 점 v에 대해 d[v] ≥ δ(s, v)를 만족하게 만들고, d[v]의 값을 갱신하더라도 이 성질이 유지된다.
Proof. 만약 이것이 거짓이라고 가정해보자. 점 v가 d[v] < δ(s, v)가 되게 만드는 첫 번째 점이라고 가정하고, 점 u가 d[v]값을 d[u] + w(u, v)로 갱신하게 만드는 점이라고 가정하자. 이를 통해 유추하면, 점 u에 대해 d[u] ≥ δ(s, u)를 만족한다. 그런데, Triangle Inequality를 활용하여 생각해보면 다음과 같은 모순이 발생한다.

d[v] < δ(s, v)
      ≤ δ(s, u) + δ(u, v)
      = δ(s, u) + w(u, v)
      ≤ d[u] + w(u, v)

Lemma. s에서 v에 이르는 최단 경로 상에서 점 u가 v의 이전에 위치한다고 가정해보자. 그렇다면, 만약 d[u] = δ(s, u)이고 간선 (u, v)가 Relax되었을 경우, d[v] = δ(s, v)임을 만족한다.
Proof. 가정에 의하면, δ(s, v) = δ(s, u) + w(u, v)이다. 이때, d[v] > δ(s, v)라고 가정하면 d[v] > d[u] + w(u, v)가 성립한다. 왜냐하면 d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)이기 때문이다. 그러므로, 해당 Dijkstra's Algorithm은 d[v] = d[u] + w(u, v) = δ(s, v)로 d[v] 값을 갱신하게 된다.

Theorem. Dijkstra's Algorithm은 반드시 V에 속한 모든 점 v에 대해 d[v] = δ(s, v)인 상태로 종료된다.
Proof. 알고리즘이 진행되면서 집합 S에 v를 추가할 때마다 d[v] = δ(s, v)임을 보장하므로, 참임을 쉽게 알 수 있다.
Figure 3.1처럼 만약 어떤 점 u가 d[u] > δ(s, u)인 상태로 집합 S에 추가된 첫 번째 점이라고 가정하고, 점 s에서 u에 이르는 최단 경로를 p라고 하자. 추가적으로, 점 y는 아직 집합 S에 포함되지 않은 점들 중에서 경로 p상에 위치한 첫 번째 점이고, 점 x는 경로 p상에서 y에 선행하는 점이라고 가정하자. 이때, 점 u가 d[u] = δ(s, u)를 위반하는 첫 번째 점이므로, d[x] = δ(s, x)이다. x가 집합 S에 포함될 때는 간선 (x, y)가 Relax되었을 것이고, 이는 d[y] = δ(s, y) ≤ δ(s, u) < d[u]임을 암시한다. 그러나, 처음에 집합 S에 점 y보다 u를 먼저 포함시켰다는 것은 d[u] ≤ d[y]임을 의미하므로 모순이다.

(3) 시간 복잡도 (Time Complexity)
Dijkstra's Algorithm의 시간 복잡도는 우선순위 큐로부터 V개의 점을 하나씩 추출하는 과정과, E개의 각 간선을 Relax하는 과정을 수행할 때의 소요 시간을 합산한 것으로 요약할 수 있다.
큐로부터 점 하나를 추출하는데 소요되는 시간을 T(EXTRACT_MIN)이라고 하고, Relaxation 과정에서 점의 d 값을 변경하고 큐 자료구조를 정비하는데 소요되는 시간을 T(DECREASE_KEY)라고 하자. 이 두 시간은 사용되는 자료구조의 종류에 따라 상이하다. Table 3.1은 자료구조별 시간복잡도를 빅 오 표기법(Big O Notation)으로 요약한 것이다.

3-1-2. 간선에 가중치가 없는 경우
모든 간선에 가중치가 없는 경우는 (u, v) ∈ E인 모든 간선 (u, v)에 대하여 w(u, v) = 1인 경우와 동치이다. 즉, 모든 간선의 가중치가 동일하기 때문에 우선순위 큐를 사용할 필요가 없다.

(1) Breadth-first Search (BFS)
단순히 기본적인 선입선출(First in, first out, 줄여서 FIFO)의 큐를 사용한다. 초기화 과정은 이전의 알고리즘과 동일하지만, 출발점 s만 먼저 큐에 삽입한 뒤 시작하는 점에 차이가 있다. 매번 큐로부터 꺼낸 특정 점 u에 인접한 점들 중 d 값이 갱신되지 않은 점들을 찾아 d[u] + 1로 값을 변경하고 큐에 삽입한다. 최종 결과는 점 s에서 집합 V - {s}에 속한 모든 점들에 도달하기까지 거쳐야 하는 최소 간선의 개수, 즉, 최단 경로가 된다. 이 알고리즘을 의사 코드로 나타내면 다음과 같다.

d[s] ← 0
for each v ∈ V - {s}
  do d[v] ← ∞
ENQUEUE(Q, s)
while Q ≠ ∅
  do u ← DEQUEUE(Q)
    for each v ∈ Adj[u]
      do if d[v] = ∞
        then d[v] ← d[u] + 1
               ENQUEUE(Q, v)

(2) 정합성 검증 (Correctness)
Idea. BFS에서의 선입선출 큐는 Dijkstra's Algorithm에 사용된 우선순위 큐의 동작을 모방한다.
Invariant. 선입선출 큐의 특성에 의해 점 v가 큐에서 점 u보다 먼저 추출되었다면, d[v] = d[u]이거나 d[v] = d[u] + 1임을 암시한다.

(3) 시간 복잡도 (Time Complexity)
선입선출 큐는 T(EXTRACT_MIN) = O(1), T(DECREASE_KEY) = O(1)이므로, 이를 반영하면 시간 복잡도는 Θ(V + E)이다.

3-1-3. Negative-weight cycle이 존재할 수 있는 경우
만약 어떤 그래프 G = (V, E)가 Negative-weight Cycle을 포함한다면, 최단 경로를 구하지 못할 가능성이 있다는 것을 앞서 Well-definedness of Shortest Paths에서 살펴보았다. 이러한 경우, Negative-weight Cycle이 그래프 내에 존재하는지 탐지할 수 있는 알고리즘이 필요하다.

(1) Bellman-Ford Algorithm
Dijkstra's Algorithm과 마찬가지로, s ∈ V인 하나의 출발점에서 v ∈ V인 모든 점 v에 이르는 각 최단경로의 길이를 구한다. 그리고, 그래프 내의 Negative-weight Cycle의 존재유무를 판단한다. 이 알고리즘을 의사 코드로 나타내면 다음과 같다.

d[s] ← 0
for each v ∈ V - {s}
  do d[v] ← ∞
for i ← 1 to |V| - 1
  do for each edge (u, v) ∈ E
    do if d[v] > d[u] + w(u, v)
      then d[v] ← d[u] + w(u, v)
for each edge (u, v) ∈ E
  do if d[v] > d[u] + w(u, v)
    then report that a negative-weight cycle exists

Bellman-Ford Algorithm은 Dijkstra's Algorithm과 달리 큐를 사용하지 않는다. Dijkstra's Algorithm에서는 큐로부터 추출한 특정 점에 인접한 간선들만 Relax를 했지만, Bellman-Ford Algorithm의 경우에는 모든 간선에 대해 Relax를 시도한다. Dijkstra's Algorithm은 Greedy Algorithm에 속하고, Bellman-Ford Algorithm은 Dynamic Programming에 속한다.
만약 |V| - 1회의 Iteration 후에도 d[v] 값들이 수렴하지 않는다면, 출발점 s에서 도달할 수 있는 Negative-weight Cycle이 그래프 내에 존재한다는 의미가 된다. 이를 통해 Negative-weight Cycle의 존재 여부를 탐지할 수 있다.

(2) 정합성 검증 (Correctness)
Theorem. 만약 그래프 G = (V, E)가 Negative-weight Cycle을 포함하지 않는 경우, Bellman-Ford Algorithm은 수행이 완료된 후 모든 점 v ∈ V에 대해 d[v] = δ(s, v)를 만족한다.
Proof. v ∈ V인 특정 점 v에 대해 출발 점 s에서 v에 이르는 최단 경로들 중에서 경로 상에 포함된 간선 수가 최소인 경로를 p라고 가정하자.
Figure 3.2에서 간선 (v_i-1, v_i)는, 총 |V| 번의 Iteration 중 적어도 i번째에서 Relax될 것임을 알 수 있다. 그리고 p가 최단 경로이기 때문에, δ(s, v_i) = δ(s, v_i-1) + w(v_i-1, v_i)를 만족한다.
좀 더 상세히 설명하자면, 초기 상태에서는 d[v₀] = 0 = δ(s, v₀)이고, d[v] ≥ δ(s, v)를 만족해야 하기 때문에, 이어지는 Relaxation 과정에서 d[v₀]는 변하지 않는다.
그런데, E에 속한 모든 간선에 대해 한 번씩 훑으며 Relaxation을 하는 것을 한 번의 Iteration이라고 했을 때, 첫 번째 Iteration에서 d[v₁] = δ(s, v₁)이 된다. 또, 두 번째 Iteration에서는 d[v₂] = δ(s, v₂)가 된다. 같은 방법으로, k 번째 Iteration에서는 d[v_k] = δ(s, v_k)가 된다.
그래프 G가 Negative-weight Cycle을 포함하지 않기 때문에 p는 단순 경로(Simple Path)가 된다. 가장 긴 단순 경로에 포함된 간선의 수는 |V| - 1보다 같거나 작다.

(3) 시간 복잡도 (Time Complexity)
Time = O(VE)
의사 코드에 의하면, 집합 E에 포함된 모든 간선을 Relax하는 과정을 |V| - 1회 반복하므로, 시간 복잡도는 O(VE)이다.

3-2. All-pairs Shortest Paths
모든 가능한 점의 쌍에 대해 최단 경로를 구하는 것은 Dijkstra's Algorithm을 |V|회 수행하면 된다. 이때, 시간 복잡도는 대략 O(VE + V²lgV)이다. 하지만, 그래프 내에 Negative-weight Cycle이 존재한다면 이 알고리즘을 사용하지 못할 것이다. 만약 그래프 내에 속한 모든 점에 대해 Bellman-Ford Algorithm을 사용한다면 시간 복잡도는 O(V²E)가 된다. 게다가, 그래프에 포함된 점의 개수가 n이라고 할 때, 간선의 개수가 n² 정도인 고밀도 그래프(Dense Graph)의 경우, 시간 복잡도는 Θ(n⁴)가 된다. 따라서 이러한 방법들 외에 어떤 효율적인 알고리즘들을 사용할 수 있는지 살펴보도록 하자.

(1) Definition of All-pairs Shortest Paths Problem
Input. 유향 그래프 G = (V, E)와 u ∈ V, v ∈ V일 때 G에 속한 모든 간선에 대한 Edge-weight Function w(u, v)가 주어진다. 이때, V = {1, 2, ..., n}이다.
Output. n x n 크기의 행렬을 결과로 도출해내며, i행 j열의 원소는 i, j ∈ V인 점 i에서 점 j에 이르는 최단경로의 길이 δ(i, j)를 나타낸다.

(2) Dynamic Programming
All-pairs Shortest Paths 문제는 Dynamic Programming의 관점에서 해결할 수 있다. n 개의 점을 포함한 유향 그래프를 나타내는 n x n 크기의 인접 행렬을 A = (a_ij)라고 정의하고, 점 i에서 출발하여 점 j에 도달할 때 최대 m 개의 간선을 사용하여 이루어지는 최단 경로의 가중치 값을 d_ij(m)이라고 정의하자.
그렇다면 Dynamic Programming을 위한 점화식은 (3.2)가 되며, 초기값은 (3.1)이 된다.
Proof. (3.2)의 최소값을 구하는 과정을 다음과 같이 의사 코드로 나타낼 수 있다.

for k ← 1 to n
  do if d_ij > d_ik + a_kj
    then d_ij ← d_ik + a_kj

이는 앞서 언급된 최단 경로 구하기 알고리즘들과 동일하게, Relaxation 과정을 거친다고 할 수 있다. 즉, 출발점 i와 도착점 j 사이에 위치한 모든 점 k들(i와 j도 포함)을 조사하여, k를 거쳐가는 최단 경로들 중 가장 짧은 최단 경로를 채택하므로, 알고리즘의 결과인 δ(i, j)는 반드시 최단 경로의 길이를 나타낸다고 할 수 있다.
Note. 만약 그래프 내에 Negative-weight Cycle이 존재하지 않는 경우, δ(i, j) = d_ij(n - 1) = d_ij(n) = d_ij(n + 1) = ⋯을 만족한다. 단순 경로에 포함된 최대 간선의 수는 n - 1이기 때문에, 최단 경로에 포함될 수 있는 최대 간선의 수를 n - 1 이상으로 증가시켜도 d_ij(m)의 값은 변경되지 않을 것이다. 당연하게도, 경로 상에 Negative-weight Cycle이 존재할 경우, 경로 상에 포함되는 간선의 수를 증가시킬 때마다 d_ij(m)의 값은 점차적으로 감소하게 된다.

(3) Matrix Multiplication Algorithm
n x n 크기의 행렬 A, B, C에 대해 C = A ⋅ B를 계산하는 과정은 (3.3)과 같다. 이 연산을 수행하기 위한 시간 복잡도는 기본적으로 Θ(n³)이다.
만약 (3.3)의 연산 중 "+"를 "min"으로, "⋅"를 "+"로 치환하면 (3.4)가 된다. 이는 (3.2)를 행렬의 곱셈 연산 문제로 바꾸는 초석이 된다.
임의의 점 i, j에 대해 d_ij(m) 값들의 집합을 행렬로 표현한 것을 D(m)라고 정의하고, (3.4)의 연산을 새로운 Matrix Multiplication "x"라고 정의하면, (3.1)과 (3.2)는 각각 (3.5)와 (3.6)으로 재정의할 수 있다.
"min"과 "+" 연산은 결합법칙이 성립한다. 따라서, 다음과 같은 성질을 관찰할 수 있다.

D(1) = D(0) ⋅ A = A¹
D(2) = D(1) ⋅ A = A²
:
D(n - 1) = D(n - 2) ⋅ A = A^n-1

따라서, 결과적으로 D(n - 1) = (δ(i, j)) = A^n-1이 성립함을 알 수 있다. 이때, 행렬 곱셈 연산을 n 번하는 것과 마찬가지이므로, 시간 복잡도는 Θ(n ⋅ n³) = Θ(n⁴)이다. 이는 Bellman-Ford Algorithm을 n 개의 점에 대해 한 번씩 수행하는 것과 차이가 없다. 그러나, 기본적인 행렬 곱셈 연산이 아닌, 효율적인 행렬 곱셈 연산 알고리즘들을 적용한다면, 시간 복잡도를 대략 Θ(n³lgn) 정도로 줄일 수 있다.
만약, Negative-weight Cycle의 존재 여부를 탐지하고자 한다면, 행렬 D(n - 1)의 대각선 원소들을 검사하여 음수 값이 존재하는지 판단하면 된다. 특정 점에서 출발하여 자기자신으로 다시 돌아오는데, 가중치가 음수라면, Negative-weight Cycle이 존재하는 것이기 때문이다. 이때, 행렬의 대각선을 검사하는데 O(n)의 시간이 추가적으로 소요된다.

(4) Floyd-Warshall Algorithm
Floyd-Warshall Algorithm은 Matrix Multiplication Algorithm과 같이 Dynamic Programming을 응용한 알고리즘이지만, 상대적으로 속도가 더욱 빠르고 구현이 쉽다. 특정 점 i에서 출발하여 점 j에 도달하고자 할 때, 중간에 거쳐가는 점은 집합 {1, 2, ..., k}에 속하는 점들로 제한한다. 이때의 최단 경로의 길이를 c_ij(k)라고 정의한다. 예를 들어, c₁₅(3)은 점 1에서 출발하여 점 4는 거치지 않고 점 1, 2, 3 중 임의의 점들을 거쳐서 점 5에 도달하는 최단 경로의 길이를 의미한다. 따라서, c_ij(0) = a_ij이고 δ(i, j) = c_ij(n)이다.
c_ij(k) 값들을 구하기 위한 Dynamic Programming의 점화식은 (3.7)이다.
(3.7)을 그림으로 표현하면 Figure 3.4와 같다. k보다 인덱스가 작은 점들만을 거친 최단 경로와 점 k를 거친 최단 경로를 비교하여, 길이가 더 작은 최단 경로를 채택한다. 이를 의사 코드로 표현하면 다음과 같다.

for k ← 1 to n
  do for i ← 1 to n
    do for j ← 1 to n
      do if c_ij > c_ik + c_kj
        then c_ij ← c_ik + c_kj

Iteration 과정에서 k가 증가하면서 c_ij(k)가 c_ij(k - 1) 값을 덮어씌우지만, c_ij(k)는 c_ij(k - 1)을 포함하는 개념이기 때문에 문제되지 않는다. 따라서, c_ij(k)를 3차원 행렬이 아니라, k를 고려하지 않은 2차원 행렬 (c_ij)로 구현하여도 문제없다.
의사 코드에 의하면 n 개의 점에 대해 3중 반복문을 통해 Iteration이 이루어지기 때문에 시간 복잡도는 Θ(n³)이다.

4. Conclusion
최단 경로 문제는 유형에 따라, 그리고 그래프의 형태나 간선의 특징에 따라 다양한 알고리즘들이 사용된다. Table 4.1과 Table 4.2는 앞서 살펴본 알고리즘들의 대략적인 시간 복잡도를 요약한 것이다. 최단 경로 문제가 주어졌을 때, 문제의 유형을 잘 파악한 뒤 적절한 알고리즘을 선택하는 것이 관건이다.

5. Source Code
https://github.com/arkainoh/algorithms/blob/master/c/GraphDijkstra.c
https://github.com/arkainoh/algorithms/blob/master/c/GridDijkstra.c
https://github.com/arkainoh/algorithms/blob/master/c/GraphBFS.c
https://github.com/arkainoh/algorithms/blob/master/c/GridBFS.c
https://github.com/arkainoh/algorithms/blob/master/c/BellmanFord.c
https://github.com/arkainoh/algorithms/blob/master/c/FloydWarshall.c

6. References
Introduction to Algorithms, 3ed, Cormen et al. and lecture notes of Demaine and Leiserson

1. 개요
나이브 베이즈 분류(Naive Bayes Classification, 이하 NBC)는 가장 기본적이면서 자주 쓰이는 매우 유용한 분류 방법이다. 예제와 함께 나이브 베이즈 분류의 개념과 특징을 알아보고, 한계와 극복 방안, 그리고 활용 사례에 대해 살펴보도록 하겠다.

2. NBC의 기본 가정 및 방법
NBC의 기본적인 가정은, 어떤 객체의 속성들이 서로 독립적이라는 것이다. 예를 들어, 분류해야 할 객체 x의 정보가 벡터로 주어진다면, 각 벡터의 요소들은 x의 속성들이라고 할 수 있으며 이들은 모두 독립적이다. 쉽게 말해서, 인간이라는 객체의 속성을 키와 몸무게라고 가정했을 경우 키와 몸무게가 상호 독립적이라고 가정하는 것이다.
이러한 가정에 의해, x가 주어졌을 때 특정 클래스 C_k로 분류하는 NBC는 다음과 같이 진행할 수 있다.
즉, P(x₁x₂x₃...x_n | C_k)를 P(x_i | C_k)들의 곱이라고 생각한다. 각 요소들의 Class Likelihood를 전부 곱해버리는 것이다. 우선, NBC를 진행하기 전 학습 과정을 의사 코드(Pseudocode)로 나타내면 다음과 같다.
이때 r은 One-hot Encoded Vector이다. 예를 들어, 주어진 데이터 x가 두 번째 클래스(C2)에 속한다는 것을 나타내는 r은 [0 1 0]이다. 따라서, 이 정보를 활용하여 데이터 D가 주어졌을 때, 우선 각 클래스마다 데이터가 몇 개 속해있는지 카운트하여 (1)의 Priority Probability를 구한다. 그 다음, 각 클래스별로 (2)의 Class Likelihood를 구해놓으면 학습이 끝난다.
예시와 함께 살펴보도록 하자. 객체 x는 [키, 몸무게]로 이루어진 벡터로 주어지고, 클래스는 남자 혹은 여자로 주어진다고 가정하자.
그렇다면, D를 구성하는 데이터들은 다음과 같이 주어질 것이다.
이 정보들을 종합하여 위 코드에서 (1)의 Priority Probability를 먼저 구해보자. 데이터들을 카운트하여 표에 정리했더니 다음과 같이 결과가 나타났다고 생각해보자.
그렇다면 전체 데이터 개수 N은 10이기 때문에, P(C₁) = 4 / 10 = 0.4이고, P(C₂) = 6 / 10 = 0.6이라는 사실을 쉽게 알 수 있다. 다음은 (2)의 Class Likelihood를 구해보자. 각 클래스별로, 그리고 각 속성별로 진행을 하면서, 특정 클래스에 속한 데이터 중에서 특정 속성 값을 가진 데이터가 몇 개 있는지 카운트하여 표에 정리한다.
(1)과 (2)를 모두 구하였기 때문에, 분류를 위한 학습이 완료되었다. 그렇다면, 이렇게 학습된 정보를 바탕으로 키가 170, 몸무게가 50인 x가 남자인지 여자인지 분류해보자.
P(C₁ | x)와 P(C₂ | x)를 구했을 때, P(C₂ | x)가 1 / 20으로 더욱 큰 값을 가지므로, x는 C₂, 즉, 남자로 분류된다.

3. NBC의 한계와 극복 방안
NBC는 매우 간단하고 실제 많은 분류 문제에서 강력한 성능을 발휘한다. 단, 문제점이 몇 가지 존재한다. 대표적으로 세 가지 정도를 생각해 볼 수 있는데, 각각에 대해 차근차근 알아보도록 하자.

(1) 실수 데이터의 처리
첫 번째 문제는 데이터의 범위와 관련된 문제이다. 예를 들어, 2의 예제에서 키가 정수가 아닌 실수형으로 주어진다고 생각해보자. 위의 예시에서는 정수형으로 주어졌기 때문에 키가 160인 사람이 몇 명인지 셀 수 있었지만, 키가 170.1, 170.232... 이런식으로 실수로 주어진다면 Class Likelihood를 제대로 구할 수 없다. P(x = v | C_k)가 전부 1 / C_k가 될 것이기 때문이다. 따라서 학습이 제대로 되지 않는다. 또한 분류도 문제이다. 학습 중에는 키가 170.3인 데이터가 없었는데 이 데이터를 분류해야 할 경우, 170.3에 대한 Class Likelihood를 구할 수 없으므로 분류가 제대로 되지 않는다.
이 문제는 완벽하게 해결할 수 없지만, 임시 방편으로 데이터를 정수 구간별로 묶는 방법을 사용할 수 있다. 예를 들어, 10 단위로 몸무게, 키를 묶어서 생각하는 것이다. 이 경우, 170.1, 170.2, 170.3의 키를 가진 각각의 데이터가 존재할 때, 키 170 ~ 180 범위의 데이터가 3개 존재한다고 생각할 수 있게 된다. 또한, 170.4의 키를 가진 데이터가 분류되어야 할 때, 이 데이터가 170 ~ 180 범위에 속한다는 가정 때문에 정상적으로 분류가 가능하게 된다.

(2) 빈번한 0
두 번째 문제는 학습과 분류 과정에서, 확률을 계산한 결과가 0이 나오는 경우가 너무 빈번하다는 것이다. 모든 속성에 대한 Class Likelihood를 곱한다는 특징때문에, 한 속성이라도 Class Likelihood가 0이 되는 경우 결과 확률이 무조건 0이 된다는 문제점이 있다. 2의 예제에서도 볼 수 있듯이, Class Likelihood가 0인 경우가 쉽게 나타난다. 학습 과정에서 특정 속성 값을 가진 데이터가 하나도 없는 경우, 해당 속성 값에 대한 Class Likelihood가 0이 되어 다른 속성 값들을 무의미하게 만들어버린다.
이를 해결하기 위한 방법 중의 하나로, 일종의 가중치, 혹은 편향(Bias)을 확률에 더해주는 방법이 있다.
b의 값은 데이터의 분포를 보고 적절한 값을 선택하면 된다. b의 값이 클수록 Prior Probability를 더욱 신뢰하는 효과가 있다.

(3) 종속성
세 번째 문제는 NBC의 근본적인 문제라고 할 수 있다. 바로 종속성과 관련된 문제이다. NBC에서는 모든 특정 객체의 속성들이 모두 독립적이라고 보기 때문에, 종속성이 있는 속성이 주어질 경우 문제가 발생할 수 있다. 2의 예제에서만 봐도, 키와 몸무게는 종속성이 있다고 생각할 수 있다. 키와 몸무게는 비례하기 마련이다. 하지만, NBC에서는 키와 몸무게가 철저히 독립적이라고 가정한다. 따라서 종속성이 매우 높은 속성들을 가진 데이터가 주어지는 문제의 경우 바람직한 결과를 기대할 수 없다. 이러한 경우, NBC에서는 딱히 해결 방법이 없다. NBC 외에 다른 분류 방법을 고려해봐야 한다.

4. NBC의 활용 사례
NBC를 실제 어떤 Application에 적용할 수 있을까? 대표적인 예로 가장 유명한 스팸(Spam) 메일 분류기가 있다. C₁ = Spam, C₂ = Ham이라고 가정한 뒤, 이메일 x가 주어졌을 때 이를 Spam 혹은 Ham으로 분류하는 것이다. x는 Bag Of Words 벡터로 주어진다. 이메일에 등장할 수 있는 단어의 종류를 모두 구해서 Dictionary로 만들고, x가 Dictionary의 단어 중 n 번째에 위치한 단어를 가지고 있으면 1, 그렇지 않으면 0로 인코딩하여 x를 0과 1로 이루어진 벡터로 만드는 것이다. 예를 들어, 이메일에 등장할 수 있는 단어의 수가 4개(Dictionary의 크기 = 4)이고 이메일 x에서 두 번째, 세 번째 단어가 나타났다면, x = [0 1 1 0]으로 나타낸다. 이를 바탕으로 Prior Probability와 단어 별로 Class Likelihood들을 구하여 학습을 하면, 강력한 스팸 분류기가 탄생한다. 실제로, 여러 이메일 시스템에서 이렇게 NBC를 활용한 스팸 처리기를 활용해왔다고 한다.

5. 정리
NBC는 데이터의 속성들이 모두 독립적이라는 가정 하에, 각 속성의 Class Likelihood를 전부 곱해버리는 방법이다. 따라서 Multivariate 문제를 Univariate 문제로 축소하여 해결한다는 특징이 있다. 학습은 Maximum Likelihood Estimation(MLE)을 활용하여 진행하고, 분류는 Maximum a Posteriori Estimation(MAP)을 활용하여 진행한다.
이 글에서는 데이터가 이산 확률 분포를 따른다는 가정이었지만, 이후의 글에서는 데이터가 연속확률분포를 따를 경우에 이 특성을 활용해 NBC로 파라미터 학습(Parametric Learning)을 진행하는 방법에 대해 살펴보도록 하겠다.

6. References
Alpaydın, Ethem. Introduction to machine learning. Cambridge, MA: MIT Press, 2014. Print.

1. 개요
세그먼트 트리(Segment Tree)는 배열처럼 데이터가 일렬로 나열되어 있을 때, 특정 구간의 합, 또는 특정 구간에서 가장 큰 수 등 구간의 정보를 효율적으로 얻어내기 위해 설계된 자료구조이다. 세그먼트 트리에 대해 자세히 알아보고, 구현 방법을 살펴보도록 하자.

2. 세그먼트 트리의 기본 개념
(1) 기본 구조
세그먼트 트리는 이진 트리(Binary Tree)로서, 각 노드는 특정 구간의 정보를 지니고 있고, 부모 노드가 자식 노드의 구간 범위 전체를 포괄하는 것을 기본 원칙으로 한다. 예를 들어, 구간 합의 정보를 저장한 세그먼트 트리의 노드1과 노드2가 각각 1 ~ 4번 데이터의 구간 합, 5 ~ 8번 데이터의 구간 합을 지니고 있다면, 노드1과 2의 부모 노드는 1 ~ 8번 데이터의 구간 합을 지니게 된다.
세그먼트 트리의 가장 최상단 루트 노드(Root Node)는 전체 구간의 정보를 지니며, 가장 최하단의 리프 노드(Leaf Node)들은 크기가 1인 범위, 즉, 각 인덱스의 데이터 하나를 지닌다. 배열로 따지면 배열의 각 요소들이 하나의 리프 노드가 되는 것이다.

(2) 연산
세그먼트 트리의 대표적인 연산으로는 데이터 갱신(Update)과 질의(Query)가 있다.

Update(Index, Data)
Query(From, To)

데이터 갱신(Update)은 새로운 데이터의 추가, 기존 데이터의 수정 및 삭제를 모두 포함한다. 기본적으로 데이터의 위치인 인덱스(Index)와 실제 데이터가 인자로 제공된다. 이를 바탕으로 특정 인덱스 위치에 있는 데이터를 갱신하는 작업을 수행한다.
질의(Query)는 구간의 정보를 탐색하여 사용자에게 반환해주는 작업을 수행한다. 기본적으로 질의하고자 하는 구간의 시작 인덱스와 끝 인덱스가 인자로 제공된다. 예를 들어, 구간 합 세그먼트 트리에 Query(1, 4)를 수행할 경우, 1번, 2번, 3번, 4번 데이터의 합이 반환된다.

3. 구현 방법
세그먼트 트리는 완전 이진 트리(Complete Binary Tree)이다. 위키피디아에 의하면, 완전 이진 트리의 정의는 다음과 같다.

(1) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리
(2) 가장 오른쪽의 잎 노드가 (아마도 모두) 제거된 포화 이진 트리(Perfect Binary Tree)

이는 세그먼트 트리의 데이터들이 각각 특정 인덱스를 가지고 순차적으로 나열되어 있다는 가정과, 상위 노드가 하위 노드들의 구간의 범위를 모두 포함한다는 조건때문에 성립한다. 따라서, 루트 노드를 1번으로 시작하여 각 레벨의 노드들을 순차적으로 나열하면 빈 공간 없이 모든 노드가 일렬로 배치되기 때문에, 기본적으로 배열을 사용하여 세그먼트 트리를 구현한다.
세그먼트 트리를 구현하는 방법에는 크게 두 가지가 있다. 하나는 Bottom-up 방식이고, 두 번째는 Top-down 방식이다. Bottom-up 방식은 단순 반복문을 이용하여 최하단의 리프 노드부터 상향하며 데이터를 갱신하거나 질의하는 방식을 뜻하며, Top-down 방식은 반대로 최상단의 루트 노드부터 시작하여 재귀 함수를 통해 하향하며 데이터를 갱신하거나 질의하는 방식을 뜻한다.
Bottom-up 방식의 경우, 배열과 단순 반복문을 사용하기 때문에 구현도 상대적으로 쉽고, 일반적으로 재귀 함수를 사용하는 Top-down 방식보다 성능 면에서도 뛰어나기 때문에 간단한 문제에서는 Bottom-up 방식을 사용하는 것이 유리하다. 반대로, Top-down 방식의 경우에는 확장성이 뛰어나다는 장점 때문에 복잡한 문제에서는 Top-down 방식을 사용하는 것이 유리한 경우가 종종 있다.
예를 들어, 단순히 특정 인덱스에 있는 하나의 데이터를 갱신하는 것이 아니라, 특정 구간 전체의 데이터에 변화를 주어 트리 내부의 많은 노드에 수정 사항이 발생하는 경우에는, Top-down 방식에 Lazy Propagation과 같은 심화적인 기법을 추가하여 효율적으로 문제를 해결할 수 있다. 반면, Bottom-up 방식은 Lazy Propagation을 적용할 수 없기 때문에 구간의 정보를 한꺼번에 갱신하는 것에는 한계가 있다.
그렇다면, Bottom-up 방식과 Top-down 방식을 어떤식으로 구현할 수 있는지 각각 예제와 함께 살펴보도록 하자. 예제는 구간 합 세그먼트 트리를 바탕으로 하며, C/C++를 기준으로 설명하도록 하겠다.

3-1. Bottom-up 방식
Bottom-up 방식은 모든 연산이 가장 최하단의 리프 노드부터 시작하여 루트 노드까지 위쪽으로 상승하며 이루어진다. 트리 구조를 만드는 법, 데이터를 갱신하는 법, 데이터를 질의하는 법에 대해 알아보자.

(1) 트리 구조 만들기 - BuildTree
순차적으로 저장되어 있는 N개의 데이터는 세그먼트 트리의 가장 최하단의 리프 노드들에 각각 저장된다. 앞서 언급했듯이, 세그먼트 트리는 완전 이진 트리 구조이기 때문에, 최하단 레벨의 노드의 최대 개수는 2의 거듭제곱이고, 이를 Capacity라고 했을 때 리프 노드들을 제외한 모든 노드들의 개수는 Capacity - 1개가 된다. Binary Heap과 유사하게 노드의 상하관계를 배열의 인덱스로 효율적으로 나타내기 위하여, 0번 인덱스는 사용하지 않고 루트 노드를 1번 인덱스에 두고 트리를 만들기 때문에 전체 세그먼트 트리는 Capacity * 2 크기의 배열로 표현할 수 있다. 따라서, N보다 큰 2의 제곱수 중에서 가장 작은 수를 찾아서 Capacity로 설정하고, Capacity * 2 크기의 배열을 생성하도록 하자.

for(Capacity = 1; Capacity < N; Capacity *= 2);
int* tree = new int[Capacity * 2];

예를 들어, N = 6일 경우 Capacity는 8이 되고, 이것이 최하단 레벨, 즉, 리프 노드의 개수가 된다. 그리고 최하단 레벨을 제외한 노드들의 개수는 7개이다.
배열을 생성하였으면, 완전 이진 트리의 성질을 만족시키기 위해서 최하단 레벨의 가장 왼쪽부터 N개의 데이터를 채워넣는다. 배열의 0번 인덱스는 사용하지 않는다는 가정때문에, N개의 데이터 중 가장 첫 번째 데이터는 Capacity번 인덱스에 저장된다. 최하단 레벨의 나머지 노드들은 데이터의 정합성을 위해 0으로 초기화한다.

int data[] = {1, 2, 3, 4, 5, 6};
cnt = 0;
for(i = Capacity; i < Capacity + N; i++) tree[i] = data[cnt++];
for(i = Capacity + N; i < capacity * 2; i++) tree[i] = 0;

그 다음은 상위 노드들의 정보를 갱신할 차례이다. 배열의 인덱스 i에 특정 노드가 있을 때, 해당 노드의 좌측 하위 노드는 인덱스 i * 2에 위치하고, 우측 하위 노드는 인덱스 i * 2 + 1에 위치하게 된다. 이 성질을 바탕으로 최하위 레벨의 바로 윗 레벨부터 시작하여, 최상단의 루트 노드까지 거슬러 올라가면서 하위 노드의 정보를 상위 노드에 포함하는 작업을 한다. 예를 들어, 인덱스 1 ~ 6 범위의 데이터의 합을 나타내는 루트 노드는, 1 ~ 4 범위의 데이터의 합을 가진 좌측 하위 노드와 5 ~ 6 범위의 데이터의 합을 가진 우측 하위 노드의 값을 더함으로써 1 ~ 6 범위의 데이터의 합을 구하게 된다.

void BuildTree(int N, int* data) {
  int i, cnt = 0;
  for(Capacity = 1; Capacity < N; Capacity *= 2);
  tree = (int*)malloc(sizeof(int) * Capacity * 2);
  for(i = Capacity; i < Capacity + N; i++) tree[i] = data[cnt++];
  for(i = Capacity + N; i < Capacity * 2; i++) tree[i] = 0;
  for(i = Capacity - 1; i > 0; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1];
}

이렇게 하면, 기본적으로 N개의 초기 데이터를 포함한 세그먼트 트리가 완성된다.

(2) 데이터 삽입, 수정, 삭제하기 - Update
특정 인덱스 i 위치에 데이터를 삽입하거나, 해당 위치의 데이터를 수정하거나 삭제하는 것은 하나의 함수로 동일하게 처리할 수 있다. 인자로 주어진 인덱스 i에 있는 데이터를 갱신한 다음, 바로 상위 노드부터 시작하여 루트 노드까지 거꾸로 올라가면서 인덱스 i를 포함하는 구간의 정보들을 갱신하면 된다. 이때, 초기 N개의 데이터들은 인덱스 Capacity부터 시작한다는 점을 상기해야 한다. 즉, 인덱스 Capacity + i에 있는 값을 갱신하고, 상위 노드로 올라가면서 구간 정보들을 갱신하면 된다.

void Update(int i, int data) {
  int k = Capacity + i;
  tree[it] = data;
  for(it = it / 2; it > 0; it--) tree[it] = tree[it * 2] + tree[it * 2 + 1];
}

이렇게 하면, N개 데이터의 갱신에 대해 O(NlogN)의 시간복잡도를 가진다.

(3) 데이터 질의하기 - Query
구간의 시작 점과 끝 점이 인자로 주어졌을 때, 해당 구간의 정보를 얻기 위해서는 해당 구간에 포함된 모든 서브 트리(Subtree)들의 정보를 합하는 과정이 필요하다. 예를 들어, 3 ~ 4 범위의 구간 합을 얻고자 한다면, 단순히 3 ~ 4 범위를 커버하는 상위 노드의 값 하나(7)를 반환해주면 된다. 그러나, 2 ~ 5 범위의 구간 합을 얻고자 한다면, 3 ~ 4 범위뿐만 아니라 2 ~ 2와 5 ~ 5 범위의 값도 최종 결과에 합산해주어야 한다.
예제와 함께 살펴보도록 하자. 1 ~ 6의 데이터가 담긴 구간 합 세그먼트 트리에서 2 ~ 5 범위의 구간 합을 구한다고 가정한다. Query 함수의 인자로는 범위의 양 끝 인덱스 2, 5가 주어진다. 양쪽 끝 인덱스를 가리키기 위한 커서 두 개를 만들어 이를 각각 L(left), R(right)라고 하자. 그렇다면 초기 상태는 L = 2, R = 5가 된다.

Query(L, R)

만약 특정 인덱스 i에 대하여 i % 2 = 1일 경우, 인덱스 i의 노드는 우측 자식 노드임을 뜻하며, i % 2 = 0인 경우는 반대로 좌측 자식 노드임을 뜻한다. (완전 이진 트리의 성질 때문에 인덱스 i에 위치한 특정 노드의 자식 노드의 개수는 항상 0 또는 2개이고, 좌측 자식 노드는 i * 2, 우측 자식 노드는 i * 2 + 1에 위치한다는 점을 상기하자.) 이때, 두 가지 주의할 점이 있다.

L이 우측 자식 노드라는 뜻은, L 바로 왼쪽의 노드는 범위에 포함되지 않는다는 뜻이다. 즉, 상위 노드의 정보가 필요하지 않음을 의미한다. 상위 노드는 L 바로 왼쪽의 노드의 정보도 포함하기 때문이다.
마찬가지로, R이 좌측 자식 노드라는 뜻은 R 바로 오른쪽의 노드가 범위에 포함되지 않는다는 뜻이다. 이 경우에도 상위 노드의 정보는 불필요하다.

이 두 가지 경우에 대해서는 더 이상 상위 노드의 정보를 탐색하지 않고, 바로 L과 R에 위치한 노드의 값을 최종 값에 합산한 뒤에 진행한다. L은 한 칸 우측으로 진행(L++)하면 되고, R은 한 칸 좌측(R--)으로 진행하면 된다. 즉, 2와 5의 값을 이미 최종 값에 반영했으므로, 다시 Query(3, 4)를 호출하는 것과 동일한 효과를 얻게 된다.
그렇다면, 앞선 두 가지 경우에 해당하지 않는 경우는 어떨까? 쉽게 예상할 수 있듯이, L과 R의 바로 옆 Sibling이 구하고자 하는 범위에 함께 포함되는 것이다. 이는 곧, 상위 노드의 정보로 대치할 수 있다는 의미이다. 따라서, 인덱스 L과 R을 2로 나누어 상위 노드를 참조하게 한다.
L < R인 동안 계속 이 작업을 반복하다보면, 구하고자 하는 범위의 모든 값들이 포함된다. 단, 마지막 L = R인 경우, 해당하는 노드의 값을 최종 값에 합산해주기만 하면 Query에 대한 답을 구할 수 있다.

int Query(int L, int R) {
  int ret = 0;
  L += Capacity;
  R += Capacity;
  for(; L < R; L /= 2, R /= 2) {
    if(L % 2) ret += tree[L++];
    if(!(R % 2)) ret += tree[R--];
  }
  if(L == R) ret += tree[L];
  return ret;
}

3-2. Top-down 방식
Bottom-up 방식과는 반대로, 모든 연산은 루트 노드에서부터 시작하면서 아래쪽으로 하강하면서 이루어진다.

(1) 트리 구조 만들기 - BuildTree
Bottom-up 방식과 마찬가지로 데이터의 수 N보다 큰 2^n 중 최소값을 찾아 Capacity로 설정한다. 그 다음, (2)에서 다룰 Update 함수를 N개의 데이터에 대해 수행하면 된다.

(2) 데이터 삽입, 수정, 삭제하기 - Update
기본적으로 5개의 인자가 필요하다. 노드를 순회하기 위한 배열 상의 인덱스 n, 그리고 인덱스 n에 위치한 노드가 커버하는 구간을 나타내기 위한 시작 인덱스 s와 끝 인덱스 e, 그리고 N개의 데이터를 배열에 저장했다고 가정했을 때의 인덱스 i, 그리고 저장할 데이터 data이다.

Update(n, s, e, i, data)

이 인자들의 정보를 트리 노드로 표현하면 다음과 같다.
처음 호출될 때는 무조건 n = 1, s = 0, e = N - 1임을 만족한다. 이는 트리 상에서 1번 인덱스에 위치한 루트 노드부터 시작하고, 루트 노드일 때는 인덱스 0 ~ 인덱스 N - 1, 즉, N개 전체의 데이터 구간을 커버한다는 의미이다.
우선, s와 e의 중간지점을 구해 변수 m에 저장해두고, 이를 기준으로 양쪽 서브 트리 중 인덱스 i를 포함한 구간으로 분기한다. 재귀적으로 다음과 같이 함수를 호출하면 된다.

m = (s + e) / 2;
if(i <= m) Update(n * 2, s, m, i, data);
else Update(n * 2 + 1, m + 1, i, data);

이러한 방식으로 서브 트리를 타고 내려가다 보면, s = e인 경우, 즉, 구간에 포함된 노드의 수가 1개인 리프 노드에 도달하게 되는데, 이때 해당 위치에 data를 삽입하면 된다.
리프 노드에 데이터를 삽입하고 나면, 재귀 호출된 함수가 종료되면서 다시 거꾸로 상위 노드 쪽으로 이동하게 되는데, 이때 새로 업데이트된 하위 노드의 정보를 담아야 하므로, 양쪽 하위 노드의 값을 더하여 해당 상위 노드에 저장하도록 한다. 이 과정을 포함한 전체 코드는 다음과 같다.

void Update(int n, int s, int e, int i, int data) {
  if(s == e) tree[n] = data;
  else {
    int m = (s + e) / 2;
    if(i <= m) Update(n * 2, s, m, i, data);
    else Update(n * 2 + 1, m + 1, e, i, data);
    tree[n] = tree[n * 2] + tree[n * 2 + 1];
  }
}

Query(n, s, e, L, R)

return Query(n * 2, s, m, L, R) + Query(n * 2 + 1, m + 1, e, L, R);

(1) L ~ R 구간에서 아예 벗어난 서브 트리
  -> 반환 값에서 제외한다.
(2) L ~ R 구간과 s ~ e 구간이 일부 겹치는 서브 트리
  -> L ~ R 구간에 포함되지 않는 정보를 제외하기 위해 재귀적으로 Query를 호출한다.
(3) L ~ R 구간에 완전히 포함되는 서브 트리
  -> 해당 서브 트리의 루트 노드(인덱스 n에 위치한 노드)의 값을 반환한다.

int Query(int n, int s, int e, int L, int R) {
  if(R < s || e < L) return 0;
  if(L <= s && e <= R) return tree[n];
  int m = (s + e) / 2;
  return Query(n * 2, s, m, L, R) + Query(n * 2 + 1, m + 1, e, L, R);
}