최단 경로 문제(shortest path problem)은 그래프 사이에서 두 노드 사이의 가장 짧은 경로를 찾는 문제이다. 최단 경로 문제를 푸는 알고리즘 중 일반 프로그래머가 알아둬야 하는 알고리즘에는 (1) Breath First Search (BFS), (2) 다익스트라(Dijkstra) 알고리즘, (3) 벨만-포드(Bellman-Ford) 알고리즘, (4) 플로이드-워셜(Floyd-Warshall) 알고리즘이 있다. 아래의 표는 상황에 따라 어떤 알고리즘을 선택해야 하는지를 정리한 표이다.

0. Graph

네 개의 알고리즘을 소개하기 앞서, 우선 각 알고리즘의 구현에 사용할 그래프 자료구조를 정의한다. 아래의 코드는 이 글에서 사용할 adjacency list 기반 weighted directed graph의 간단한 구현이다.

struct Edge {
    int target_node;
    int weight;
    Edge(int t, int w) { target_node = t; weight = w; }
};

class DirectedGraph {
    public:
        DirectedGraph(int size);
        void AddEdge(int node1, int node2, int weight);
        
        /* Shortest path algorithms: will be implemented in Section 1-4 */
        int GetShortestDistanceBFS(int from, int to);
        int GetShortestDistanceDijkstra(int from, int to);
        int GetShortestDistanceBellmanFord(int from, int to);
        vector<vector<int>> GetShortestDistancesFloydWarshall();
    private:
        vector<vector<Edge>> nodes;
};

DirectedGraph::DirectedGraph(int size) {
    for (int i = 0; i < size; ++i) {
        nodes.push_back(vector<Edge>());
    }
}

void DirectedGraph::AddEdge(int node1, int node2, int weight) {
    nodes[node1].push_back(Edge(node2, weight));
}

Line 13-16의 네 개의 메소드는 아래의 섹션들에서 구현한다.

1. Breath First Search (BFS)

Edge에 weight가 부여되지 않은 그래프 상에서 두 노드 간의 최단 거리는 단순한 그래프 탐색 알고리즘 BFS를 사용하여 구할 수 있다. BFS는 시작 노드로부터 깊이가 1, 2, 3, 4, ... 인 노드들을 순서대로 방문하기 때문에, 이 특징을 이용하면 모든 노드들의 최단 거리를 쉽게 계산할 수 있다(모든 weight가 1이라고 가정하면 깊이 = 최단 거리).

BFS를 사용한 두 노드 사이의 최단 거리를 계산하는 함수의 코드는 아래와 같다. 이 함수는 두 노드가 연결되어 있지 않을 경우 -1, 연결되어 있을 경우 그 거리를 리턴한다.

int DirectedGraph::GetShortestDistanceBFS(int from, int to) {
    vector<int> dist(nodes.size(), -1);
    queue<int> q;
    dist[from] = 0;
    
    q.push(from);
    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (auto it : nodes[curr]) {
            int next = it.target_node;
            if (dist[next] == -1) {
                dist[next] = dist[curr] + 1;
                if (next == to) return dist[next];
                q.push(next);
            }
        }
    }

    return -1;
}

전형적인 BFS 코드라서 크게 설명할 내용은 없다. 일반적으로 BFS는 각 노드의 방문 여부를 표시하는 Boolean 배열을 하나 사용하는데, 여기에서는 최단 거리를 계산하는 것이 목표이기 때문에 정수형 배열(또는 벡터) dist를 사용한다. 새로운 노드에 방문할 때마다 이 배열을 갱신하게 되는데, 해당 코드는 line 14에 있다. 또한 시작 노드로부터 우리가 원하는 노드까지의 거리를 계산했을 경우 이를 리턴하고 바로 수행을 종료한다(line 15).

BFS의 시간 복잡도는 \(O(|V|+|E|)\)이다. 여기서 \(|V|\)는 node(or vertex)의 개수이고 \(|E|\)는 edge의 개수이다. 시간 복잡도가 이렇게 나오는 이유는 탐색 과정에서 모든 node와 edge를 방문하기 때문이다.

