[카테고리:] C++ 코딩테스트 강좌

안녕하세요! 이번 글에서는 위상 정렬에 대해 알아보겠습니다. 위상 정렬은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 선형으로 나열하는 알고리즘으로, 특정한 순서를 유지해야 할 때 유용합니다. 예를 들어 작업의 종속성을 처리하거나 컴파일러가 코드의 실행 순서를 결정할 때 사용됩니다.

문제 설명

다음 문제를 해결해 보겠습니다.

입력

첫 번째 줄에는 정점의 개수 N (1 ≤ N ≤ 1000)과 간선의 개수 M (0 ≤ M ≤ 10000)이 주어진다.

다음 M개의 줄에는 x y 쌍이 주어지며, 이는 작업 x가 작업 y보다 먼저 수행되어야 함을 의미한다.

출력

작업을 수행할 수 있는 순서를 한 줄에 공백으로 구분하여 출력한다. 만약 순서가 불가능하다면 -1을 출력한다.

예제 입력

    6 6
    1 2
    1 3
    2 4
    3 4
    4 5
    5 6
    

예제 출력

1 2 3 4 5 6

위상 정렬의 원리

위상 정렬은 두 가지 방법으로 구현할 수 있습니다: DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색). 여기서는 BFS를 이용한 Kahn의 알고리즘을 소개합니다. Kahn의 알고리즘은 다음과 같은 절차로 진행됩니다.

1. 모든 정점의 진입 차수를 기록합니다.
2. 진입 차수가 0인 정점을 큐에 넣습니다.
3. 큐에서 정점을 하나씩 꺼내고, 그 정점을 결과 리스트에 추가합니다.
4. 꺼낸 정점으로부터 나가는 모든 간선을 제거하고, 각 간선의 도착 정점의 진입 차수를 업데이트합니다. 진입 차수가 0이 되는 정점을 큐에 추가합니다.
5. 큐가 빌 때까지 반복합니다. 결과 리스트의 크기가 입력한 정점의 개수와 다르면 사이클이 존재하는 것이므로 -1을 반환합니다.

기본 코드 구현

아래는 C++로 위상 정렬을 구현한 기본적인 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topologicalSort(int n, vector<vector<int>> &graph) {
    vector<int> inDegree(n + 1, 0);
    vector<int> result;

    // 진입 차수 계산
    for (int i = 1; i <= n; i++) {
        for (int j : graph[i]) {
            inDegree[j]++;
        }
    }

    queue<int> q;

    // 진입 차수가 0인 정점 큐에 삽입
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 사이클 확인
    if (result.size() != n) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << ' ';
        }
        cout << endl;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }

    topologicalSort(n, graph);
    return 0;
}
    

코드 설명

위 코드에서는 먼저 진입 차수를 담기 위해 inDegree라는 배열을 선언합니다. 각 정점의 진입 차수를 계산한 뒤, 진입 차수가 0인 정점을 큐에 넣습니다. 그 다음 큐에서 정점을 꺼내고, 꺼낸 정점으로부터 나가는 간선을 모두 제거하고 진입 차수를 업데이트합니다. 만약 result 리스트의 크기가 정점의 개수와 다르면 사이클이 존재하므로 -1을 출력합니다.

복잡도 분석

위상 정렬의 시간 복잡도는 O(N + M)입니다. 여기서 N은 정점의 개수, M은 간선의 개수입니다. 진입 차수를 세는데 O(M) 시간이 소요되고, 각 정점마다 진입 차수를 업데이트하는 과정에서도 O(M) 시간이 걸립니다. 따라서 전체적으로 O(N + M)의 시간 복잡도를 가집니다. 공간 복잡도는 O(N + M)으로, 그래프를 저장하기 위한 리스트와 진입 차수 배열을 고려해야 합니다.

추가 연습 문제

아래의 추가 연습 문제를 통해 위상 정렬을 더 깊이 이해하고 적용해보세요.

1. 주어진 작업을 기반으로 다양한 작업 조합을 만들고 위상 정렬을 적용해 보세요.
2. 사이클이 포함된 그래프를 입력으로 주어졌을 때, 적절한 에러 처리를 구현해 보세요.
3. 진입 차수가 같은 정점이 여러 개일 경우, 그 중 하나의 정점을 무작위로 선택하도록 구현해 보세요.

결론

이번 포스트에서는 위상 정렬의 개념과 구현 방법, 예제 문제를 통해 위상 정렬의 활용 방법에 대해 배워보았습니다. 위상 정렬은 다양한 분야에서 많이 응용되는 알고리즘이므로 충분히 이해하고 연습하는 것이 중요합니다.

이제 여러분도 위상 정렬을 활용하여 복잡한 작업을 정렬하고 관리하는 데에 자신감을 가질 수 있기를 바랍니다. 계속해서 연습하고 다양한 문제를 풀어보세요!

