C++ 코딩테스트 강좌, 선분 방향 구하기

코딩테스트는 현업에서의 프로그래밍 능력을 평가하기 위해 다양한 문제를 포함하고 있습니다. 이번 글에서는 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++ 프로그래밍 능력을 향상시킬 수 있습니다.