알고리즘 문제 풀이를 위한 C++ 카탈로그

이 문서에 대해

C++은 기능이 아주 많은 언어입니다. 포인터처럼 메모리의 주소를 사용자가 직접 다룰 수 있는 인터페이스도 있고 auto처럼 비교적 최근에 추가된 기능들도 있습니다. 어떤 문제가 주어졌을 때 그 문제를 해결하는 과정에서 여러 가지 서로 다른 도구를 사용할 수 있고 실제로 문제를 푸는 많은 분들이 서로 다른 여러 도구들을 사용합니다.

읽고 있는 분들이 C++의 기초적인 문법(변수, 연산, 함수, 반복문, 입출력, 구조체, 포인터 등)을 알고 있다고 가정합니다. 이 문서에서는 문제 풀이 과정에서 효과적으로 사용할 수 있는 문법과 표준 라이브러리의 기능들을 가능한 넓고 다양하게 소개합니다.

문서에서 소개하는 기능들을 모두 공부하려면 많은 시간과 노력이 필요합니다. 자세한 내용을 알아보기 위해서는 링크된 레퍼런스 문서나 다른 학습 자료를 참고하시는 것을 추천드립니다. 이 문서에서 소개한 기능들을 대부분 사용할 수 있게 되면 적어도 문제 풀이 과정에서 프로그래밍 언어에 대한 지식이 부족하다고 느낄 일이 많지 않게 될 것입니다.

제가 제작한 알고리즘 강의 자료에는 소스 코드가 많이 있습니다. 제 코드를 읽는 분들이 항상 제가 사용하는 언어의 기능들을 모두 파악하고 있지는 않습니다. C++에 익숙하지 않거나 사용한 적이 없는 문법이나 컨테이너를 코드에서 보았을 때에 참고할 수 있는 자료로도 사용될 수 있도록 작성되었습니다.

문서에 잘못 설명된 부분이 있으면 제게 말씀해 주시면 (아마 곧) 반영하겠습니다. 그럴 때에는 이 글에 댓글이나 제 프로필의 연락처를 통해 말씀해 주시길 바랍니다.

어떤 컴파일러/버전를 사용해야 하는가

출전하려고 하는 대회나 코딩 테스트에서 사용하는 컴파일러와 같은 것을 사용하는 것이 좋습니다. 적어도 같은 C++ 표준을 사용하는 것을 권장합니다. 백준 온라인 저지의 블로그에 어떤 대회에서 어떤 C++ 컴파일러와 옵션을 사용하는지 대해 잘 정리된 글이 있습니다.

만약 Visual C++ 2019를 사용하고 있다면 사용하고 계신 C++은 C++14 표준이 적용됩니다. 프로젝트 설정에서 언어 표준을 C++17이나 C++20으로 변경할 수 있습니다. 안타깝게도 프로젝트를 만들 때마다 언어 표준이 변경되도록 하는 기능은 Visual Studio 설정에 없습니다.

이 문서에서 소개하는 기능들은 모두 C++14 이상 버전에서 문제 없이 컴파일할 수 있습니다.

기초 타입들

https://en.cppreference.com/w/cpp/language/types

정수를 다룰 때에 주로 32-bit 정수 변수형인 int를 사용합니다. 조금 더 공간 최적화를 원할 때에는 short(16-bit)나 char(8-bit)를 사용하는 경우도 있습니다.

비트 연산

https://en.cppreference.com/w/c/language/operator_arithmetic

정수 자료형들은 비트 연산을 할 때에도 사용합니다. not, and, or, xor 연산에 대해 묻는 문제들이 많이 있고 그런 문제들은 대개 해당 연산의 정의를 문제에 제공합니다.

long long

문제를 풀다 보면 32비트 연산으로 다룰 수 있는 것(약 ±2147483647)보다 큰 수를 다룰 때가 많습니다. 그럴 때는 64비트 정수를 사용해야 합니다. 64비트 정수는 'long long'또는 'long long int'로 선언할 수 있습니다.

64비트보다 큰 정수

