C++ 알고리즘:: Fast I/O, C++ STL

I. 시작하기

왜 알고리즘 문제 해결에서 C++을 많이 사용하는가?

⇒ low-level 언어라 속도가 빠르다. (속도가 중요하지 않고 다양한 라이브러리와 함수, 쉬운 문법을 원한다면 Python으로 알고리즘을 시작해도 좋다.)

⇒ 참고 예제 코드가 많다.

 

C와 C++의 차이점?

⇒ cin, cout을 통한 입출력 방향, namespace, i/o header변화, string, bool type

C는 char, C++은 string

정렬 함수(정렬, 이진탐색), 자료구조(스택, 큐) 가 이미 구현되어있다. (C++ STL)

C언어의 표준 함수를 모두 사용 가능하다. #include <stdio.h>

 

namespace

식별자간의 이름 충돌을 위한, 모든 식별자가 고유하도록 보장하는 코드 영역.

같은 영역 안에 식별자간 이름 충돌을 막는 장치이다.

범위 지정 연산자 ::를 사용한다.

설정해두면 해당 연산자를 써주지 않아도 됨.

 

C++의 입출력

C: scanf(), printf()

→ stdio.h 헤더, 굉장히 빠름, 포맷 지정자가 필요

C++: cin, cout

→ iostream 헤더, 상대적으로 느림, 포맷 지정자 사용 필요 없음

⇒ 유일한 단점이지만 Fast I/O로 해결 가능!

 

 

II. C++ Fast I/O

Why Fast I/O?

데이터 입출력은 프로그램의 실행시간 중 상당 부분을 차지한다. 입출력 속도를 빠르게만 해도 프로그램 실행시간을 줄일 수 있다.

방법1. cin/cout대신 scanf/printf를 사용

한다. iostream에 cstdio도 포함되어 있어 헤더를 추가할 필요가 없다.

방법2. sync 끊어주기

1. C++의 cin/cout이 느린 이유는 C 입출력 버퍼와 C++ 입출력 버퍼를 동기화 시켜야 하기 때문 (그러나 C언어와 혼용 사용 불가하다)
2. cin, cout은 묶여있는 (tie) 관계이므로 입력이 들어오기 전에 모든 출력을 방출하기 때문에 속도가 느리다
3. ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

방법3. endl대신 '\n'을 사용.

endl은 개행역할 뿐만 아니라 출력 버퍼에 쌓인 내용을 한 번에 출력하는 flush역할을 해서 실행 시간이 오래 걸림

 

 

III. C++ STL

STL?

: standard template libabry

• 컨테이너: (자료구조) 데이터를 저장하는 객체. vector, pair, deque, list, set, map, stack 등
• 알고리즘: 검색 lower_bound(), upper_bound(), binary_search()이나, 정렬 sort() 등
• 반복자(iterator) : 컨테이너 안에 element주소를 가리킴. (포인터와 비슷한 개념). 같은 로직의 모든 컨테이너를 순회할 수 있음
• 함수자(functr)

 

STL Container: Vector

배열 크기가 동적으로 할당되는 배열. (C-amollac)

인덱스를 통해 접근이 가능하다.

 

C++ STL: Vector의 선언과 사용법

#include <vector>
vector<class or type> name;

vector v; //int 자료형 담는 벡터 생성
vector v(4); //크기 4인 int 벡터 생성
vector v = {3,4,7}; //int형 벡터 생성 및 초기화
vector v[1001]; //int형 벡터 배열 생성
vector v; //2차원 벡터 생성
vector<pair<int, long long>> v; //pair 자료구조 담은 벡터 생성

 

Vector 주요 메서드

v.front(), v.back() 맨앞, 맨뒤에 접근
v.push_back(item), v.emplace_back(item) 새로운 요소 삽입 (emplace는 메모리 재할당이 없어서 push_back보다 삽입 시간이 적음)
v.pop_back() 벡터 마지막 요소 제거
v.erase(index), v.erase(start, end) 벡터 중간요소 제거 (시간복잡도가 커서 잘 안씀)
v.size() 벡터의 사이즈 확인 가능

 