이번 강좌에서는 C++을 사용하여 “오큰수 구하기”라는 문제를 해결해보겠습니다. 이 문제는 주어진 수열에서 각 원소에 대해 자신보다 크고, 가장 가까운 위치에 있는 수를 찾는 문제입니다. 이를 통해 스택을 활용한 문제 해결 방법과 효율적인 알고리즘 설계를 배워보겠습니다.

문제 설명

주어진 정수 배열에서 각 배열의 원소에 대해, 그 원소보다 큰 수가 오른쪽에 있는 가장 가까운 위치를 찾아 해당 수를 출력합니다. 만약 그런 수가 존재하지 않는다면 -1을 출력해야 합니다.

입력

• 첫 번째 줄에 배열의 크기 N (1 ≤ N ≤ 1,000,000)
• 두 번째 줄에 N개의 정수로 이루어진 배열 A (0 ≤ A[i] ≤ 1,000,000)

출력

• N개의 정수로 이루어진 배열 B를 출력해야 하며, B[i]는 A[i]의 오른쪽에서 가장 가까운 큰 수입니다. 그런 수가 없다면 -1을 출력해야 합니다.

예제 입력

5
2 1 2 4 3

예제 출력

4 2 4 -1 -1

문제 접근 방법

이 문제를 해결하는 가장 효율적인 방법은 스택(Stack) 자료구조를 사용하는 것입니다. 배열의 맨 뒤에서부터 시작하여 각 원소를 순회하면서 다음과 같은 과정을 수행합니다.

1. 스택이 비어있지 않고, 현재 원소가 스택의 가장 위에 있는 원소보다 크면, 스택에서 원소를 pop 합니다. 이 때 pop한 원소는 현재 원소의 오큰수가 됩니다.
2. 현재 원소의 인덱스와 오큰수 값을 배열에 저장합니다.
3. 현재 원소를 스택에 push합니다.

이 과정을 배열의 처음까지 반복하여 모든 원소의 오큰수를 찾을 수 있습니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. 각 원소는 스택에 단 한 번 push되고 단 한 번 pop되므로, 모든 원소를 들른다고 하더라도 스택의 원소 개수는 N을 넘지 않습니다.

구현

이제 실제로 위의 알고리즘을 C++로 구현해보겠습니다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void findNextGreaterElement(const vector<int>& arr, vector<int>& result) {
    stack<int> s; // 스택 선언

    for (int i = arr.size() - 1; i >= 0; --i) {
        // 스택에서 현재 원소보다 작거나 같은 원소를 제거
        while (!s.empty() && s.top() <= arr[i]) {
            s.pop();
        }
        // 스택이 비어있으면, 오큰수는 -1
        if (s.empty()) {
            result[i] = -1;
        } else {
            result[i] = s.top(); // 스택의 가장 위 원소가 오큰수
        }
        s.push(arr[i]); // 현재 원소를 스택에 추가
    }
}

int main() {
    int N;
    cout << "배열의 크기를 입력하세요: ";
    cin >> N;

    vector<int> arr(N);
    cout << "배열 원소를 입력하세요: ";
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    vector<int> result(N);
    findNextGreaterElement(arr, result);

    cout << "오큰수: ";
    for (int i = 0; i < N; ++i) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

코드 설명

위의 코드는 “오큰수 구하기” 문제를 해결하기 위한 C++ 프로그램입니다. 다음은 각 부분에 대한 설명입니다.

• 헤더 파일 포함: iostream, vector, stack 라이브러리를 포함하여 입출력, 벡터 사용, 스택 사용을 가능하게 합니다.
• findNextGreaterElement 함수: 이 함수는 입력으로 주어진 배열과 결과를 저장할 벡터를 받아, 오큰수를 찾는 핵심 로직을 포함하고 있습니다.
• main 함수: 프로그램의 시작점으로, 사용자로부터 배열의 크기와 원소를 입력받고, 오큰수를 계산한 후 결과를 출력합니다.

결론

이번 강좌에서는 “오큰수 구하기” 문제를 C++을 사용하여 효율적으로 해결하는 방법을 배웠습니다. 스택을 활용하여 배열의 각 원소에 대해 오큰수를 찾아내는 과정에서 스택의 특징과 알고리즘의 효율성을 느낄 수 있었습니다. 실제 코딩 테스트에서는 이러한 자료구조와 알고리즘을 활용할 수 있는 능력이 중요합니다.

코딩테스트에서 자주 출제되는 문제인 만큼 다양한 변형 문제에 대해서도 고민해보고, 스택을 활용한 문제 해결 능력을 키우는 것이 중요합니다. 앞으로도 유사한 문제들을 접하면서, 다양한 알고리즘과 자료구조를 익혀보시기 바랍니다.