64비트보다 더 큰 정수가 필요한 경우는 거의 없습니다. C++ 표준에는 64비트보다 큰 정수 자료형이 없습니다. 64비트 GCC에는 표준과 관계없이 128비트 정수형이 구현되어 있고, '__int128'로 쓸 수 있습니다.

거의 모든 문제는 64비트 정수를 사용해 해결할 수 있도록 출제됩니다. 만약 그것보다 큰 정수형이 필요한 경우에는 정수를 저장하거나 출력하는 방법을 직접 구현해 사용해야 합니다.

개인적으로 긴 정수 연산이 필요한 문제가 나오면 C++ 대신 긴 정수를 지원하는 언어(Java, Python)를 사용하는 편입니다.

unsigned int

unsigned int를 직접 선언해 사용하는 경우는 거의 없습니다. 하지만 STL의 어떤 함수들(예를 들어, vector::size)은 return type이 unsigned int이기 때문에 주의해서 다뤄야 할 때가 많이 있습니다. 예를 들어 아래와 같은 코드를 실행하면 언더플로우가 발생합니다.

#include<iostream>
#include<vector>

using namespace std;

int main() {

	vector<int> A(0);
	auto x = A.size() - 1;
	//unsigned int x

	cout << x;
}

-1을 기대하고 위와 같은 코드를 실행하지만 실제로 출력되는 값은 4294967295입니다.

실수 자료형

실수 자료형(Floating-point)은 32비트인 float와 64비트인 double이 있습니다.

float는 정확도가 끔찍하기 때문에 대개 double만 사용합니다. float의 정확도가 어떤 느낌인지 실험해보고 싶다면 '10000에 0.0001을 10000번 더해서 출력하기'를 float과 double로 각각 계산해 출력해 봅시다.

long double이라는 자료형이 존재하는데, 이는 컴파일러에 따라 다르게 작동합니다. 128비트 실수 자료형이 지원되는 컴파일러에서는 double보다 정확도가 높은 128비트 자료형으로 작동합니다. GCC(64-bit)에서는 128비트 long double을 사용할 수 있습니다. 지원되지 않는 컴파일러라면 double과 다르지 않습니다.

포인터와 레퍼런스

C++로 문제를 푸는 코드를 작성할 때에는 작성자의 기호에 따라 포인터를 전혀 사용하지 않을 수도 있고 자주 사용할 수도 있습니다. 포인터를 사용한다고 해도 다중 포인터처럼 복잡한 구조나 개념을 다루는 일은 드뭅니다.

레퍼런스는 포인터보다 자주 유용합니다. 예를 들어 범위 기반 for문에서 레퍼런스를 사용해 접근하면 원본을 수정할 수 있습니다.

C++ 표준 라이브러리의 컨테이너들을 사용하면 포인터와 유사한 인터페이스인 iterator를 접하게 됩니다.

OOP

OOP(Object-Oriented Programming)에 관련된 기능이나 지향성은 문제 풀이 과정에서 드물게 사용하게 됩니다. 문제 풀이 과정에는 코드 재사용이 자주 발생하지 않습니다.

STL의 컨테이너는 클래스 구조로 되어 있습니다. 그래서 클래스를 사용하는 기본적인 방법은 알아야 합니다.

문제 풀이 중에 구조체나 클래스를 만들게 되는 경우도 있는데, 예를 들어 column이 여러 개인 데이터를 다룰 때에 구조체나 클래스를 사용해 관리하면 편리한 경우가 있습니다. 정렬 가능한 상태를 유지하려면 클래스를 만드는 것보다 pair나 tuple을 사용하는 것이 좋을 때도 많이 있습니다.

구조체로 구현한 템플릿을 사용하게 되는 경우가 있습니다. 예를 들어 아래는 제가 자주 사용하는 사전 작성된 분리 집합(Disjoint Set Union)을 구현하는 코드입니다.

#include<vector>
#include<algorithm>
using namespace std;