2. Dijkstra Algorithm

다익스트라 알고리즘은 가장 많이 알려진 최단 경로 알고리즘으로, 시작 노드를 기준으로 다른 모든 노드 사이의 거리를 계산하는 알고리즘이다. 다익스트라 알고리즘은 시작 노드에서 시작에서 최단 거리가 짧은 노드를 차례대로 선택하며 거리를 계산한다. 알고리즘의 동작을 간단하게 요약하면 다음과 같다.

1. 아직 선택되지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
2. 1번에서 선택된 노드와 연결된 다른 노드의 최단 거리를 갱신한다.
3. 아직 선택되지 않은 노드가 남아있으면 1번으로 돌아간다.

2번에서 최단 거리를 갱신할 때는 아래 식을 이용한다.

$$dist_{curr} \leftarrow \min(dist_{curr}, dist_{next} + cost(curr, next))$$

여기서 \(curr\), \(next\)는 각각 1번 단계에서 선택된 노드와 2번 단계에서 갱신해야 하는 노드이고, \(dist_i\)는 시작 노드로부터 \(i\) 노드까지의 거리, \(cost(i, j)\)는 \(i\) 노드에서 \(j\) 노드로 연결된 edge의 weight이다.

위의 그림은 다익스트라 알고리즘의 수행 예제이다. 매 루프마다 위의 1, 2번 단계가 완료된 시점을 보여준다. 자세한 설명은 생략하도록 하겠다.

다익스트라 알고리즘의 시간 복잡도는 1번 단계에서 최단 거리가 가장 짧은 노드를 어떻게 선택하느냐에 따라 달라진다. 매 루프마다 아직 방문하지 않은 노드들의 최단 거리를 일일이 확인하고 이중 가장 짧은 노드를 선택하면 \(O(|V|^2)\)이 걸린다. Priority queue 또는 heap를 사용하여 최단 거리가 가장 짧은 노드를 찾아낼 경우 \(O(|E|\log|E|)\)가 걸린다. 상황에 따라 둘 중 적절한 구현을 선택해야 한다(Edge가 밀집해있지 않은 많은 그래프에서는 후자가 좋은 선택이 될 것이다).

Priority queue를 사용한 구현 코드는 아래와 같다.

