코딩테스트를 준비하면서 C++ 자료구조를 최근에 많이 학습하게 되었습니다.
이제는 조금 익숙해지기 시작했지만 정리를 한번 하고 진행하자 생각해서 정리하게 되었습니다.
1. Vector (동적 배열)
개념
- 크기가 동적으로 변하는 배열
- 연속된 메모리 블록을 사용하여 빠른 인덱스 접근 가능
- push_back을 활용해 원소 추가
vector<int> v = {1, 2, 3};
// 원소 추가
v.push_back(4); // {1, 2, 3, 4}
v.emplace_back(5); // {1, 2, 3, 4, 5}
// 원소 삭제
v.pop_back(); // {1, 2, 3, 4}
// 특정 위치 접근
cout << v[2]; // 3
// 벡터 크기 조정
v.resize(10, 100); // {1, 2, 3, 4, 100, 100, ...}
// 정렬
sort(v.begin(), v.end());
활용 사례
- 빠른 임의 접근이 필요한 경우
- 정렬 후 사용 (배열 기반 문제)
주의할 점
- 중간 삽입/삭제 연산이 많다면 list가 더 유리함
2. Set / MultiSet (정렬된 집합)
개념
- set: 중복 없는 정렬된 데이터 저장
- multiset: 중복 허용
set<int> s = {5, 2, 8, 1};
multiset<int> ms = {5, 2, 8, 1, 5};
// 원소 삽입
s.insert(3);
ms.insert(3);
// 원소 삭제
s.erase(5); // 특정 원소 삭제
ms.erase(ms.find(5)); // 특정 원소 한 개만 삭제
// 탐색
auto it = s.find(2); // 존재하면 해당 위치 반환, 없으면 s.end()활용 사례
- 중복 없는 데이터 저장 (set)
- 정렬된 상태 유지하면서 중복 허용 (multiset)
주의할 점
- 해시 기반 빠른 탐색이 필요하면 unordered_set을 고려
3. Map / MultiMap (Key-Value 저장)
유니티 개발할 때는 Dictionary로 사용했던 자료구조 :)
개념
- map: 키(key) 기준 자동 정렬
- multimap: 중복 키 허용
map<string, int> m;
m["apple"] = 5;
m["banana"] = 2;
m.insert({"orange", 3});
// 탐색
if (m.find("apple") != m.end()) cout << "Exists!";
// 삭제
m.erase("banana");
활용 사례
- 연관 배열 (dict 역할)
- 이진 탐색 트리 기반 정렬이 필요한 경우
주의할 점
- 빠른 탐색이 필요하면 unordered_map 사용 (O(1) 탐색)
4. priority_queue (우선순위 큐)
개념
- 기본적으로 최대 힙 (큰 값 우선)
- greater<type>을 사용하면 최소 힙
priority_queue<int> pq; // 최대 힙
priority_queue<int, vector<int>, greater<int>> min_pq; // 최소 힙
pq.push(5);
pq.push(2);
pq.push(8);
// 최댓값 꺼내기
cout << pq.top(); // 8
pq.pop();활용 사례
- 최소/최대값을 빠르게 추출해야 할 때
- 다익스트라 알고리즘
주의할 점
- pop()은 최상단 요소를 삭제하지만 반환하지 않음
5. Permutation (순열)
개념
- next_permutation()을 사용하면 사전순으로 다음 순열을 구할 수 있음
vector<int> perm = {1, 2, 3};
do {
for (int num : perm) cout << num << " ";
cout << "\n";
} while (next_permutation(perm.begin(), perm.end()));활용 사례
- 모든 경우의 수 탐색 (완전 탐색)
주의할 점
- 정렬된 상태에서 시작해야 모든 순열을 탐색 가능 → Sort()
