PS에 사용되는 C++ 기능 정리

C++의 Standard Template Library에는 C언어보다 훨씬 많은 함수와 기능들이 있기 때문에, 이들을 모두 익히는 것은 불가능하다. 하지만 PS에 사용되는 함수와 자료구조들은 굉장히 한정적이다. 이에 이들을 간략히 정리하고자 한다. 다른 사람들도 볼 수 있게 해서 문제를 풀다가 필요한 기능에 해당하는 C++ 함수를 찾아볼 수 있도록 하고, 나도 가끔씩 C++의 함수가 헷갈리기 때문에 정리해 두고 참고용으로 사용하기 위함이다. 나는 C++ 언어 자체는 깊게 모르고, PS에 사용되는 기법들만 익히는 정도이기 때문에, 이론적인 내용에는 오류가 있을 수 있으며 오류를 발견하면 댓글로 달아주면 감사하겠다.

 

iterator

객체지향형 프로그래밍 언어인 C++의 가장 큰 특징은 class와 template라고 볼 수도 있겠지만, 나는 이러한 기능들을 사용해본 적이 한 번도 없다. PS에 사용되는 C++의 기능은 container과 algorithm 정도이다. container은 간단한 자료 구조들을 미리 만들어 놓은 것으로, iterator의 개념을 알아야 이용할 수 있다. algorithm은 C언어로 구현되는 주요 알고리즘들을 표준함수로 정의한 것이므로 어렵지 않다. 그래서 먼저 container 개념을 소개하고자 한다.

iterator은 포인터(배열에만 사용)의 container 버전이다. 어떤 (container + 자료형) Type에 대해

Type::iterator it;

와 같이 선언한다. iterator과 포인터는 표기도 매우 유사하여, *it는 it가 가리키는 값을 의미한다. 그런데 iterator과 포인터는 중요한 차이점이 있다. 포인터 ptr은 ptr+n(n은 정수)와 같은 연산이 항상 가능하였다. iterator은 자료구조에 따라 다르다.

- bidirectional iterator은 왼쪽 또는 오른쪽으로 한 칸 이동하는 것만 가능하며, 이 외에는 순서가 없다.

- random access iterator은 포인터처럼 순서와 값이 있다.

구체적으로 말하자면, bidirectional iterator r과 s에 대해서는 다음의 연산만 가능하다.

r++, ++r, r--, --r, r==s, r!=s

순서가 없기 때문에 r<s같은 비교연산은 불가능하다.

반면, random access iterator r과 s에 대해서는 다음의 연산이 모두 가능하다. 포인터처럼 생각하면 된다.

r++, ++r, r--, --r, r==s, r!=s, r+n, r-n, r+=n, r-=n, r-s, r<s, r>s, r<=s, r>=s

r-s는 r과 s 사이의 거리를 의미한다. 물론, r-s 이후의 연산은 r과 s가 같은 container에 해당할 때만 유의미하다.

 

container은 다음의 두 가지가 있으며, 각각에 대한 설명은 나중에 하겠다.

- sequence container은 배열처럼 선형으로 배치된다.

- associative container은 키(key) 값에 의해 정렬된 상태가 유지된다.

선형은 왜 sequence container의 특징인가? associative container도 쓸 때는 선형처럼 쓰지만, 실제로 정렬된 상태를 동적으로 유지하려면 Red-Black Tree와 같은 비선형 자료구조를 쓰기 때문이다.

 

선형으로 저장하는 container

선형으로 저장하는 container 중 대표적인 vector부터 소개하겠다.

vector은 끝에서의 삽입과 삭제가 효율적으로 가능하며 random access iterator을 제공하는 container이다. '효율적으로'라는 말은 배열의 크기 N에 대해 O(1)에 가능하다는 의미이다. 선언할 때에는 다음과 같이 선언한다. 선언 이후에 벡터의 초기상태는 비어있다.

vector<Type> vec;

Type는 형태로, int나 float 같은 것이어도 되고 구조체여도 된다. 위와 같이 정의된 vector은 길이 제한이 없다. 한편, 길이 n짜리 vector을 만들고 싶으면 다음과 같이 정의한다.

vector<int> a(n);

여기서 n은 변수여도 된다. container 들의 배열도 가능하며, 다음과 같이 선언한다.

vector<int> b[10];

여기서는 배열이므로 당연히 대괄호 안은 상수여야 한다. 소괄호와 대괄호의 차이에 유의해야 한다.