int DirectedGraph::GetShortestDistanceDijkstra(int from, int to) {
    vector<int> dist(nodes.size(), -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[from] = 0;

    pq.push(pair<int, int>(0, from));
    while (!pq.empty()) {
        int curr = pq.top().second;
        pq.pop();

        for (auto it : nodes[curr]) {
            int next = it.target_node;
            int cost = it.weight;
            if (dist[next] < 0 || dist[next] > dist[curr] + cost) {
                dist[next] = dist[curr] + cost;
                pq.push(pair<int, int>(dist[next], next));
            }
        }
    }

    return dist[to];
}

코드의 형태가 queue를 priority_queue로 대체한 것만 제외하면 BFS와 매우 유사한 것을 확인할 수 있다.

다익스트라 알고리즘은 매우 잘 알려진 최단 경로 찾기 알고리즘이지만, 음수의 weight를 가지는 edge가 존재할 경우 사용할 수 없다. 이유는 1번 단계에서 선택되는 노드 \(i\)의 \(dist_i\)가 시작 노드로부터 노드 \(i\) 까지의 최단 거리임을 보장할 수 없기 때문이다. 이런 경우에는 벨만-포드 알고리즘을 사용하게 된다.

3. Bellman-Ford Algorithm

벨만-포드 알고리즘은 다익스트라 알고리즘과 동일한 식을 사용하여 시작 노드로부터 각 노드의 최단 거리를 찾는다.

$$dist_{curr} \leftarrow \min(dist_{curr}, dist_{next} + cost(curr, next))$$

단, 벨만-포드 알고리즘은 다익스트라 알고리즘과는 다른 방식으로 이 식을 적용한다. 벨만-포드 알고리즘의 착안점은 최단 경로가 최대 N-1 개의 edge로 이루어져 있다는 것이다(모든 노드를 방문할 경우). 따라서 N-1 번 루프를 돌면서 매 루프마다 모든 edge에 대해 위의 식을 적용한다면 시작 노드로부터 각 노드의 최단 거리를 찾을 수 있다(엄밀한 정당성 증명은 아니니 다른 자료를 찾아보고 증명 과정을 한 번은 읽어보길 권함).

1. 모든 edge에 대해 위의 식을 적용한다.
2. 1번 단계를 N-1회 반복한다.

이 알고리즘의 시간 복잡도는 \(O(|V||E|)\)이다.

구현 코드는 아래와 같다.

int DirectedGraph::GetShortestDistanceBellmanFord(int from, int to) {
    const int inf = 987654321;
    vector<int> dist(nodes.size(), inf);
    dist[from] = 0;

    for (int i = 0; i < nodes.size() - 1; ++i) {
        for (int curr = 0; curr < nodes.size(); ++curr) {
            if (dist[curr] < inf) {
                for (auto it : nodes[curr]) {
                    int next = it.target_node;
                    int cost = it.weight;
                    dist[next] = min(dist[next], dist[curr] + cost);
                }
            }
        }
    }

    return dist[to];
}

한 가지 주의할 점은 그래프 내에 negative cycle이 존재할 경우 최단 거리가 제대로 정의되지 않을 수도 있다는 것이다. 이런 경우인지를 확인하기 위해서는 알고리즘 수행이 끝난 후 1번 단계를 한번 더 실행해야 한다. 이 때 최단 거리가 계속 감소한다면 negative cycle에 의해 최단 거리가 제대로 정의되지 않는 상황인 것이다.

4. Floyd-Warshall Algorithm

모든 노드 쌍에 대해 최단 거리를 계산하는 가장 직관적인 방법은 모든 쌍에 대해 다익스트라 알고리즘이나 벨만-포드 알고리즘을 적용하는 것이다. 하지만 플로이드-워셜 알고리즘을 사용하면 이보다 더 빠르게 모든 노드 쌍의 최단 거리를 계산할 수 있다.

플로이드-워셜 알고리즘의 키워드는 경유점이다. \(d_k(i,j)\)를 노드 0부터 \(k\)를 경유할 수 있을 때 노드 \(i\)로부터의 노드 \(j\)까지의 최단 거리라고 정의하자. 이 때 다음의 식이 성립한다.

$$d_k(i,j) = \min(d_{k-1}(i,j), d_{k-1}(i,k) + d_{k-1}(k,j))$$

위의 식의 의미를 생각해보자. \(d_k(i,j)\)를 계산해야 할 때 고려해야 하는 경우의 수는 두 가지이다: (1) 최단 경로가 노드 \(k\)를 경유하거나, (2) 최단 경로가 노드 \(k\)를 경유하지 않는다. (1)의 경우 \(d_k(i,j)\)의 값은 \(d_{k-1}(i,j)\)와 동일하다. (2)의 경우 \(d_k(i,j)\)의 값은 \(k\)를 경유하지 않는 노드 \(i\)로부터의 노드 \(k\)까지의 최단 거리와 \(k\)를 경유하지 않는 노드 \(k\)로부터의 노드 \(j\)까지의 최단 거리의 합과 동일하다.

\(k\)를 노드의 개수만큼 증가시켜가며 위의 식을 적용하면 모든 노드 쌍의 최단 거리를 계산할 수 있다. 아래의 코드를 참고하자.

vector<vector<int>> DirectedGraph::GetShortestDistancesFloydWarshall() {
    const int inf = 987654321;
    vector<vector<int>> dists(nodes.size(), vector<int>(nodes.size(), inf));

    for (int i = 0; i < nodes.size(); ++i) {
        dists[i][i] = 0;
    }
    for (int i = 0; i < nodes.size(); ++i) {
        for (auto it : nodes[i]) {
            dists[i][it.target_node] = it.weight;
        }
    }

    for (int k = 0; k < nodes.size(); ++k) {
        for (int i = 0; i < nodes.size(); ++i) {
            for (int j = 0; j < nodes.size(); ++j) {
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j]);
            }
        }
    }

    return dists;
}

