C++ 코딩테스트 강좌, 선분을 그룹으로 나누기

현대의 프로그래밍 언어 중 C++는 그 속도와 효율성 덕분에 매우 인기 있는 언어입니다. 다양한 분야에서 널리 사용되고 있으며, 특히 알고리즘 문제 풀이에 있어서 강력한 도구가 됩니다. 이번 글에서는 “선분을 그룹으로 나누기”라는 주제로 알고리즘 문제를 해결하는 과정을 단계별로 살펴보겠습니다.

문제 설명

주어진 문제는 여러 개의 선분들이 있을 때, 선분들을 겹치지 않도록 그룹으로 나누는 것입니다. 두 개의 선분이 겹친다는 것은 한 선분의 끝점이 다른 선분의 시작점보다 앞쪽에 있으면서도 끝점이 다른 선분의 끝점보다 뒤쪽에 있는 경우를 의미합니다. 이 문제를 푸는 데 필요한 단계와 방법들을 알아보겠습니다.

문제 예제

다음과 같은 선분들이 주어졌다고 가정해봅시다:

    선분 1: (1, 3)
    선분 2: (2, 5)
    선분 3: (6, 8)
    선분 4: (7, 9)
    선분 5: (10, 12)

위의 선분들을 그룹으로 나누면 다음과 같은 그룹이 나올 수 있습니다:

그룹 1: {(1, 3), (2, 5)}
그룹 2: {(6, 8), (7, 9)}
그룹 3: {(10, 12)}

문제 해결 과정

1단계: 문제 분석

문제를 해결하기 위해 먼저 입력 및 출력 형식을 명확히 해야 합니다. 선분들은 두 개의 정수 (시작점, 끝점)로 표현되며, 여러 선분이 겹쳐지는 경우를 한 그룹으로 묶어야 합니다. 나중에 그룹의 개수를 출력해야 합니다.

2단계: 접근 방법

선분들이 겹치는 경우를 판단하기 위해서는 선분들을 시작점에 따라 정렬하고, 각 선분을 차례로 확인하여 겹치는지 여부를 판단해야 합니다. 겹치지 않는 경우에만 새로운 그룹을 만들 수 있습니다.

3단계: 알고리즘 설계

우리가 사용할 알고리즘은 다음과 같습니다:

모든 선분을 시작점 기준으로 정렬합니다.
정렬된 선분을 순회하면서 현재 그룹의 끝점과 다음 선분의 시작점을 비교합니다.
겹치는 경우에는 현재 그룹의 끝점을 업데이트하고, 겹치지 않는 경우에는 새로운 그룹을 시작합니다.

4단계: 구현

아래는 C++로 구현한 코드입니다:


#include 
#include 
#include 

using namespace std;

struct LineSegment {
    int start;
    int end;
};

bool compare(LineSegment a, LineSegment b) {
    return a.start < b.start;
}

int groupLineSegments(vector& segments) {
    if (segments.empty()) return 0;

    // 선분을 시작점 기준으로 정렬
    sort(segments.begin(), segments.end(), compare);
    
    int groupCount = 1;
    int currentEnd = segments[0].end;

    for (int i = 1; i < segments.size(); i++) {
        if (segments[i].start <= currentEnd) {
            // 겹치는 경우, currentEnd를 업데이트
            currentEnd = max(currentEnd, segments[i].end);
        } else {
            // 겹치지 않는 경우, 새로운 그룹 시작
            groupCount++;
            currentEnd = segments[i].end;
        }
    }

    return groupCount;
}

int main() {
    vector segments = {{1, 3}, {2, 5}, {6, 8}, {7, 9}, {10, 12}};
    int result = groupLineSegments(segments);
    
    cout << "그룹의 개수: " << result << endl;
    return 0;
}

5단계: 코드 실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:


그룹의 개수: 3

결론

이번 강좌에서는 C++를 활용하여 ‘선분을 그룹으로 나누기’ 문제를 해결해 보았습니다. 이 문제를 통해 알고리즘을 설계하는 과정을 경험하고, 정렬 및 그룹 분류의 기초 개념을 익힐 수 있었습니다. 실제 코딩테스트에서는 이와 같은 문제를 자주 만날 수 있으므로, 이러한 문제를 반복적으로 연습하는 것이 중요합니다. 앞으로도 다양한 알고리즘 문제를 다루는 연습을 계속하며 실력을 쌓아가시길 바랍니다.