라이브스마트

코딩테스트는 현업에서의 프로그래밍 능력을 평가하기 위해 다양한 문제를 포함하고 있습니다. 이번 글에서는 C++로 ‘선분의 방향 구하기’ 문제를 해결하는 과정을 자세히 알아보겠습니다. 이 문제는 기하학적 문제로, 점과 벡터의 기초적인 개념이 필요합니다.

문제 설명

주어진 점 A(x1, y1), B(x2, y2), C(x3, y3)가 있을 때, 선분 AB와 선분 AC의 방향을 구하는 문제입니다. 이때 선분의 방향은 시계 방향, 반시계 방향 또는 동일선 위로 구분됩니다.

입력 형식

3
0 0
1 1
2 2

첫 번째 줄에는 점의 개수가 주어지고, 다음 세 줄에는 각각 점의 좌표가 주어집니다.

출력 형식

0

0은 동일선 위에 있음을 나타내며, 1은 반시계 방향, -1은 시계 방향을 의미합니다.

알고리즘 접근법

세 점 A, B, C가 주어졌을 때 그들의 방향성은 벡터의 외적을 통해 구할 수 있습니다. A에서 B로 향하는 벡터와 A에서 C로 향하는 벡터의 외적의 부호를 이용하여 방향을 결정할 수 있습니다.

벡터의 외적 계산

외적을 통해 구한 결과는 다음과 같이 정의됩니다:

cross_product = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

여기서:

• cross_product > 0 : 반시계 방향
• cross_product < 0 : 시계 방향
• cross_product = 0 : 동일선 위

코드 구현

이제 C++로 문제를 해결하기 위한 코드를 작성해 보겠습니다.

#include <iostream>

using namespace std;

int main() {
    int x1, y1, x2, y2, x3, y3;
    
    // 점 A, B, C의 좌표 입력
    cout << "점 A 좌표 (x1 y1): ";
    cin >> x1 >> y1;
    cout << "점 B 좌표 (x2 y2): ";
    cin >> x2 >> y2;
    cout << "점 C 좌표 (x3 y3): ";
    cin >> x3 >> y3;

    // 외적 계산
    int cross_product = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    
    // 방향 판단
    if (cross_product > 0) {
        cout << "반시계 방향 (1)" << endl;
    } else if (cross_product < 0) {
        cout << "시계 방향 (-1)" << endl;
    } else {
        cout << "동일선 위 (0)" << endl;
    }

    return 0;
}

코드 설명

코드는 다음과 같은 단계를 포함합니다:

1. 사용자로부터 점 A, B, C의 좌표를 입력받습니다.
2. 외적을 계산하여 cross_product를 구합니다.
3. 결과에 따라 방향을 판단하고 출력합니다.

보다 심화된 이해를 위한 추가 설명

이 문제는 기하학적 이해를 요구합니다. 벡터의 외적은 일반적으로 3D 공간에서 두 벡터의 평면을 구별하는 데 사용되지만, 2D 공간에서는 방향을 구별하는 데 유용한 도구となります. 기하학적 개념과 벡터 수학을 이해하므로써, 다양한 문제를 해결할 능력을 기를 수 있습니다.

기하학적 직관

기하학적으로 이 문제는 직선의 기울기를 이해하는 것이기도 합니다. 선분 A에서 B로, 그리고 A에서 C로 향하는 경우, 두 벡터의 상대적인 기울기를 판단함으로써 방향성을 파악 할 수 있습니다. cross_product가 양수인지 음수인지에 따라 점 C가 선 AB의 왼쪽에 있는지 오른쪽에 있는지를 알 수 있습니다.

결론

이번 강좌에서는 간단한 기하학 문제를 통해 코딩테스트에서 자주 출제되는 유형을 다뤘습니다. ‘선분의 방향 구하기’ 문제는 기초적인 기하학의 이해가 필요한 문제로, 벡터의 외적을 이용하여 해결할 수 있습니다. 이러한 문제를 연습함으로써 알고리즘적 사고를 기르고, 기초적인 C++ 프로그래밍 능력을 향상시킬 수 있습니다.

문제 설명