\(k\)가 1, 2, 3, ... 인 경우를 차례대로 계산하기 때문에 삼차원 배열이 아닌 이차원 배열을 사용할 수 있고, 이로 인해 메모리 사용량을 줄일 수 있다는 점을 참고하자.

플로이드-워셜 알고리즘의 시간 복잡도는 \(O(|V|^3)\)이다. 메인 루프인 line 14-20의 코드를 보면 바로 알 수 있다.

이번에 연구실에 새로 들어오는 신입생들에게 자료구조와 알고리즘 스터디를 시킬 예정인데, 해당 스터디에서 사용할 숙제 문제들을 공유한다. 기초적인 문제들 위주로 백준 온라인 저지와 LeetCode에서 선택하였다. 언어는 C++을 사용한다.

리스트는 스터디가 진행될 동안 계속 갱신될 것이다.

• Algorithm analysis and sorting
  
  • Insertion sort and selection sort (같은 문제를 두 알고리즘으로 두 번 풀기)
  • Merge sort
  • Quick sort
• Array and Linked List
  • Remove n-th node from end of list
  • Reverse linked list
• Stack and queue
  • Stack
  • Queue
  • 쇠막대기 (STL stack을 사용할 것)
  • 조세퍼스 문제 (STL queue를 사용할 것)
• Tree
  • 트리 순회
  • Maximum depth of binary tree
  • Symmetric tree
• Heap
• Graph

문제

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of \(O(\log n)\). If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1,-1]

풀이

주어진 배열에서 특정값을 가지는 주소를 \(O(\log n)\)에 찾는다고 했으니 당연히 binary search를 제일 먼저 떠올려야 한다. Binary search를 사용하기로 작정하고 문제를 살펴보면, 두 번의 전형적인 binary search 알고리즘으로 답을 구할 수 있다는 것을 알게 될 것이다. Starting position을 찾기 위해 1번, ending position을 찾기 위해 1번이 필요하다. 시간 복잡도는 \(O(\log n)\)이고, 공간 복잡도는 \(O(1)\)이다.

좀 더 알고리즘을 개선할 여지가 없는지 고민해보자. 두 번의 binary search에서 중복된 작업이 수행된다. 수행 시작부터 주어진 target value를 처음 찾을 때까지 작업이 이에 해당한다. 따라서 이 작업을 한 번만 하도록 알고리즘을 수정하면 수행 시간이 줄어들 것이다.

알고리즘을 크게 보면 다음 세 부분으로 나눌 수 있다.

1. Binary search를 수행하며 target value를 가지는 index를 찾는다. 만약 없으면 [-1, -1]을 리턴한다.
2. 1번에서 남아있는 왼쪽 구역에 대해 binary search를 계속 수행하여 starting position을 찾는다.
3. 1번에서 남아있는 오른쪽 구역에 대해서도 binary search를 수행하여 ending position을 찾는다.

코드 (C++)

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> ret;

    int left = 0;
    int right = nums.size() - 1;
    int mid;
 
    /* Step 1 */
    while (left <= right) {
        mid = (left + right) / 2;
        if (nums[mid] == target) {
            break;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    if (left > right) {
        ret.push_back(-1);
        ret.push_back(-1);
        return ret;
    }
    
    /* Step 2 */
    int start_left = left;
    int start_right = mid;
    while (start_left < start_right) {
        int start_mid = (start_left + start_right) / 2;
        if (nums[start_mid] < target) {
            start_left = start_mid + 1;
        } else {
            start_right = start_mid;
        }
    }

    /* Step 3 */
    int end_left = mid;
    int end_right = right;
    while (end_left < end_right) {
        int end_mid = (end_left - end_right) / 2 + end_right;
        if (nums[end_mid] > target) {
            end_right = end_mid - 1;
        } else {
            end_left = end_mid;
        }
    }
        
    ret.push_back(start_left);
    ret.push_back(end_left);
    return ret;
}