PS Thread

나는 Java, Kotlin이 주력 언어다. 업무에서도 이 두 가지를 쓰지만 C++를 알아두면 선택지가 넓어질 것 같아 입문해보려고 한다. LeetCode를 풀면서 C++ 숙련도를 올려보자.

오늘 배운 것

1. std::vector (동적 배열) 선언법

C++에서는 객체를 생성할 때 new를 무분별하게 사용하지 않는다.

잘못된 예: vector<int> res = new vector(); (자바 스타일)

C++에서 new를 쓰면 메모리 주소(포인터)를 반환하기 때문에 vector<int>* res처럼 선언해야 하고, 나중에 직접 delete로 메모리를 해제해야 한다.

올바른 예: vector<int> res(크기);

이렇게 선언하면 함수가 끝날 때 자동으로 메모리가 정리되는 지역 변수가 된다.

2. .size() 메서드

배열이나 리스트의 길이를 구할 때 언어마다 이름이 다르지만, C++에서는 size()를 표준으로 사용한다.

3. 참조자 (Reference, &)

코드의 vector<int>& nums에서 & 기호는 원본을 가져다 쓰겠다는 뜻이다.

• vector<int> nums: 함수를 호출할 때 배열 전체를 복사 (메모리 낭비가 큼)
• vector<int>& nums: 원본 배열의 별명만 지어줌 (메모리 사용이 거의 없고 빠름)

4. 벡터의 초기화와 인덱스 접근

C++ 벡터는 선언할 때 크기를 미리 정해두면 일반 배열처럼 []를 사용해 접근할 수 있다.

vector<int> v(10);: 크기가 10이고 0으로 초기화된 벡터 생성. v[0]부터 v[9]까지 사용 가능.

크기를 정하지 않고 생성(vector<int> v;)했다면, v[i] = 10;처럼 대입할 수 없고 반드시 v.push_back(10);을 써야 한다.

5. 스택(Stack) vs 힙(Heap) - new의 의미가 다르다

Java에서 new는 일상적이지만, C++에서 new는 이 객체를 수동으로 관리하겠다는 선언에 가깝다.

Java: Solution sol = new Solution(); // GC(Garbage Collector)가 알아서 치워준다.

• C++ (Stack): Solution sol; // 함수가 종료되면 메모리에서 자동으로 사라진다.
• C++ (Heap): Solution* sol = new Solution(); // 사용 후 delete sol;을 하지 않으면 메모리 누수가 발생한다.

6. 네임스페이스 (std::) - 가문 밝히기

C++의 표준 라이브러리(STL)는 모두 std 네임스페이스 안에 있다.

Java는 import 후 클래스 이름만 쓰면 되지만, C++은 std::vector, std::sort처럼 출처를 밝히는 것이 원칙이다.

코드 상단에 using namespace std;를 선언하면 생략할 수 있으나, 규모가 큰 프로젝트에서는 이름 충돌 방지를 위해 std::를 명시하는 습관이 좋다.

7. 범위 기반 for 루프 (Range-based for loop)

Kotlin의 for (num in nums)나 Java의 for (int num : nums)와 같은 문법을 C++11부터 지원한다.

for (int n : nums) { 
    // n은 nums 요소를 '복사'해서 가져온다.
}

for (int& n : nums) { 
    // &를 붙이면 '참조'로 가져온다.
    // n을 수정하면 원본 nums도 수정되고, 복사 비용이 들지 않아 효율적이다.
}

Java/Kotlin -> C++ 대응표

Java / Kotlin	C++ STL	핵심 특징
ArrayList<T>	vector<T>	연속 메모리, 인덱스 접근 O(1)
LinkedList<T>	list<T>	중간 삽입/삭제 O(1), 인덱스 접근 느림
Stack<T>	stack<T>	LIFO
Queue<T>	queue<T>	FIFO
Deque<T>	deque<T>	양쪽 삽입/삭제 O(1)
PriorityQueue<T>	priority_queue<T>	기본 최대 힙
HashMap<K,V>	unordered_map<K,V>	평균 O(1), 정렬 없음
TreeMap<K,V>	map<K,V>	자동 정렬, O(logN)
HashSet<T>	unordered_set<T>	평균 O(1), 중복 없음
TreeSet<T>	set<T>	정렬 유지, 중복 없음

코테에서 자주 쓰는 선택 기준

• "순서대로 담고 인덱스로 빠르게 접근" -> vector
• "키 기준 정렬된 순회 필요" -> map / set
• "정렬 필요 없고 존재 여부만 빠르게" -> unordered_map / unordered_set
• "최솟값/최댓값을 계속 꺼내야 함" -> priority_queue
• "BFS 레벨 탐색" -> queue
• "슬라이딩 윈도우에서 앞뒤 pop/push" -> deque

꼭 알아둘 기본 시간복잡도 (암기용)

• vector: 뒤 push_back 평균 O(1), 중간 삽입/삭제 O(N), 인덱스 접근 O(1)
• map/set: 삽입/삭제/탐색 O(logN)
• unordered_map/unordered_set: 평균 O(1), 최악 O(N)
• priority_queue: 삽입 O(logN), top 조회 O(1), pop O(logN)

실전 코드 패턴

#include <bits/stdc++.h>
using namespace std;

// 1) 최소 힙 (Java PriorityQueue 기본 동작과 유사)
priority_queue<int, vector<int>, greater<int>> minHeap;

// 2) 빈도수 카운트
unordered_map<int, int> freq;
for (int x : nums) freq[x]++;