struct DSU {
	vector<int> parent, rank;
	DSU(int n) : parent(n), rank(n) {
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}
	int find(int u) {
		if (u == parent[u]) return u;
		else return parent[u] = find(parent[u]);
	}
	void merge(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) return;
		if (rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
		if (rank[u] == rank[v]) rank[v] += 1;
	}
};

이 코드를 그대로 붙여넣으면 7번째 줄의 생성자를 통해 크기가 n인 분리 집합을 생성하고 merge와 find 함수를 통해 이 집합에 접근할 수 있습니다. 이렇게 구조체나 클래스를 미리 작성해 반쯤 캡슐화된 형태로 코드에 넣을 수 있습니다.

OOP를 자주 다루는 분들은 이 구조체의 모든 멤버 변수와 함수가 public인 것이 못마땅할 수도 있습니다. 이는 이후에 구조체를 수정해야 하는 경우에 유리하기 때문입니다. DSU를 사용하는 문제를 푸는 과정에서 'rank'같은 멤버 변수에 접근해야 할 때가 있는데 그럴 때마다 그 변수에 접근하기 위한 멤버 함수를 만드는 건 너무 오래 걸립니다.

접근 지정자는 주로 작성자의 실수를 방지하기 위해 사용합니다. 그런데 우리는 작성하고 있는 코드를 다른 사람이 편집하게 하지 않을 겁니다. 그리고 코드가 200줄을 넘기는 일도 아마 없을 겁니다. 그래서 이렇게 씁니다. 만약 접근 지정자를 엄밀하게 사용하는 코드를 선호한다면 그렇게 템플릿을 만들어서 사용하면 됩니다.

iostream(cin, cout)

https://www.cplusplus.com/reference/iostream/

iostream(cin, cout)은 C++에서 표준 입출력을 처리하는 방법입니다.

stdio(scanf, printf)의 포맷 스트링을 사용하는 방법과 비교하면 여러 가지 장.단점이 있습니다.

빠른 입출력

cin과 cout을 사용해 입출력을 처리하면 버퍼나 동기화와 관련된 처리 때문에 stdio보다 느리게 작동합니다. 프로그램을 시작할 때에 아래 함수들을 실행하면 충분히 빠르게 작동합니다.

아래 함수들에 대해 자세히 설명된 문서를 링크합니다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);

이 최적화 코드는 iostream을 사용해 글자를 10만 개 이상 입력받아야 하는 문제를 풀 때 필수적입니다. 'sync_with_stdio'를 해제한 상태에서 iostream과 stdio를 혼용하면 오작동할 수 있으니 주의해야 합니다.

iostream을 다룰 때에 줄바꿈을 위해 endl을 사용하는 경우가 있습니다. endl은 줄을 바꾼 뒤 버퍼를 비우는 작업을 포함합니다. 대부분 문제는 실행이 끝난 뒤에 출력된 내용들을 비교하기 때문에 버퍼를 자주 비우지 않아도 됩니다. 따라서 endl 대신 '\n'을 사용하는 것이 좋습니다.

precision

https://en.cppreference.com/w/cpp/io/ios_base/precision

https://en.cppreference.com/w/cpp/io/manip/fixed

실수를 다룰 때 출력 방식을 조정하는 방법입니다. 위 문서의 내용을 외울 필요는 없고, 필요할 때마다 참조하면 됩니다.

getline

개행 문자가 나올 때까지 한 줄을 입력받는 함수입니다. 표준 라이브러리에 getline이라는 이름을 가진 함수가 두 가지 있습니다.

• std::getline (string): 스트림으로부터 한 줄 전체를 입력받아 string에 저장합니다.
• std::istream::getline(char*): 스트림으로부터 한 줄 전체를 입력받아 char형 배열에 저장합니다.

std::string을 사용한다면 std::getline을 자주 사용하게 됩니다. 한 줄 단위로 string에 입력한 채로 파싱하면 편리한 문제들이 많이 있습니다.

Iterator

C++의 iteartor는 컨테이너의 원소들에 접근하거나 관리하기 위한 인터페이스입니다. '*' 또는 '->' 연산자를 사용하면 해당하는 원소의 값에 접근할 수 있습니다.