vector에 접근하는 방법은 배열과 거의 유사하다. 즉, a[0]은 a의 첫 원소를, a[3]은 a의 네 번째 원소를 의미한다. b[2][3]이라고 하면 벡터 b[2]의 네 번째 원소를 의미하는 것이다. 이러한 접근이 가능함은 vector이 random access iterator을 제공함을 암시한다. vector에 대한 몇 가지의 함수를 아래에 소개한다. 함수를 사용할 때에는 구조체에서 하는 것처럼 벡터 이름 옆에 점을 찍고 함수 이름을 쓴다. 예를 들어 a의 시작 iterator은 a.begin()이다.

함수	기능		시간복잡도
begin	첫 원소의 iterator 반환		상수
end	마지막 원소 다음의 iterator 반환; *(a.end())는 오류		상수
empty	비어 있으면 true, 아니면 false 반환		상수
size	벡터에 담긴 원소의 개수 반환		상수
front	첫 원소 반환; a.front() == a[0]		상수
back	마지막 원소 반환; a.back() == a[a.size()-1]		상수
clear	벡터를 비움		배열의 길이에 선형
push_back(v)	벡터의 마지막 원소 뒤에 원소 v를 삽입		amortized 상수
pop_back(v)	벡터의 마지막 원소를 삭제		amortized 상수
insert(it, v)	iterator it 다음 위치에 v를 삽입		배열의 길이에 선형
erase(it)	iterator it에 있는 원소를 삭제		배열의 길이에 선형

표에서 볼 수 있듯이 끝에서의 삽입과 삭제는 상수 시간이지만, 중간에서의 삽입과 삭제는 선형 시간이다.

iterator을 이용하여 벡터를 처음부터 끝까지 돌려면,

for(vector<int>::iterator it = a.begin(); it != a.end(); it++){ }

로 하면 된다.

다음으로 deque를 소개하겠다.

deque은 시작과 끝에서의 삽입과 삭제가 효율적으로 가능하며 random access iterator을 제공하는 container이다.

deque는 vector과 시작에서의 삽입과 삭제가 가능하다는 것 말고는 거의 똑같다. 함수도 vector의 함수가 모두 있으며 다음이 추가된다.

push_front(v)	덱의 맨 앞 원소 앞에 원소 v를 삽입	amortized 상수
pop_front()	덱의 맨 앞 원소를 삭제	amortized 상수

deque에서 접근할 때는 주의할 점이 있다. deque<int> a; a.push_back(3); a.push_back(5); a.push_back(7); 을 했다고 하자. 그러면 이때 a[1] = 5이다. 그런데 여기서 a.pop_front(); 를 했다고 하자. 이제는 a[1] = 7이 된다. 즉, deque에서는 시작에서 삽입과 삭제가 가능하므로, 새로운 원소를 추가하지 않았는데도 a[i](i는 고정)가 달라질 수 있다. 나는 deque를 사용하는 문제에서 습관적으로 a[i]를 쓰고, 맨 앞에서 삭제를 하고, 동일한 원소를 참조할 때 a[i]를 또 써서 틀린 적이 많다.

마지막으로 list를 소개하겠다.

list은 아무 위치에서의 삽입과 삭제가 효율적으로 가능하며 bidirectional iterator을 제공하는 container이다. list는 deque이 가지는 모든 함수를 가지지만, insert와 erase 함수가 amortized 상수라는 점만 다르다. list는 bidirectional iterator을 제공하므로, list<int> a; 에서 a[3]과 같은 접근을 해서는 안 된다. 반드시 주어진 함수들을 이용해서 접근해야 한다. 예를 들어, a[3]의 값을 val에 저장하고 싶으면 list<int>::iterator it = a.begin(); 에 it++; 를 3번 한 다음에 *it를 호출해야 할 것이다. it+3과 같은 연산이 안되기 때문이다.

 

정렬된 상태가 유지되는 container

정렬된 상태가 유지되는 container에는 set과 map이 있다.

set은 집합의 원소가 곧 키 값이고 bidirectional iterator을 제공하는 container이다. set은 그 이름(수학에서 집합)으로 알 수 있듯이, 중복된 원소를 허용하지 않는다. set을 정의할 때는 다음과 같이 사용한다.

set<type, comp> s;

type는 자료형이고, comp는 자료를 비교하는 기준이 되는 비교함수다. 비교함수란 두 자료 a, b를 입력받아 a < b이면 1을 반환하고, a > b 이면 0을 반환하는 함수다. 그런데 int 같은 경우에는 이미 비교함수가 내재되어 있어서 comp를 생략하고 그냥

set<int> s;

로 정리하면 된다.

set도 기본적인 함수들은 선형으로 저장하는 container 들과 유사하다. 그러나 push_back, pop_back 같은 함수는 없고, 다음과 같이 집합에 원소를 삽입하고 삭제하고 원소인지 확인한다.

