[Algorithm]C++로 알고리즘 시작하기

이 글은 2021.03.12 에 진행된 코어멤버 수연님의 ‘C++로 알고리즘 시작하기’ 세션을 바탕으로 작성된 블로그 포스팅입니다.

새 창에서 열기  (발표자 노트를 참고하실 수 있습니다)

 

시작하기

💡 왜 알고리즘 문제 해결에서 C++를 많이 사용하나요?

• low-level 언어이므로 속도가 매우 빠릅니다.
• 참고할 수 있는 예제 코드가 많습니다.
• 가끔 C++ 사용을 강제하는 문제가 있습니다.

💡 C를 통한 문제 해결과의 차이점은 뭔가요?

• cin, cout을 통한 입출력
• namespace
• 새로운 타입(string, bool 등)
• 정렬 함수, 자료구조 등이 이미 구현되어 있음(STL)

 

C++ Fast I/O

cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);

C++의 cin/cout이 느린 이유는 C의 입출력 버퍼와 C++의 입출력 버퍼를 동기화시켜야 하기 때문입니다. 또, cin과 cout은 서로 묶여있는(tie) 관계이므로 입력이 들어오기 전에 모든 출력을 방출하는데, 이것도 C++의 입출력 속도를 느리게 하는 원인 중 하나입니다.

위 코드를 추가하여 입출력 스트림의 동기화를 해제하고 untie하게 만들어 입출력 시간을 크게 단축할 수 있습니다.

cout << "hello" << '\n';
// not cout << "hello" << endl;

endl은 개행하는 역할뿐만 아니라 출력 버퍼에 쌓인 내용을 한꺼번에 출력하는 역할(flush)을 합니다. endl을 ‘\n’으로 바꾸어주는 것만으로 실행시간을 단축시킬 수 있습니다.

 

C++ STL

STL은 Standard Template Library(표준 템플릿 라이브러리)의 줄임말로, 다음과 같은 4가지 요소를 포함합니다.

• 컨테이너: 데이터를 저장하는 객체. vector, pair, deque, list, set, map, stack 등
• 알고리즘: 검색, 정렬 등
• 반복자
• 함수자

C++ STL: Container

Vector

#include <vector>
vector<type> name;

• C++의 동적 배열. 삽입 순서에 따라 상대적인 위치를 갖습니다.
• 배열과 동일하게 인덱스를 통해 접근 가능합니다.

 

v.front()	벡터의 첫번째 요소
v.end()	벡터의 마지막 요소
v.push_back()	벡터의 마지막에 새로운 요소 삽입
v.emplace_back()	벡터의 마지막에 새로운 요소 삽입(push_back보다 빠름)
v.pop_back()	벡터의 마지막 요소를 제거
v.erase(index) v.erase(start, end)	벡터의 해당 인덱스 또는 범위에 해당하는 요소들을 제거
v.insert(index, item)	벡터의 해당 인덱스에 요소 삽입
v.size()	벡터의 크기

 

Stack

#include <stack>
stack<type> name;

• 후입선출(LIFO): 가장 나중에 들어간 것이 가장 먼저 나옵니다.
• 짝맞추기 문제에 많이 사용됩니다.

 

s.empty()	스택이 비었는지 확인, 비었으면 true
s.top()	스택의 가장 상위 요소를 리턴
s.push(item)	item을 스택에 추가
s.pop()	가장 최근에 들어간 요소를 스택에서 제거, 반환값 없음
s.size()	스택의 크기

 

Queue

#include <queue>
queue<type> name;

• 선입선출(FIFO): 가장 먼저 들어간 것이 가장 먼저 나옵니다.
• 순서를 고려한 처리가 필요할 때, 특히 BFS(너비 우선 탐색)에서 사용합니다.

 

q.empty()	큐가 비었는지 확인, 비었으면 true
q.front()	큐의 첫 요소를 리턴
q.back()	큐의 마지막 요소를 리턴
q.push(item)	item을 큐에 추가
q.pop()	가장 최근에 들어간 요소를 큐에서 제거, 반환값 없음
q.size()	큐의 크기

 

Pair

#include <utility> // or <vector> or <algorithm>
pair<type, type> name;

• 데이터 쌍을 표현할 수 있습니다.
• 짝을 이루는 데이터를 표현할 때 사용합니다.

 

p.first	p의 첫번째 요소를 반환
p.second	p의 두번째 요소를 반환
make_pair(a, b)	a와 b를 쌍으로 묶는 페어 생성

 

Map

#include <map>
map<type, type> name;

• key와 value가 쌍(pair)로 저장되며, key를 통해 value에 빠르게 접근 가능합니다.
• key는 오름차순으로 정렬되어 저장됩니다.
• key는 중복되지 않으며, 중복되는 key를 사용하려면 multimap 컨테이너를 사용해야 합니다.
• m[key] = value; 형태로 원소를 추가, 수정, 접근 가능합니다.

 

m.insert(pair)	맵에 pair 객체를 삽입
m.size()	맵의 크기
m.find(key)	맵 내에서 key 값을 탐색하여 해당 위치의 반복자 리턴, 없을 시 m.end() 리턴

 

Set

#include <set>
set<type> name;

• 원소의 중복을 허용하지 않습니다.
• 자동적으로 정렬된 상태를 유지합니다.

 

s.insert(val)	셋에 값 삽입
s.find(val)	셋 내에서 val 값을 탐색하여 해당 위치의 반복자 리턴, 없다면 s.end() 리턴
s.erase(val)	셋에 저장된 val 요소 삭제

 

C++ STL: Iterator(반복자)

• 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공합니다.
• 컨테이너와 알고리즘이 하나로 동작하도록 묶어주는 인터페이스 역할을 합니다.

 

C++ STL: Algorithm

• sort(s, e, function): Quick sort
• stable_sort(s, e, function): Merge sort, 같은 값을 가지는 원소들에 대해 상대적인 순서 유지
• binary_search(s, e, val): 이분탐색
• lower_bound(s, e, val): [s, e) 구간에서 val 이상인 첫 값의 위치를 반환
• upper_bound(s, e, val): [s, e) 구간에서 val 값을 초과하는 첫 값의 위치를 반환
• 등등..