99클럽 코테 스터디 16일차 TIL C++ 문자열 : 그리디, set, priority_queue

문제 소개

https://www.acmicpc.net/problem/2212 : 그리디

고속도로 위에 여러 개의 센서를 설치하고, 센서에서 수집한 자료를 분석하기 위해 몇 개의 집중국을 세워야 합니다. 예산상의 제약 때문에 최대한 적은 영역을 커버할 수 있도록 집중국을 배치해야 합니다.

 

이 문제에서는 그리디 알고리즘을 이용하여 전체 커버리지의 길이 합을 최소화할 수 있도록 집중국을 배치하는 방법을 배웁니다. 또한, 문제를 해결하면서 set과 vector의 사용법, 정렬된 자료구조를 다루는 방법을 학습했습니다.

학습 내용 정리

1. 그리디 알고리즘

그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 반복하여 전체 문제를 해결하는 방식입니다. 이 문제에서는 "가장 긴 거리 간격을 우선적으로 제거하여 구간을 최소화"하는 방식으로 그리디 알고리즘을 적용했습니다.

2. set의 기본 사용법

(1) set의 특징

• 중복을 허용하지 않음: set은 중복된 값을 저장하지 않습니다. 이 문제에서는 중복된 센서 위치가 있어도 한 번만 저장되도록 할 수 있습니다.
• 자동 정렬: set은 삽입할 때마다 자동으로 정렬하므로, 추가적인 정렬 작업이 필요 없습니다.

(2) 예제 코드: set의 기본 사용법

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> uniqueNumbers;

    // 중복된 값 삽입
    uniqueNumbers.insert(5);
    uniqueNumbers.insert(3);
    uniqueNumbers.insert(8);
    uniqueNumbers.insert(3); // 중복 값
    uniqueNumbers.insert(1);

    // set의 내용 출력
    cout << "Set contents: ";
    for (int num : uniqueNumbers) {
        cout << num << " "; // 출력: 1 3 5 8
    }
    cout << endl;

    return 0;
}

(3) 정렬 기준 변경하기

기본적으로 set은 오름차순으로 정렬되지만, 사용자 정의 비교 함수를 제공하여 내림차순 등 다른 정렬 기준을 지정할 수 있습니다.

#include <iostream>
#include <set>

using namespace std;

// 내림차순 정렬을 위한 비교 함수
struct CustomCompare {
    bool operator()(int a, int b) const {
        return a > b; // a가 b보다 크면 true (내림차순)
    }
};

int main() {
    set<int, CustomCompare> descendingSet;

    descendingSet.insert(5);
    descendingSet.insert(3);
    descendingSet.insert(8);
    descendingSet.insert(1);

    // set의 내용 출력
    cout << "Descending set contents: ";
    for (int num : descendingSet) {
        cout << num << " "; // 출력: 8 5 3 1
    }
    cout << endl;

    return 0;
}

3. priority_queue (우선순위 큐)

우선순위 큐는 set과는 다른 방식으로 자료를 자동 정렬합니다. 기본적으로 내림차순으로 정렬된 최대 힙으로, 가장 큰 값을 먼저 반환합니다. 오름차순이 필요할 때는 greater<int>를 지정하여 최소 힙으로 구현할 수 있습니다.

예제 코드: 최소 힙

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

int main() {
    priority_queue<int, vector<int>, greater<int>> minHeap; // 최소 힙
    minHeap.push(5);
    minHeap.push(2);
    minHeap.push(3);

    // 가장 작은 값부터 꺼내기
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    // 출력: 2 3 5

    return 0;
}

4. 문제 해결을 위한 아이디어

이 문제에서는 전체 센서 위치를 K개의 구역으로 나누는 방식을 사용했습니다. 일직선으로 배치된 센서들 사이의 거리를 구한 후, 가장 긴 간격을 K-1개 제거하여 K개의 구역을 만듭니다. 이때 남은 거리의 합이 최소가 됩니다.

5. 문제 풀이 코드

전체 코드를 통해 그리디 알고리즘을 구현했습니다.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int sensorCount, stationCount, sensorPosition;
    cin >> sensorCount >> stationCount;

    set<int> uniqueSensors;
    while (sensorCount-- > 0) {
        cin >> sensorPosition;
        uniqueSensors.insert(sensorPosition);
    }

    // set의 내용을 vector로 변환하여 인덱스를 사용할 수 있게 함
    vector<int> sortedSensors(uniqueSensors.begin(), uniqueSensors.end());
    vector<int> sensorGaps;

    // 인접 센서들 사이의 거리 계산
    for (size_t i = 1; i < sortedSensors.size(); i++) {
        int gap = sortedSensors[i] - sortedSensors[i - 1];
        sensorGaps.push_back(gap);
    }

    // 거리 오름차순 정렬
    sort(sensorGaps.begin(), sensorGaps.end());

    // 설치할 집중국 개수에 따라 거리 합 계산
    int minimumCoverage = 0;
    stationCount = min(stationCount, (int)uniqueSensors.size());
    for (size_t i = 0; i < sensorGaps.size() - stationCount + 1; i++) {
        minimumCoverage += sensorGaps[i];
    }

    cout << minimumCoverage << endl;

    return 0; // 프로그램 종료
}

오늘의 회고

이 문제를 통해 그리디 알고리즘의 핵심 개념을 이해하고, 다양한 자료 구조의 사용법을 익힐 수 있었습니다. 특히 set을 사용해 중복된 데이터를 처리하고, 자동 정렬된 상태로 유지하면서 효과적으로 거리를 계산하는 방법이 인상 깊었습니다. 또한 priority_queue를 사용하여 우선순위에 따라 자동 정렬되는 구조에 대한 이해도 강화할 수 있었습니다. 앞으로도 그리디 알고리즘의 다양한 패턴을 연습하며 효율적인 문제 해결 방법을 탐구하고자 합니다.