함수	기능	시간복잡도
insert(v)	v를 집합에 추가(v가 이미 있으면 아무 일도 일어나지 않음)	배열의 길이의 로그
erase(it)	iterator it가 가리키는 원소를 집합에서 제거	배열의 길이의 로그
find(v)	v가 있는 집합의 iterator을 반환(v가 없으면 s.end() 반환)	배열의 길이의 로그
count(v)	집합에 v의 개수 반환; s.count(v) == (s.find(v)==s.end() ? 0 : 1)	배열의 길이의 로그

map은 키 값이 별도로 지정되고 bidirectional iterator을 제공하는 container이다. map은 그 이름(수학에서 함수를 사상이라고도 하며 사상이 mapping임)으로 알 수 있듯이, map에 담긴 모든 키 값의 집합을 정의역으로 하는 함수로도 볼 수 있다. map을 정의할 때는 키와 데이터를 다음과 같이 정의해야 한다.

map<type_key, type_value> a;

a[key] = value는 (key, value)를 mapping 하여 a에 저장한다는 의미이다. 여기서 key가 이미 있는 값이면 key에 해당하는 함수값 a[key]를 value로 바꾸게 된다.

multiset과 multimap은 각각 set, map과 모든 것이 동일하나, 중복된 키 값을 허용한다. multiset에서는 count 함수가 원소가 있는지 없는지 이상의 정보를 제공하게 될 것이다.

container adapters

container 의 기능 중 일부만을 발췌하여 자주 사용하는 자료구조를 만들어 놓은 것이 container adapter이다. stack(스택), queue(큐), priority_queue(최대힙) 등이 있다. queue는 deque에서 push_front와 pop_back이 없어져 있는 구조라고 보면 된다. priority_queue와 stack에서는 삽입 및 삭제가 뻔하며, 접근되는 위치도 뻔하므로, push_back, pop_back, back 대신에 다음의 함수들을 사용한다.

push(v), pop(), top()

priority_queue는 최대 힙이므로 모든 기능이 로그 시간이 된다. 중간에서의 접근은 세 자료구조 모두 불가능하다. 이름도 직관적이고, 매우 익숙한 자료구조이므로 구체적인 설명은 생략한다.

이상의 container 등을 정리하면 다음과 같다.

container	정렬 여부	iterator 종류	시작 접근	끝 접근	중간 접근
vector	X	아무 데나 접근	X	삽입과 삭제	시간이 오래 걸림
deque	X	아무 데나 접근	삽입과 삭제	삽입과 삭제	시간이 오래 걸림
list	X	왼쪽 오른쪽만 접근	삽입과 삭제	삽입과 삭제	삽입과 삭제
(multi)set	O	왼쪽 오른쪽만 접근	무의미함
(multi)map	O	왼쪽 오른쪽만 접근
stack	X	무의미함	X	삽입과 삭제	불가능
queue	X		삭제만	삽입만	불가능
priority_queue	맨 위에만 최댓값		무의미함

algorithms

여러 가지 알고리즘이 표준함수로 정의되어 있다. 이중 몇 가지만을 소개하고자 한다.

함수	기능	시간복잡도
sort(it1, it2)	it1부터 it2 하나 앞까지를 오름차순 정렬; sort(a.begin(), a.end())는 a 전체 정렬	O(N log N)
sort(it1, it2, comp)	it1부터 it2 하나 앞까지를 비교 함수 comp 기준으로 오름차순 정렬	O(N log N)
lower_bound(it1, it2, v)	it1부터 it2 하나 앞까지에서 v 이상이 등장하는 첫 위치의 iterator 반환	random access iterator인 경우, O(log N) bidirectional iterator인 경우, O(N)
upper_bound(it1, it2, v)	it1부터 it2 하나 앞까지에서 v 초과가 등장하는 첫 위치의 iterator 반환	random access iterator인 경우, O(log N) bidirectional iterator인 경우, O(N)
next_permutation(it1, it2, v)	it1부터 it2 하나 앞까지의 원소를 가지고 만들 수 있는 순열 중 사전순으로 다음에 오는 것(이미 마지막 순열이면 첫 순열)으로 해당 부분을 바꾼 후, 해당 순열이 마지막 순열이면 false, 아니면 true를 반환	O(N)
prev_permutation(it1, it2, v)	next_permutation과 동일하나 이전 순열로 바꾸고, 이미 첫 순열이면 false 반환	O(N)

lower_bound, upper_bound는 C언어로 구현되는 이분 탐색에 해당한다. 단, set처럼 bidirectional iterator의 경우 이분 탐색이 불가능하므로 시간복잡도가 O(N)임에 유의해야 한다. (나는 문제를 풀 때 lower_bound가 set에서 O(log N) 이라고 착각했다가 망한 적이 있다.) next_permutation, prev_permutation은 자주 사용하지 않지만, 나는 가끔 백트래킹(backtracking; bruteforcing) 문제에서 재귀를 돌리기 귀찮을 때 이 함수들을 사용한다.