여러 개의 빌딩이 하나의 도시를 구성하고 있습니다. 각 빌딩은 고유한 번호를 가지고 있으며,
빌딩들 사이에는 방향성이 있는 도로가 존재합니다. 문제는 이러한 빌딩들을 특정한 순서로
건축해야 하는 규칙이 존재하며, 그 순서를 구하는 것입니다.

모든 빌딩은 주어진 조건에 의해 건축 순서가 결정됩니다. 이 문제는 위상 정렬(Topological Sort) 문제로
나타낼 수 있습니다. 주어진 규칙을 기반으로 원하는 빌딩의 순서를 계산하여 출력하는 것이
목적입니다.

입력 형식

첫 번째 줄에는 빌딩의 수 N과 도로의 수 M이 주어집니다. (1 ≤ N ≤ 10^6, 0 ≤ M ≤ 10^6)
다음 M개의 줄에는 도로의 정보가 주어지며, 두 정수 A, B가 주어질 경우 이는 빌딩 A가
빌딩 B보다 먼저 건축되어야 함을 의미합니다.

출력 형식

빌딩의 건축 순서를 한 줄로 출력합니다. 만약 건축 순서를 정할 수 없는 경우 ‘0’을 출력합니다.

예제

입력

    4 2
    1 2
    2 3
    

출력

    1 2 3 4
    

접근 방법

이 문제를 해결하기 위해 우리는 두 가지 방법을 고려할 수 있습니다.
1. DFS(Depth-First Search)를 활용한 방법
2. Kahn의 알고리즘을 활용한 방법

위상 정렬 문제는 사이클이 없는 방향 그래프에서 가능한 빌딩 순서를 찾아야 하는 문제입니다.
여기서 사이클이 존재하면 문제의 요구사항을 만족할 수 없기 때문에,
이를 체크하는 과정이 필요합니다.

1. DFS를 활용한 방법

DFS를 사용하여 그래프를 탐색하면서 각 노드를 방문하는 방식으로
위상 정렬을 수행할 수 있습니다. 이 방식의 핵심은 각 노드를 스택에
추가할 때, 해당 노드의 모든 자식 노드가 방문되었을 때입니다.

2. Kahn의 알고리즘

Kahn의 알고리즘은 각 노드의 진입 차수를 사용하여 위상 정렬을 수행하는 방법입니다.
이 알고리즘은 다음과 같은 단계를 포함합니다:

1. 그래프의 진입 차수를 계산합니다.
2. 진입 차수가 0인 노드를 큐에 추가합니다.
3. 큐에서 노드를 하나씩 꺼내어 출력하고, 해당 노드와 연결된 모든 노드의
   진입 차수를 감소시킵니다. 만약 진입 차수가 0이 된 노드를 큐에 추가합니다.
4. 이 과정을 반복합니다. 모든 노드를 방문했다면 성공적으로 위상 정렬을
   수행한 것이고, 사이클이 없는 것입니다.

구현

이제 위에 설명한 Kahn의 알고리즘을 사용하여 문제를 해결하는 코드를
구현해보겠습니다.

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

void topologicalSort(int N, vector>& graph, vector& inDegree) {
    queue q;
    vector result;

    // 진입 차수가 0인 노드를 큐에 추가
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

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

        // 현재 노드와 연결된 모든 노드의 진입 차수 감소
        for (int neighbor : graph[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // 결과 출력
    if (result.size() == N) {
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    } else {
        cout << "0" << endl; // 사이클이 존재할 경우
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector> graph(N + 1);
    vector inDegree(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; // A -> B
        graph[A].push_back(B);
        inDegree[B]++;
    }

    topologicalSort(N, graph, inDegree);

    return 0;
}
    

결론

위상 정렬 문제는 많은 알고리즘 문제에서 접할 수 있는 유형 중 하나로,
특히 프로젝트의 작업 순서를 결정해야 할 때 유용하게 사용될 수 있습니다.
이 강좌에서는 Kahn의 알고리즘을 통해 빌딩 순서를 구하는 문제를 해결했습니다.
다양한 변형 문제가 존재하므로, 실제 코딩테스트에서 실력을 쌓기 위해
다양한 문제를 풀어보기를 권장합니다.

수고하셨습니다! 여러분의 코딩테스트 준비에 많은 도움이 되었기를 바랍니다.