99클럽 코테 스터디 17일차 TIL C++ 우선순위큐, 표준 입출력 동기화 해제

우선순위 큐를 활용한 문제 풀이와 학습 기록

문제1 : 우선순위큐, 표준 입출력 동기화 해제

https://www.acmicpc.net/problem/2075

학습 과정: 다양한 시도와 결과

문제1 : 우선순위큐, 표준 입출력 동기화 해제

(1) 시도1: 메모리 초과

• 모든 데이터를 우선순위 큐에 삽입한 후, (N)번째로 큰 값을 찾는 방식으로 접근했습니다.
• 문제점: 메모리 초과 발생.
  • 총 (N \times N = 2,250,000)개의 정수를 큐에 저장해야 하므로 메모리 사용량이 (12)MB를 초과.
  • 각 정수가 (4)바이트라면 (9)MB가 필요하지만, 우선순위 큐의 내부 관리 메모리까지 고려하면 제약을 넘습니다.
• 모든 데이터를 저장하기보다는 문제를 해결하는 데 필요한 최소한의 데이터만 유지해야 한다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int N, it;
    cin >> N;
    priority_queue<int> queue;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> it;
            queue.push(it);  // 모든 값을 우선순위 큐에 삽입
        }
    }

    int find_num;
    for (int i = 0; i < N; i++) {
        find_num = queue.top();  // N번째 큰 값 찾기
        queue.pop();
    }

    cout << find_num << endl;
    return 0;
}

(2) 시도2: 시간 초과

• (N)개의 최대값만 유지하도록 우선순위 큐의 크기를 제한하는 방식으로 개선했습니다.
• 큐의 크기가 (N)을 초과하면 가장 작은 값을 제거하여 메모리를 절약했습니다.
• 문제점: 시간 초과 발생.
  • (N \times N)개의 데이터를 cin으로 입력받는 과정에서 병목현상이 발생.
  • 기본적으로 C++의 cin은 느리며, 대규모 데이터 처리에서 실행 시간이 초과됨.

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

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

    priority_queue<int, vector<int>, greater<int>> minHeap;  // 최소 힙
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            cin >> num;

            minHeap.push(num);  // 힙에 삽입
            if (minHeap.size() > N) {
                minHeap.pop();  // 힙 크기 유지
            }
        }
    }

    cout << minHeap.top() << endl;  // N번째로 큰 값 출력
    return 0;
}

 

(3) 시도3: 성공 (입출력 최적화)

• 입출력 속도를 최적화하여 시간 초과 문제를 해결했습니다.
• ios_base::sync_with_stdio(false)와 cin.tie(NULL)를 사용해 C++ 표준 입출력 동기화를 해제하고 속도를 크게 향상시켰습니다.
• 성공적으로 실행.
• 입출력 병목 문제를 해결하며 시간 초과 없이 데이터를 처리.

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

int main() {
    ios_base::sync_with_stdio(false);  // C와 C++ 입출력 동기화 해제
    cin.tie(NULL);  // cin과 cout의 묶음을 해제

    int N;
    cin >> N;

    priority_queue<int, vector<int>, greater<int>> minHeap;  // 최소 힙
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            cin >> num;
            minHeap.push(num);  // 힙에 삽입

            if (minHeap.size() > N) {
                minHeap.pop();  // 힙 크기 유지
            }
        }
    }

    cout << minHeap.top() << endl;  // N번째로 큰 값 출력
    return 0;
}

우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)는 큐와 비슷하지만, 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다. 내부적으로 힙(Heap) 자료구조를 사용해 구현되며, 두 가지 형태로 나뉩니다:

1. 최대 힙(Max-Heap): 가장 큰 값이 큐의 맨 앞에 위치.
   • 기본적으로 priority_queue<int>는 최대 힙으로 구현됩니다.
2. 최소 힙(Min-Heap): 가장 작은 값이 큐의 맨 앞에 위치.
   • 최소 힙은 priority_queue<int, vector<int>, greater<int>> 형식으로 선언합니다.

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

int main() {
    // 최대 힙 선언
    priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);

    cout << "Max Heap Top: " << maxHeap.top() << endl; // 20 출력
    maxHeap.pop();
    cout << "Max Heap Top after pop: " << maxHeap.top() << endl; // 10 출력

    // 최소 힙 선언
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);

    cout << "Min Heap Top: " << minHeap.top() << endl; // 5 출력
    minHeap.pop();
    cout << "Min Heap Top after pop: " << minHeap.top() << endl; // 10 출력

    return 0;
}

입출력 최적화

기본적으로 cin과 cout은 C++의 표준 입출력이며, C의 scanf와 printf와 동기화됩니다. 이는 사용 편의성을 높이는 반면, 속도는 느려지는 단점이 있습니다.

1. ios_base::sync_with_stdio(false):
   • C와 C++ 입출력 동기화를 끊어 속도를 개선.
   • 대규모 데이터를 처리하는 경우 필수적인 최적화.
2. cin.tie(NULL):
   • cin과 cout의 묶임을 풀어, cout이 cin의 입력을 기다리지 않게 만듦.

오늘의 회고

이번 학습을 통해 문제의 제약 조건을 정확히 이해하고, 효율적인 알고리즘 설계와 실행 환경에 맞는 최적화를 적용하는 것이 얼마나 중요한지 배웠습니다. 처음에는 메모리 초과와 시간 초과 문제를 겪었지만, 이를 개선하면서 우선순위 큐와 입출력 최적화의 중요성을 깨닫게 되었습니다.