기타 기능들

이 외에 내가 자주 사용하는 유용한 기능들을 정리하고자 한다.

먼저, 구조체에서 constructor과 비교함수를 정의하는 것이 C++에서 가능하다. 예를 들어, 다음과 같은 구조체가 있다고 하자.

struct A{
    int a;
    int b;
    A(int t1, int t2){
        a=t1;
        b=t2;
    }

    bool operator<(A const &v) const{

         return b < v.b;

    }
};

구조체 A 내부의 A가 constructor 이다. 여기서 A(3, 5)를 호출하면, t1=3, t2=5가 a=3, b=5로 전달되어 이렇게 a와 b가 짝지어진 형태가 된다. vector<A> vec;과 같이 선언한 후, A.push_back(A(3, 5)); 와 같은 코드도 가능하다.

bool operator<는 연산자 '<'를 정의한다. 즉, 비교 기준을 정의한다. 이때, 비교는 두 대상이 하는 것이므로, 현재 구조체 내의 대상과 다른 구조체 내의 대상을 비교한다. 여기서는 다른 구조체를 v로 받았으므로, (나의 b) < (다른 구조체의 b)이면 1을 반환하고, 아니면 0을 반환한다. 이는 'b가 작을수록 작은 값이다'라는 비교기준을 세운 것이다. 이렇게 구조체 내부에 비교기준을 정해두면, sort 함수에서 comp 항을 넣지 않아도 된다. 이미 자료형 내에 비교함수가 내재돼있기 때문이다.

 

다음으로, 단순한 순서쌍인데 구조체를 만들기 귀찮으면 pair이나 tuple을 사용한다.

pair<type1, type2> : 두 자료의 순서쌍이다. pair<int, float> a; 와 같이 선언한 후, a.first는 첫번째 자료, a.second는 두번째 자료가 된다. constructor은 make_pair로, vector<pair<int, float> > a; 에서 a.push_back(make_pair(5, 1.23)); 을 하면 순서쌍 (5, 1.23)이 추가된다.

tuple<type1, type2, type3> : 세 개 이상의 자료의 순서쌍이다. 여기서는 세 개를 예시로 들었다. pair<int, int, int> a; 와 같이 선언한 후, get<n>(a) (n은 정수)로 접근한다. 여기에서 n은 몇 번째에 해당하는지에 대한 번호이며 0부터 시작한다. constructor은 make_tuple로, vector<tuple<int, int, int> > a; 직후 a.push_back(make_tuple(2, 3, 4)); 을 하면 순서쌍 (2, 3, 4)가 추가된다. 이때 get<0>(a.front())는 2, get<2>(a.front())는 4이다.

 

마지막으로, string은 문자열을 유용하게 처리하게 해준다. string s = "ABC"; 와 같이 선언하며, 접근 방식은 똑같이 str[i]이다. str1 < str2(str1이 str2보다 사전순으로 앞선가?)와 같은 비교연산도 가능해진다. 다음의 함수들은 문자열을 다루는 것을 보다 편리하게 해준다.

함수	기능	시간복잡도
front()	맨 앞 문자	상수
back()	맨 뒤 문자	상수
size()	길이	상수
substr(idx, len)	idx 번째(0부터 셈)에서 시작하여 길이 len인 부분문자열을 반환함	O(len)
push_back(c)	맨 뒤에 문자 c를 추가	상수
pop_back()	맨 뒤에서 문자 하나 삭제	상수

 

함수들이 들어 있는 헤더 파일

함수들이 들어 있는 파일을 언급하고 글을 마무리하겠다.

기본적으로 알고리즘 함수들은 다 <algorithm> 파일에 있다. 자료 구조에 대한 파일 이름은 해당 자료구조 이름과 동일하다. 다만, priority_queue는 <queue>에 포함, multiset은 <set>에 포함, multimap은 <map>에 포함, pair은 <algorithm>에 포함된다. 따라서 이 글에 나온 모든 기능을 사용하려면 다음과 같을 것이다.

 

#include <cstdio>

#include <algorithm>

#include <vector>

#include <deque>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <tuple>

#include <string>

using namespace std;

 

C++의 <iostream>으로 입출력을 하는 것은 나는 선호하지 않는다. 왜냐하면 cin, cout 함수가 느리기 때문이다. 한번은 printf, scanf로 입출력을 하면 될 것을 cin, cout으로 썼다가 시간 초과가 난 적이 있었다.