반복문으로 vector 순회하기

1. 시작 인덱스, 종료조건, 증감연산 명시

**for int i=0; iv.size(); i++){}** 

: i는 벡터의 인덱스이며, v[i]로 접근 가능.

1. 범위 기반 for문

**for (auto i: v){}**

: i는 벡터 요소 값이며, 시작 종료 조건을 알려주지 않아도 된다. 범위 기반 for문에서는 배열 요소 값을 변경할 수 없다.

 

언제 벡터를 사용하는가?

트리 그래프의 구조를 표현할 때!

vector v[MAX_SIZE];

i번째 벡터 배열에는 i번째 노드와 연결되어 있는 노드 번호를 push함으로써 노드 연결 관계를 표현할 수 있다.

동적 배열 자료구조가 필요한 상황

 

 

STL Container: Stack

후입선출(LIFO)

짝맞추기에 많이 쓰임

#include <stack>
stack <class or type> name

stack<int> s; //int 자료형 담는 stack)
stack<long long> s; //long long 자료형 담는 stack)

s.empty() //스택이 비었는지 확인, 비었으면 true, 비지 않으면 false
s.top() //스택의 가장 상위 요소 리턴
s.push(item) //item을 stack에 추가
s.pop() //가장 최근에 들어간 요소를 스택에서 제거, 반환값이 없으니 항상 s.top()을 통해 미리 값을 저장해야함
s.size() //stack의 크기

 

 

STL Container : Queue

선입선출(FIFO): 가장 먼저 들어간 것이 가장 먼저 나옴

순서를 고려한 처리가 필요할 때, 특히 BFS(너비 우선 탐색)에서 사용

#include <queue>
queue<class or type> name;

queue<int> q;
queue<pair<int, int>> q;

q.empty() //큐가 비었는지 확인, 비었으면 true, 비지 않으면 false
q.front() //큐의 첫 요소를 리턴
q.back() //큐의 마지막 요소를 리턴
q.push(item) //item을 큐에 추가
q.pop() //가장 첫 요소를 큐에서 제거, 반환값이 없으니 항상 q.front()을 통해 미리 값을 저장해야함
q.size() //큐의 크기

 

 

STL Cotainer: Pair

두 요소를 하나의 요소로 취급하는. 짝을 이루는 데이터를표현할 때 사용. 데이터의 쌍을 표현

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

pair<int, int> p;
pair<int, Person> p; //int값과 Person객체를 묶는 pair

p.first() //페어 p의 첫번째 요소 반호나
p.second()
make_pair(a,b) //a,b를 쌍으로 묶는 pair 생성

언제 사용? 가중치가 있는 그래프를 표현할 때 벡터와 함께 사용. 특히 다익스트라 문제를 해결할 때. 엘레멘트의 우선순위

 

STL Container: Map

key와 value가 쌍(pair)로 저장되며, key를 통해 value에 빠르게 접근 가능. (파이썬의 틱셔너리 처럼)

key는 오름차순으로 정렬되어 저장되며,key는 중복되지 않는다. (중복 key는 multimap 컨테이너에서 사용가능)

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

map<int, int>, m;

m.insert(p) //맵에 pair객체인 p를 삽입
m.size() //맵 크기
m.find(key) //맵 내에서 key라는 키를 가진 요소의 위치(반복자)를 리턴, 없을 시 m.end() 리턴
m[key] = value; //명령어를 통해 원소 (key, value)를 추가, 수정 가능

언제? 특정 키워드에 대한 정보를 저장하고 빠르게 참조해야 할 때 사용한다.

 

 

STL Container: Set

원소 중복 허용 하지 않음, 삽입 순서 상관없이 자동으로 정렬 상태 유지. (수학의 집합). 선형자료구조(벡터)에 비해 속도 용이

#include <set>
set<class or type> name;

• set s;

