[1. 입출력 데이터 다루기]
입력값을 유형별로 정리해서 효율적으로 처리해보자.
1. 숫자 다루기
cmath 헤더를 추가하여 사용할 수 있는 연산들.
1) 반올림하기
주어진 숫자를 '가장 가까운' 정수로 변환하는 것이며 round 함수를 사용하면 된다. 만약 0.5면 0에서 먼쪽으로 반올림한다. 예를 들어, round(2.5) = 3, round(-2.5) = -3이다.
2) 올림, 소수점 버리기/내림
주어진 숫자보다 크거나 같은 가장 작은 값을 구할 때 ceil함수를 사용.
가장 가까운 작은 정수로 변환할 때 floor 함수를 사용. 예를 들어, floor(-3.7) = -4이다. 음수에 대해서는 소수점 이하를 단순히 버리는 것이 아니라 숫자가 더 줄어든다.
2. 문자열 스트림
stringstream은 문자열을 마치 스트림처럼 다룰 수 있도록 해주는 클래스이다. 즉, 문자열을 입력 스트림처럼 처리해서 cin에서 데이터를 추출하듯 문자열에서 값을 추출할 수 있다.
1) 공백 기준으로 분리
분리할 문자열을 stringstream의 생성자에 전달하여 입력 스트림으로 설정한다. 그 후, >> 연산자를 이용해서 문자열에서 원하는 데이터를 차례대로 변수에 저장한다. 예를 들어,
#include <iostream>
#include <ssstream>
#incldue <string>
using namespace std;
int main() {
string str = "123 * 67";
stringstream stream(str);
int num;
char c;
float f;
stream >> num >> c >> f;
return 0;
}반환되는 값은 123 X 67 구분되어 반환.
2) 특정 문자 기준으로 분리
공백 대신 문자로 구분하기 위해서는 getline 함수를 사용할 수 있다. 예를 들어, getline(ss, buf, ',') 와 같이 사용하면 "," 기준으로 문자열을 분리할 수 있다. 일반적으로 while 반복문과 함께 사용해서 문자열을 끝까지 순차적으로 분리한다.
2) 진법 변환
출력시 10진수를 16진수로 변환해야 할 때, stringstream과 hex(조작자)를 활용해서 간단하게 처리할 수 있다.
stringstream과 << 연산자를 활용한다. 예를 들어, ss << hex << decimalNumber; 식으로 사용한다. ss는 16진수 문자열로 출력될 것이다.
16진수를 10진수로 변환할 때. stringstream과 >> 연산자를 활용한다. ss >> hex >> decimalNumber;식으로 사용한다. ss가 16진수 "ff" 였다면, decimalNumber는 10진수로 변환되어 나올 것이다.
[2. STL 사용하기]
C++에서 표준 라이브러리로 제공되는 STL의 구조와 주요 구성 요소를 알아보자.
여기에서는 컨테이너, 반복자, 알고리즘 등에 익숙해져야한다.
1. STL 구성요소
컨테이너, 알고리즘, 반복자가 있다.
컨테이너는 데이터를 저장하고 관리하는 객체이고, -> vector, map, list
알고리즘은 컨테이너에 저장된 데이터를 처리하는 다양한 함수를 제공하며, -> sort(), next_permutation()
반복자는 컨테이너의 요소들을 순회하고 접근하는 방법을 제공한다.
1) 반복자
컨테이너와 알고리즘이 서로 독립적으로 작동하도록 연결해준다.
순방향 반복자는 컨테이너의 요소들을 앞에서부터 차례로 순회하며, 각 원소에 접근할 수 있게 한다.
begin(), end(). 반복자가 가리키는 곳을 읽거나 수정할 수 있다. ++ 연산자는 지원하지만 --연산자는 지원하지 않는다.
역방향 반복자는 rbegin(), rend(). ++, -- 연산자 모두 지원한다.
2) 컨테이너
(1) 벡터
배열과 매우 유사한 컨테이너지만 크기를 동적으로 조절할 수 있다. <vector> 헤더 파일이 필요. 인덱스를 통해 특정 위치의 원소에 쉽게 접근할 수 있다.
vector<int> vec 같이 기본 생성자를 활용한다. 선언과 동시에 초기값을 직접 지정할 수 있도 있다.
배열과 마찬가지로 [] 연산자를 사용하여 특정 위치의 원소에 직접 접근할 수 있다.
벡터는 내부 데이터를 자동으로 관리하므로 메모리 구조를 직접 고려하지 않고 삽입과 삭제를 수행할 수 있다. 이때 사용하는 것이 push_back() 메서드, pop_back() 메서드, insert() 메서드이다. 모든 원소를 삭제하고 싶으면 clear() 메서드를 활용한다. 중간 삽입 시에는 지정한 번호 뒤에 삽입되고 나머지가 뒤로 한칸씩 밀리게 된다.
// 짝수인 원소만 0으로 변경하는 예제
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i] % 2 == 0)
vec[i] = 0;
}
for (int num : vec) {
cout << num << " ";
}
return 0;
}
// 출력결과: 1 0 3 0 5벡터를 사용할 때 비효율을 방지하기 위해서는 reserve를 활용해서 메모리 재할당을 방지하는 것이 좋다. (그냥 미리 메모리를 확보하는 것)
// reserve를 사용하여 메모리 재할당을 방지하는 예제
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec;
vec.reserve(10); // 최대 10개의 원소를 넣을 예정이므로 미리 메모리 확보
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << end
}
return 0;
}
/*
출력결과:
size: 1, capacity: 10
size: 2, capacity: 10
...
size: 10, capacity: 10
유의사항: reserve를 사용하면 불필요한 재할당 없이 성능 최적화 가능
*/
(2) 셋(set)
중복되지 않는 원소들을 정렬된 상태로 저장하는 컨테이너이다. <set> 헤더 파일을 포함해야 한다.
set<int> s 와 같이 빈 셋을 선언할 수 있고, 초기화도 가능하다. 또한, set<int>s2 = s1 과 같이 기존 셋을 복사해서 새로운 셋을 만들 수 있다.
삽입시 insert() 메서드, 삭제는 erase() 메서드, 모든 원소 삭제시에는 clear()메서드. set의 경우에는 삽입을 하던 삭제를 하던 매번 정렬된 상태를 유지한다. 따라서 삽입/삭제시 시간 복잡도는 O(logN) 이다.
정렬 상태를 유지하는 특성 때문에 원소를 바로 수정할 수는 없다. 그래서 기존 원소를 삭제하고, 새로운 값을 삽입하는 방식으로 처리해야 한다.
set은 중복된 원소를 허용하지 않기 때문에 중복된 값을 저장해야 한다면 multiset을 사용해야 한다.
원소의 정렬이 필요하지 않고 빠른 탐색이 중요한 경우에는, 해시 기반의 unordered_set을 사용하는 것이 더 적합할 수 있다.
set은 삽입과 동시에 자동 정렬되므로 원소의 삽입 순서가 유지되지 않는다. 삽입 순서가 중요하다면 vector나 list 등의 컨테이너를 사용하는 것이 좋다.
set은 인덱스를 지원하지 않으므로 인덱스를 사용해서 원소에 접근해야 하는 경우 vector를 사용하는 것이 적합하다.
// set에서 원소를 변경하려면 erase 후 insert를 사용해야 함
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {1, 2, 3, 4, 5};
// 3을 30으로 변경하려면, 먼저 3을 삭제하고 30 삽입
s.erase(3);
s.insert(30);
for (int v : s) {
cout << v << " ";
}
return 0;
}
// 출력결과: 1 2 4 5 30
// 원소를 직접 수정할 수 없기 때문에 반드시 erase + insert 필요
(3) 맵(map)
키와 값을 쌍으로 갖는 연관 컨테이너이다. <set> 헤더 파일을 포함해야 한다. 중복 키를 허용하지 않고 키를 기준으로 데이터가 자동으로 오름차순 정렬된다. <map> 헤더 파일을 포함해야 한다.
map<keyType, valueType> m 과 같이 선언한다. map<string, int> m1 = m2 와 같이 기존 맵을 복사할 수도 있다.
[] 연산자를 활용해서 맵의 값을 변경할 수 있다. m["Alice"] = 31. key값 Alice에 접근해서 값을 31로 변경한다. 다만 해당 키가 없다면 새로운 키-값 쌍을 만든다.
at() 메서드를 사용해서 맵의 값을 변경할 수도 있다. m.at("Bob") = 26. Bob 키에 연결된 값을 26으로 변경한다. 다만 [] 연산자와는 다르게 해당 키가 없으면 out_of_range 예외가 발생한다.
삽입에는 insert() 메서드를 사용한다. 이미 존재한다면 삽입은 무시되고 삽입된 위치의 반복자와 함께 false가 반환된다.
삭제에는 erase() 메서드를 사용한다.
모든 원소를 삭제하려면 clear() 메서드를 사용한다.
단순히 키만 필요하고 값이 필요하지 않는 경우 : set 사용이 적합
원소의 삽입 순서를 유지해야 한다면 : vector 또는 list
// [] 연산자를 사용하여 기존 값 변경 및 없는 키 추가
#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> myMap = {{"Apple", 1}, {"Banana", 2}, {"Cherry", 3}};
myMap["Apple"] = 10; // 기존 키의 값 변경
myMap["Durian"] = 4; // 새로운 키-값 쌍 추가
for (auto& p : myMap) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
// 출력결과:
// Apple: 10
// Banana: 2
// Cherry: 3
// Durian: 4
// [] 연산자는 키가 없을 경우 새로 추가함// insert()를 이용한 삽입 및 중복 키 처리 결과 확인
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> myMap;
auto result1 = myMap.insert({1, "Apple"});
auto result2 = myMap.insert({2, "Banana"});
auto result3 = myMap.insert({1, "Cherry"}); // 중복 키
cout << "삽입 1 성공 여부: " << result1.second << endl; // true
cout << "삽입 2 성공 여부: " << result2.second << endl; // true
cout << "삽입 3 (중복) 성공 여부: " << result3.second << endl; // false
for (auto& p : myMap) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
// 출력결과:
// 삽입 1 성공 여부: 1
// 삽입 2 성공 여부: 1
// 삽입 3 (중복) 성공 여부: 0
// 1: Apple
// 2: Banana// erase()를 사용하여 키 또는 반복자를 통해 원소 삭제
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> myMap = {
{1, "Apple"}, {2, "Banana"}, {3, "Cherry"}
};
myMap.erase(2); // 키 2 삭제
auto it = myMap.find(3); // 키 3의 반복자 찾기
if (it != myMap.end()) {
myMap.erase(it); // 반복자를 통한 삭제
}
for (auto& p : myMap) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
// 출력결과:
// 1: Apple
// 키 기반 삭제는 O(logN), 반복자 삭제는 평균 O(1)3) 알고리즘
알고리즘을 사용하려면 기본적으로 <algorithm> 헤더를 포함해야 한다.
(1) sort()
sort() 함수는 기본적으로 오름차순으로, 범위 [First, last)에 있는 원소들을 정렬한다. first는 포함하고, last는 포함하지 않는다.
sort(first, last) 형식으로 사용하거나, sort(first, last, comp) 형식으로 사용할 수 있다.
보통 사용자 정의 비교 함수는 bool comp(a,b) 형식으로 선언한다. 그러니까 a, b를 비교했을 때 true 를 반환하면 a는 b보다 먼저 와야 한다는 의미가 된다. 즉, 정렬 기준을 직접 정의할 수도 있다.
// 사용자 정의 비교 함수(comp)를 사용한 내림차순 정렬
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(int a, int b) {
return a > b; // a가 b보다 크면 앞에 와야 한다 → 내림차순
}
int main() {
vector<int> vec = {5, 2, 9, 1, 7};
sort(vec.begin(), vec.end(), comp); // 내림차순 정렬
for (int v : vec) {
cout << v << " ";
}
return 0;
}
// 출력결과: 9 7 5 2 1// 문자열 벡터를 길이 기준으로 정렬하는 사용자 정의 comp 함수 사용
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compareByLength(const string& a, const string& b) {
return a.length() < b.length(); // 짧은 문자열이 앞에 오도록 정렬
}
int main() {
vector<string> names = {"Alice", "Bob", "Christina", "Dan"};
sort(names.begin(), names.end(), compareByLength);
for (const string& name : names) {
cout << name << " ";
}
return 0;
}
// 출력결과: Bob Dan Alice Christina
(2) find()
범위 [first, last) 내에서 특정 값과 일치하는 첫 번째 원소를 선형 탐색한다. 일치하는 값이 있으면 해당 원소를 가리키는 반복자를 반환하고, 없으면 last 반복자를 반환한다.
find(first, last, value) 형식으로 사용한다.
// 찾으려는 값이 없을 때 find()가 반환하는 값 확인
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
auto it = find(vec.begin(), vec.end(), 99); // 99는 없음
if (it == vec.end()) {
cout << "값을 찾을 수 없습니다." << endl;
}
return 0;
}
// 출력결과: 값을 찾을 수 없습니다.
// 값이 없으면 마지막 반복자(end) 반환
(3) count()
범위 [firrst, last) 내에서 특정 값이 몇 번 등장하는지 계산하여 반환한다.
count(first, last, value) 형식으로 사용한다.
// 존재하지 않는 값에 대해 count()를 수행하는 예제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4};
int result = count(v.begin(), v.end(), 10);
cout << "10의 개수: " << result << endl;
return 0;
}
// 출력결과: 10의 개수: 0
// 값이 존재하지 않으면 count는 0 반환
(4) unique()
범위 [firrst, last) 내에서 연속된 중복 요소를 제거한다.
실제로 컨테이너에서 원소가 삭제되는 것은 아니고, 각 원소의 첫번째 발생만 유지되도록 원소들을 앞쪽으로 덮어씌워 재배열한다. 재배열한 뒤 이후의 영역은 보통 erase()와 함께 완전히 제거한다(그제서야 원소가 삭제됨). erase 안하면 값이 남아있을 수 있다.
unique 함수는 중복 제거 후 마지막 고유 원소의 다음 위치를 가리키는 반복자를 반환한다.
// unique()는 연속된 중복 요소만 제거 (재배열만 함)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 1, 2, 2, 2, 3, 1, 1};
auto newEnd = unique(v.begin(), v.end());
for (auto it = v.begin(); it != newEnd; ++it) {
cout << *it << " ";
}
return 0;
}
// 출력결과: 1 2 3 1
// 주의: 실제 컨테이너 크기는 그대로이고, 중복 제거된 결과는 앞쪽에만 있음// unique()와 erase()를 조합해 실제로 중복 원소 삭제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 1, 2, 2, 3, 3, 3};
v.erase(unique(v.begin(), v.end()), v.end());
for (int val : v) {
cout << val << " ";
}
return 0;
}
// 출력결과: 1 2 3
// erase–remove idiom을 통해 연속된 중복 요소가 완전히 제거됨[3. 효율적인 코드 구현하기]
앞에서 배운 것들을 활용하는 데에 있어서 중요한점이 성능을 고려해야 한다는 것이다. 굳이 쓰지 않는 기능을 가진 컨테이너, 알고리즘 등을 사용할 필요는 없다. 시간 복잡도와 실제 성능을 고려하자.
1) 벡터 vs 덱
벡터와 덱은 둘 다 임의접근이 되기 떄문에 비슷한 컨테이너처럼 보이지만 사실 이 둘의 내부는 완전히 다르다.
벡터 : 배열과 동일하게 메모리가 연속적으로 할당됨. -> 별다른 조치 없이 임의 접근이 가능.
덱 : 맨 앞의 원소와 맨 뒤의 원소를 가리키는 포인터가 있고, 내부적으로 데이터가 여러 개의 청크(chunk)라는 영역으로 쪼개짐.
(1) 맨 앞에 원소를 삭제(추가)하는 경우 -> '덱'을 사용!
벡터의 경우에는 맨 앞에 원소를 삭제(추가)하는 경우 뒤의 원소들이 전부 이동해야 함.
덱의 경우 청크를 나눠서 관리하므로 이동하지 않아도 됨. O(1) 연산.
(2) 임의 접근을 하는 경우 -> 임의 접근을 빈번하게 하는 경우에는 '벡터'를 사용!
벡터와 덱 모두 점근적 상한 기준으로는 O(1) 연산이나, 데이터가 커지면 덱이 불리해지게 됨. 덱의 경우 각 청크가 불연속적이기에 이들을 관리하는 map을 내부적으로 관리하게 되는데, 데이터가 커지면 맵을 통해 청크 위치를 찾고 접근하는 데 필요한 연산 횟수가 증가하기 때문.
2) 정렬이 필요없는데 정렬하는 경우
컨테이너 중 set과 같은 컨테이너는 원소가 삽입될 때마다 자동으로 정렬해준다. 그런데 굳이 정렬을 할 필요가 없다면 사용할 필요가 없다는 뜻이기도 하다. 또한 map의 경우에도 키를 삽입할 때마다 연산이 발생되므로 코딩테스트에서 잘못 사용하면 불리할 수도 있다. 이경우에는 키값을 기준으로 정렬이 필요 없다면 unordered_map 사용을 고려해보아야 한다.
// ---------------- map ----------------
map<int, int> ordered_map;
auto start_map = chrono::high_resolution_clock::now();
for (int i = 0; i < N; ++i) {
ordered_map[i] = i;
}
// ---------------- unordered_map ----------------
unordered_map<int, int> unordered_map;
auto start_umap = chrono::high_resolution_clock::now();
for (int i = 0; i < N; ++i) {
unordered_map[i] = i;
}
3) 특정 원소를 찾는 경우
특정 원소를 찾는 경우에도 컨테이너에 따라 성능 차이가 크게 발생할 수 있다.
벡터는 선형 컨테이너이고, 특정 데이터에 접근하기 위해서는 해당 데이터의 인덱스를 통해 임의 접근해야한다. 다만 인덱스에는 데이터에 대한 특별한 정보가 없어 결국 순차 탐색을 해야한다. O(N).
set과 map은 데이터를 레드 블랙 트리로 관리한다. O(logN).
unordered_set과 unordered_map. unordered가 붙는 컨테이너는 해시 기반으로 관리한다. O(1).
4) 문자열을 결합하는 경우
문자열에 문자를 추가하는 연산의 경우에도 큰 성능의 차이가 발생할 수 있다.
(1) + 연산자 : 매번 새로운 문자열을 다시 만든다. 기존 문자열 길이가 N 이라면, O(N)이다.
(2) += 연산자와 append() 메서드 : 매번 새로운 문자열을 만들지 않고 기존 문자열에 덧붙이는 방식이다. O(1)에 가깝다.
5) auto & 과 auto
반복문을 사용할 때 auto와 auto&로 받는 것은 큰 성능 차이가 발생할 수 있다. auto는 복사가 발생하지만, auto&는 복사가 발생하지 않는다. 다만 auto&로 접근해서 값을 받아올 때 값의 변경이 발생하지 않도록 const auto& 형식으로 보통 같이 사용한다.
*오늘의 코드카타*
자연수 n이 매개변수로 주어진다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. (제한사항 : 3 <= n <= 1,000,000)
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int solution(int n) {
int answer = 0;
int x;
for (x = 2; x < n; x++) {
if (n % x == 1) {
answer = x;
break;
}
}
return answer;
}나머지가 1이려면 최소한 2 이상의 수로 나눠야 하므로 x는 2부터 시작해서 n보다는 작은 반복문 for를 작성했다.
그리고 조건에 맞는 수를 찾으면 멈추도록 break;를 사용했다.
'게임 프로그래밍 공부 > C++ 코딩테스트' 카테고리의 다른 글
| [C++ 코딩테스트 연습] 5. 시뮬레이션 (0) | 2026.05.15 |
|---|---|
| [C++ 코딩테스트 연습] 4. 배열, 정렬 (0) | 2026.05.14 |
| [C++ 코딩테스트 연습] 3. 재귀함수 (0) | 2026.05.12 |
| [C++ 코딩테스트 연습] 1. 필수 문법 (0) | 2026.05.07 |