set이나 map과 같은 비선형 자료구조 라이브러리를 다룰 때에는 원소에 순서대로 접근하기 위해 iterator를 사용해야 할 때가 있습니다.

컨테이너에 대해 공부할 때에 해당 컨테이너에서 iterator가 어떻게 작동하는지도 공부하면 좋습니다. 아래 링크에는 자주 사용하는 컨테이너인 vector와 set에서 iterator를 사용하는 간단한 예시가 있습니다.

vector::begin: https://en.cppreference.com/w/cpp/container/vector/begin

set::begin: https://en.cppreference.com/w/cpp/container/set/begin

auto

https://en.cppreference.com/w/cpp/language/auto

auto는 초기화되는 l-value의 타입을 컴파일러가 유추하는 기능입니다. 문제 풀이 과정에서는 타입 이름이 길어서 여러 번 적기 어려운 경우나 코드의 다른 부분에서 타입을 바꿨을 때 auto로 쓴 부분도 함께 변경되기를 원하는 경우에 사용합니다.

C++는 strong-typed 언어입니다. auto로 선언한 변수의 타입은 컴파일할 때 정해집니다. 타입이 모호하다면 컴파일 에러가 발생하거나 컴파일러 경고를 보게 될 수 있습니다.

vector<int> A(n);
for (auto it = A.begin(); it != A.end(); it++) {
	//it의 타입: 'vector<int>::iterator'
}

범위 기반 for 문

https://en.cppreference.com/w/cpp/language/range-for

범위 기반(range-based) 반복문을 사용하면 범위 안에 있는 모든 원소에 대해 반복문이 작동합니다.

이 때 값에 접근할 때와 레퍼런스에 접근할 때에 다르게 작동합니다. 아래 코드의 둘째 줄처럼 배열 내 원소의 레퍼런스에 접근하는 경우에는 원래 값을 수정할 수 있습니다. 아래의 두 입력 방법은 배열 A에 같은 원소를 저장합니다.

vector<int> A(n);
for (auto& a : A) cin >> a;

vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];

범위 기반 반복문을 사용할 때는 원소의 위치를 찾거나 이전/이후 항목에 접근하기 까다롭기 때문에 그런 작업이 필요한 경우에는 범위 기반 반복문을 사용하지 않습니다.

set이나 map을 사전순으로 순회할 때에는 범위 기반 반복문이나 iterator를 사용해야 합니다. 아래 코드를 실행하면 S의 모든 원소를 공백을 사이에 두고 사전 순으로 출력합니다.

set<int> S;
for (auto x : S) {
	cout << x << ' ';
}

std::vector

https://en.cppreference.com/w/cpp/container/vector

vector는 동적 배열 컨테이너입니다. vector를 만들 때에는 크기를 미리 지정할 수도 있고 원소를 하나씩 뒤에 붙여(push_back) 만들 수도 있습니다.

2차원 이상 배열은 벡터 안에 벡터를 넣어 구현합니다. 아래는 2차원 정수 배열의 크기와 내용을 입력받는 코드입니다. 첫 번째 줄에는 행과 열의 수인 n과 m이 입력되고, 그 다음 줄부터 총 n줄에 걸쳐 각 줄에 정수 m개가 입력됩니다.

int n, m;
cin >> n >> m;
vector<vector<int>> A(n,vector<int>(m));

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> A[i][j];
	}
}

std::string

https://en.cppreference.com/w/cpp/string/basic_string

C에서처럼 char형 배열을 사용해 문자열을 관리하는 것보다 std::string을 사용하는 것이 강력하고 안전합니다.

char형 배열에서 문자열의 길이를 구하는 strlen 함수를 실행했을 때 처음부터 마지막까지 글자 수를 세야 하기 때문에 시간이 오래 걸리지만 std::string::length는 미리 저장된 길이를 가져오기 때문에 빠르게 실행됩니다.

string에 관련된 함수는 아주 많이 있습니다. 이런 함수들을 한 번에 많이 익히려고 하지 말고 문제를 해결하는 데에 필요한 것을 매번 찾아서 사용하는 것을 추천합니다.