// 3) key 정렬 순회가 필요할 때
map<int, int> ordered;
for (int x : nums) ordered[x]++;

// 4) 중복 제거 + 존재 여부 확인
unordered_set<int> seen;
if (seen.count(x)) {
    // already exists
}
seen.insert(x);

bits/stdc++.h 없이 필요한 헤더만 include 하기

온라인 저지에서는 #include <bits/stdc++.h>가 편하지만, 표준 C++ 헤더는 아니기 때문에 환경에 따라 동작하지 않을 수 있다. 실무/이식성을 생각하면 필요한 헤더를 명시적으로 include하는 습관이 좋다.

#include <iostream>      // cin, cout
#include <vector>        // vector
#include <string>        // string
#include <algorithm>     // sort, max, min, lower_bound
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <map>           // map
#include <set>           // set
#include <queue>         // queue, priority_queue
#include <stack>         // stack
#include <deque>         // deque
#include <utility>       // pair
#include <limits>        // numeric_limits

using namespace std;

자주 쓰는 알고리즘 유틸까지 넣고 싶다면 다음도 많이 사용한다.

• <functional>: greater<>, less<>, 함수 객체
• <numeric>: accumulate, gcd(환경에 따라)
• <tuple>: tuple, tie

C++ STL 사용 시 자주 하는 실수

• unordered_map은 순서를 보장하지 않는다. 출력 순서 기대하면 안 됨
• priority_queue는 기본이 최대 힙이다 (최소 힙은 comparator 필요)
• vector에 크기 없이 v[i] = ... 하면 런타임 에러 가능성 있음
• map[key]++는 key가 없으면 자동으로 0 생성 후 증가한다

정리하면, 코테에서는 대부분 vector + unordered_map/set + priority_queue 조합으로 시작하고, "정렬된 상태 유지"가 필요할 때만 map/set로 바꾸면 판단이 빨라진다.

C++ priority_queue 정리. 핵심은 **기본이 최대 힙(Max-Heap)**이라는 점이다.

1) 기본 사용법 (최대 힙)

가장 큰 값이 top()에 온다.

#include <queue>
#include <iostream>

using namespace std;

int main() {
    // 기본: 큰 값 우선
    priority_queue<int> pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);

    cout << "Top element: " << pq.top() << endl; // 30

    pq.pop(); // 30 제거
    cout << "Next top: " << pq.top() << endl; // 20
}

2) 최소 힙 (Min-Heap)

가장 작은 값을 top()으로 두려면 세 번째 템플릿 인자로 greater<T>를 쓴다.

// priority_queue<자료형, 구현체, 비교연산자>
priority_queue<int, vector<int>, greater<int>> pq;

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top() << endl; // 10

3) pair와 함께 사용하기

pair<int, int>는 기본 비교가 사전식(lexicographical)이다.

• 먼저 first를 비교
• first가 같으면 second를 비교

기본 priority_queue<pair<int, int>>에서는 큰 값이 우선이므로, first/second 모두 내림차순 우선순위를 가진다.

priority_queue<pair<int, int>> pq;

pq.push({5, 100}); // 거리 5, 인덱스 100
pq.push({5, 200}); // 거리 5, 인덱스 200
pq.push({10, 50}); // 거리 10, 인덱스 50

// 결과: {10, 50} -> {5, 200} -> {5, 100} 순으로 나옴

4) 핵심 멤버 함수

함수	설명	시간 복잡도
push(val)	요소 추가	$O(\log N)$
pop()	최우선 요소 제거	$O(\log N)$
top()	최우선 요소 조회 (제거 X)	$O(1)$
empty()	비어있는지 확인	$O(1)$
size()	요소 개수	$O(1)$

5) 커스텀 정렬 (구조체 comparator)

정렬 기준이 복잡하면 comparator를 직접 정의하는 것이 가장 안전하다.

예: 거리(first)는 큰 값 우선, 거리가 같으면 인덱스(second)는 작은 값 우선

struct Compare {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        if (a.first == b.first) {
            return a.second > b.second; // 두 번째 인자는 작은 게 위로 (오름차순)
        }
        return a.first < b.first; // 첫 번째 인자는 큰 게 위로 (내림차순)
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

주의: pop()은 반환값이 없다. 값을 사용하려면 top()을 먼저 읽고 pop()해야 한다.

6) greater<T> / less<T> 정리

greater<int>는 <functional>의 함수 객체다. 내부적으로 a > b 비교를 수행한다.

template <typename T>
struct greater {
    bool operator()(const T& a, const T& b) const {
        return a > b;
    }
};

사용 예시

• sort(..., greater<int>()) -> 내림차순 정렬
• priority_queue<int, vector<int>, greater<int>> -> 최소 힙

vector<int> v = {1, 4, 2, 5, 3};
sort(v.begin(), v.end(), greater<int>()); 
// 결과: {5, 4, 3, 2, 1}

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top() << endl; // 10

less vs greater 비교

기능	less<T> (기본값)	greater<T>
비교 연산	a < b	a > b
std::sort 결과	오름차순	내림차순
priority_queue 결과	최대 힙	최소 힙

7) C++14 이후 간결한 표기

C++14부터는 greater<int>() 대신 greater<>()를 쓸 수 있다.

sort(v.begin(), v.end(), greater<>());

정리: 코테에서 우선순위 큐는 "기본 최대 힙"을 먼저 기억하고, 최소 힙이 필요하면 greater<T>를 넣는 습관을 들이면 실수를 크게 줄일 수 있다.