on my way
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 끊어주기
- C++의 cin/cout이 느린 이유는 C 입출력 버퍼와 C++ 입출력 버퍼를 동기화 시켜야 하기 때문 (그러나 C언어와 혼용 사용 불가하다)
- cin, cout은 묶여있는 (tie) 관계이므로 입력이 들어오기 전에 모든 출력을 방출하기 때문에 속도가 느리다
- 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]로 접근 가능.
- 범위 기반 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>
- sort(s, e, function): O(n log n)
=> 퀵정렬 - stable_sort(s, e, function): O(n log n)
=> 합병 정렬 (sort후에도 값이 같은 원소들의 상대적인 순서유지) - binary_search(s, e, val): O(log n)
=> 이분 탐색 - lower_bound(s, e, val): O(log n)
=> [s, e) 구간에서 val 이상인 첫 값의 위치를 반환 - 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++ 강의,
'algorithm > CodingTest' 카테고리의 다른 글
C++ 알고리즘:: 다이나믹 프로그래밍 (0) | 2021.10.30 |
---|---|
C++ 알고리즘:: 완전 탐색(Brute-Force) & 백트레킹(Backtracking) (0) | 2021.10.24 |
C++ 알고리즘:: 스택(Stack), 큐(Queue), 덱(Deque) (0) | 2021.10.11 |
C++ 알고리즘:: 정렬 알고리즘 정리 (버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬) (0) | 2021.10.03 |
C++ 알고리즘:: 시간 복잡도 Big O (0) | 2021.10.02 |