std::pair

https://en.cppreference.com/w/cpp/utility/pair

std::pair를 사용해 값들을 묶으면 연산자를 재정의하지 않고 비교나 정렬할 수 있습니다. 원소들을 묶어서 관리하고 싶은데 정렬 함수를 만들고 싶지 않을 때 자주 사용합니다.

타입이 같은 두 pair를 비교하면 첫 번째 원소(first)를 먼저 비교해 값이 서로 다르다면 그 결과를 return합니다. 첫 번째 원소가 같다면 두 번째 원소(second)를 비교한 결과를 return합니다. 이런 비교 연산의 작동 방식은 C++ 레퍼런스에 잘 설명되어 있습니다.

자주 사용하는 라이브러리

문제 풀이 과정에서 자주 사용하는 라이브러리들을 나열합니다. 모두 한 번에 공부하기보다는 이런 라이브러리가 있다는 것을 파악해둔 뒤에 나중에 문제를 푸는 과정에 어떤 기능이 필요하게 되면 연습하면 좋습니다.

• 선형 자료구조들: stack, queue
• 이진 탐색 트리 기반 자료구조들: map, set, multimap, multiset
• 우선 순위 큐(힙): priority_queue
• 해시 기반 자료구조들: unordered_map, unordered_set

algorithm 헤더

• 정렬: sort
• 원소 관리: swap, reverse, fill, rotate
• 최소, 최대: max, min
• 최대/최소 원소 찾기: max_element, min_element
• 중복 원소 제거: unique
• 이분 검색: lower_bound, upper_bound, binary_search
• 순열 생성: next_permutation, prev_permutation
• 무작위로 섞기: shuffle

functional 헤더

• 연산자 함수: greater, less 등

주로 sort에서 정렬 순서를 바꿀 때 사용합니다.

numeric 헤더

• 원소의 합: accumulate

C++17부터는 numeric 헤더에 최대공약수와 최소공배수(gcd, lcm) 함수가 정의되어 있습니다.

다른 기능들

아래는 제가 작성하는 코드에는 사용하지 않지만 취향에 따라 문제풀이에 사용해볼 만한 것들입니다.

• for_each: 좋은 기능이라고 생각합니다. 사용하지 않는 이유는 그저 제가 기존 for문 사용법에 너무 익숙하기 때문입니다.
• 람다 표현식: 이름 없는 함수를 만드는 기능입니다. 정렬 함수의 인자로 사용되는 비교 함수처럼 짧은 구간에서 잠시 함수를 정의할 때 유용합니다. 람다 함수를 사용하는 코드를 읽으려면 람다 함수에 대한 지식이 필요합니다. 그래서 강의에 쓰기에 곤란한 기능입니다. 강의에 쓸 일이 없으니 개인적으로 평소에도 잘 쓰지 않게 되었습니다.
• tuple: pair를 일반화한 형태입니다. 원소를 여러 개 가진 클래스입니다. 이 때 원소의 갯수와 타입은 컴파일 시점에 정해집니다. 기능적으로 pair의 상위 호환이지만 멤버 함수를 다루는 방법이 꽤 복잡합니다. 원소 3개 까지는 pair 안에 pair를 넣어 만들어도 그다지 끔찍하지 않지만 그것보다 많아지면 tuple을 사용하고 싶어집니다.
• array: 정적 배열 컨테이너입니다. C-style 배열과 비고하면 배열 끝 체크가 내장되어 있고 함수의 인자로 넘기기 편리합니다. 동적 배열인 vector만 사용해도 필요한 모든 것을 만들 수 있지만 array를 선호하는 분들도 있습니다.
• list: 연결 리스트 컨테이너입니다. deque나 vector로 대부분 처리할 수 있기 때문에 개인적으로 자주 사용하지 않지만 구현 방법에 따라 list 컨테이너를 사용하면 편리할 때가 있습니다.
• regex: 정규 표현식 라이브러리입니다.
• bitset: 비트 연산에 특화된 자료구조입니다.