s.insert(value) //s에 값 삽입
s.find(value) //s 내에서 value값을 탐색하여 해당 위치의 iterator 반환, 없다면 s.end()반환
s.erase(k) //s에 저장된 val요소 삭제

언제? 요소들을 중복되지 않게 정렬된 상태로 저장하고 싶을 때.

중복없는 vector를 만들고 싶을 때 assign() 메서드와 함께 사용.

 

 

STL Iterator(반복자)

컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법 제공.

컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할 (컨테이너 전용 포인터)

• Iterator는 STL 컨테이너의 메모리 상 주소를 가리킨다.

set s;

s.begin(), s.end() //끝의 다음 주소를 가리키는 것!

vector은 +연산이 가능함

• Iterator를 통한 컨테이너 순회

vector<int>::iterator iter;
for(iter = v.begin(); iter != v.end(); iter++){
        cout<<*iter<<' ';
}

container::iterator 타입의 반복자를 선언하여 컨테이너 전체를 순회할 수 있음, (포인터 처럼) 애스터리스크(*)를 붙여 컨테이너 내 요소에 접근할 수 있다

• auto 타입(타입 추론)을 통해 더 간단하게 코드 작성 가능

for(auto iter=v.begin(); iter!=v.end(); iter++){
        cout<<*iter<<' ';
}

 

 

STL Algorithm

정렬, 이진탐색, upper&lower bound, swap 등

#include <algorithm>

1. sort(s, e, function): O(n log n)
   => 퀵정렬
2. stable_sort(s, e, function): O(n log n)
   => 합병 정렬 (sort후에도 값이 같은 원소들의 상대적인 순서유지)
3. binary_search(s, e, val): O(log n)
   => 이분 탐색
4. lower_bound(s, e, val): O(log n)
   => [s, e) 구간에서 val 이상인 첫 값의 위치를 반환
5. upper_bound(s, e, val): O(log n)
   => [s, e) 구간에서 val 값을 초과하는 첫 값의 위치를 반환

lower_bound와 upper_bound로 값이 같은 원소들 중 시작과 끝에 있는 원소들의 위치를 알 수 있다.

upper_bound - lower_bound = 컨테이너 내 해당 변수가 몇 개 인지

 

 

sort() 다루기

1. sort(s, e, function) : O(n log n)

• 구간[s, e)에서 정렬
• function은 비교함수, 옵션

2. stable_ sort(s, e, function) : O(n log n)

• 값이 같은 원소들의 상대적인 순서 유지
• 구간[s, e)에서 정렬
• function은 비교함수, 옵션

배열: sort(arr, arr+length, function)

벡터: sort(v.begin(), v.end(), function)

function은 선택사항. 비교함수 직접 선언하여 오름차순아닌 다른 기준으로도 배열과 벡터를 정렬 가능.

마지막 주소에 +1을 해주어야 한다. (백터는 아님)

 

 

정렬함수 이용하기 : greater, less

#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

int main(){
  int myints[] = {32,71,12,45,26,80,53,33};
  vector<int> myvector (myints, myints+8);

  sort (myvector.begin(), myvector.end(), greater<int>());
}

less : 첫번째 인자가 두번째 인자보다 작으면 true 반환

⇒ 오름차순

greater : 첫번째 인자가 두번째 인자보다 크면 true 반환

⇒ 내림차순

 

커스텀 정렬: 정렬 함수의 세번째 인자 이용

#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main(){
  int myints[] = {32,71,12,45,26,80,53,33};
  vector<int> myvector (myints, myints+8);

  // using function as comp, ascending order
  sort(myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)
}​

 

 

 

출처: 1. GDSC 남수연님 C++ 강의,

        2. https://jisun-rea.tistory.com/entry/c-sort-%ED%95%A8%EC%88%98-%EB%82%B4%EB%A6%BC%EC%B0%A8%EC%88%9C-%EC%BB%A4%EC%8A%A4%ED%85%80-%EC%A0%95%EB%A0%AC

[c++] sort 함수 / 내림차순 / 커스텀 정렬