99클럽 코테 스터디 19일차 TIL C++ priority_queue, 약수탐색(sqrt)

오늘의 학습 키워드

문제 1: priority_queue
BOJ 19638: 센티와 마법의 뿅망치

문제 2: 완전탐색, 약수탐색, sqrt
Programmers: 카펫

공부한 내용 본인의 언어로 정리하기

문제 1: priority_queue

(1) priority_queue 개념과 주요 사용법

• priority_queue
  • C++ STL에서 제공하는 자료구조로, 데이터가 최대 힙(Max Heap) 또는 최소 힙(Min Heap)의 형태로 관리됩니다.
  • 가장 큰 값 또는 가장 작은 값을 반복적으로 처리해야 하는 상황에서 유용.
  • 기본 동작: 내림차순으로 정렬된 힙(가장 큰 값이 top()에 위치).
  • 시간 복잡도:
    • 삽입/삭제: (O(\log N))
    • 최댓값/최솟값 접근: (O(1))
• 주요 메서드:
  1. pq.push(value): 값을 큐에 삽입.
  2. pq.top(): 큐에서 최댓값 반환 (값은 제거되지 않음).
  3. pq.pop(): 최댓값을 제거.
  4. pq.empty() / pq.size(): 큐가 비었는지 확인하거나 크기를 반환.

(2) 입력값에 맞는 자료형

자료형 선택 가이드

1. int: 정수 계산 ((10^9) 이하) → 배열 인덱스, 반복문, 카운트 등.(4 bytes)
2. long: 플랫폼에 따라 크기가 다름 → (10^9 \sim 10^{18}) 범위의 큰 정수 처리.(4 또는 8 bytes)
3. long long: (10^9) 이상 큰 정수 → 금융 계산, 천문학 등에서 (10^{18}) 수준 처리.(8 bytes)
4. float: 소수점 이하 약 7자리 (4 bytes)
5. double: 소수점 이하 약 15자리 (8 bytes)

(3) 전체 풀이

문제 요약
센티는 자신보다 키가 큰 거인들을 마법의 뿅망치를 사용해 키를 줄이려 합니다.
우선순위 큐를 활용하여 가장 큰 키의 거인을 반복적으로 줄이고, 제한된 뿅망치 횟수 내에 모든 거인이 센티보다 작아질 수 있는지 확인하는 문제입니다.

핵심 풀이 전략:

1. 우선순위 큐를 사용해 가장 큰 거인의 키를 효율적으로 관리.
2. 제한된 횟수(T) 동안 가장 키가 큰 거인을 H / 2로 줄임.
3. 목표를 달성하면 성공, 그렇지 않으면 실패를 출력.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long N, H, T;
    cin >> N >> H >> T;

    priority_queue<long long> queue;
    while (N-- > 0) {
        long long height;
        cin >> height;
        queue.push(height);
    }

    long long top, t;
    for (t = 0; t < T; t++) {
        top = queue.top();
        if (top < H) break; // 모든 거인의 키가 H보다 작으면 종료
        long long nxt = max(top / 2, 1LL); // nxt를 long long으로 계산
        queue.pop();
        queue.push(nxt);
    }

    top = queue.top(); // 남아 있는 가장 큰 키 확인
    if (top < H) {
        cout << "YES" << endl;
        cout << t << endl; // 정확한 뿅망치 사용 횟수 출력
    } else {
        cout << "NO" << endl;
        cout << top << endl; // 가장 큰 거인의 키 출력
    }

    return 0;
}

문제 2: 완전탐색, 약수탐색, sqrt

(1) 약수 구하기

• 약수를 구하는 효율적인 방법:
  약수는 항상 제곱근을 기준으로 대칭적입니다.
  • 예: (36)의 약수는 ((1, 36), (2, 18), (3, 12), (4, 9), (6, 6)).
  • 따라서 (1 \sim \sqrt{N}) 범위만 탐색하면 됩니다.
• 시간 복잡도:
  • (O(\sqrt{N})), (N)이 (brown + yellow)일 때 효율적.

(2) 전체 풀이

문제 요약
주어진 갈색(brown)과 노란색(yellow) 격자를 조합하여 카펫의 가로와 세로를 구하는 문제입니다.
카펫의 크기와 형태는 다음과 같은 조건을 만족해야 합니다:

1. 가로 (\geq) 세로.
2. 갈색 격자는 테두리로만 존재.
3. 노란색 격자의 크기 ( (width - 2) \times (height - 2) ).

풀이 전략:

1. ( \text{totalCells} = \text{brown} + \text{yellow} )에서 약수 쌍 ((height, width))를 구합니다.
2. 각 쌍에 대해:
   • ( (width - 2) \times (height - 2) = \text{yellow} )를 확인.
3. 조건을 만족하면 정답 반환.

#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

vector<int> solution(int brown, int yellow) {
    // 총 격자 수
    int totalCells = brown + yellow;

    // 가능한 약수 쌍 탐색
    for (int height = 1; height <= sqrt(totalCells); height++) {
        if (totalCells % height != 0) continue; // 약수만 탐색
        int width = totalCells / height;       // 대응하는 가로 길이

        // 노란색 영역 조건 확인
        if ((width - 2) * (height - 2) == yellow) {
            return {width, height}; // 조건을 만족하는 경우 반환
        }
    }

    return {}; // 조건에 맞는 값이 없는 경우 (문제 제한사항상 도달하지 않음)
}

오늘의 회고

문제 1:
priority_queue는 항상 가장 큰 값 또는 작은 값을 효율적으로 관리할 때 유용합니다. 이번 문제를 통해 최대 힙의 사용법과 반복적인 조건 처리를 다루는 방법을 학습했습니다. 특히 삽입과 삭제가 (O(\log N))로 매우 효율적이라는 점에서 실전에서 활용도가 높은 자료구조임을 느꼈습니다.

문제 2:
약수 탐색의 효율성을 높이기 위해 제곱근까지만 탐색하는 방법을 사용했습니다. 제곱근 탐색을 통해 (O(\sqrt{N})) 복잡도로 약수 쌍을 빠르게 구할 수 있었고, 조건을 직접 확인하여 추가적인 메모리 사용도 줄였습니다.

배운 점:

1. priority_queue의 기본 동작과 최대 힙/최소 힙의 활용.
2. 제곱근 범위로 약수를 구해 완전탐색 문제를 효율적으로 해결하는 방법.