본문 바로가기

STL

 (12)
[BOJ] 1822번 차집합 (C++) https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m, k; cin >> n >> m; set s; for(int i = 0; i > k; s.insert(k); } for(int j = 0; j < ..
[C++] STL - 정렬 알고리즘 함수 (sort, stable_sort, binary_search) 정렬 알고리즘 함수는 컨테이너의 지정된 범위의 요소들이 정렬되도록 컨테이너를 변경하는 함수이다. 모든 정렬 알고리즘 함수는 올바른 정렬을 위해 임의 접근 반복자를 사용한다. 따라서 임의 접근이 가능한 컨테이너만이 사용할 수 있다. sort() #include // < 를 이용한 비교 (1) template void sort(RandomIt first, RandomIt last); // 비교 함수 (comp) 를 이용한 비교 (2) template void sort(RandomIt first, RandomIt last, Compare comp); first부터 last 전까지의 원소들을 오름차순으로 정렬한다. first와 last는 임의 접근 반복자여야 한다. 따라서 list의 경우 sort 함수로 정렬할..
[C++] STL - 변경 알고리즘 함수 (copy, swap, transform, next_permutation) 변경 알고리즘 함수는 컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 요소의 값만을 변경할 수 있는 함수이다. STL에서 제공하는 대표적인 변경 알고리즘 함수에는 copy(), swap(), transform()이 있다. copy() #include template OutputIt copy(InputIt first, InputIt last, OutputIt d_first); first부터 last 전까지의 모든 원소들을 d_first부터 시작하는 곳에 복사한다. swap(), swap_range() #include template void swap (T& a, T& b) swap의 경우 해당 변수에 있는 값들을 서로 바꿔주는 역할을 한다. #include template< class Forward..
[C++] STL - 읽기 알고리즘 함수 (find, for_each) STL의 목적은 일반적인 알고리즘에 대한 효율적인 구현을 제공하는 것이다. 따라서 STL은 이러한 알고리즘을 STL 알고리즘 함수나 STL 컨테이너의 멤버 함수를 사용하여 구현하고 있다. STL 알고리즘은 기능별로 다음과 같이 구분할 수 있다. 읽기 알고리즘 (algorithm 헤더 파일) 변경 알고리즘 (algorithm 헤더 파일) 정렬 알고리즘 (algorithm 헤더 파일) 수치 알고리즘 (numeric 헤더 파일) 이 글에서는 읽기 알고리즘 함수에 대해 알아보자. 읽기 알고리즘 함수는 컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 특정 데이터를 읽기만 하는 함수이다. STL에서 제공하는 대표적인 읽기 알고리즘 함수에는 find(), for_each()가 있다. find() #includ..
[C++] STL - pair, tuple pair은 두 객체를 하나의 객체로 취급할 수 있게 묶어주어 데이터 쌍 역할을 한다. #include 헤더 파일에 존재하는 STL이지만 algorithm, vector과 같은 헤더파일에서 이미 include 하고 있기 때문에 따로 utility를 include 하지 않아도 사용 가능하다. 변수 선언 값을 할당하는 방법은 다음 3가지 중 선택 pair p1; p1.first = 10; p1.second = 'c'; pair p2; p2 = make_pair(40, 30); pair p3; p3 = {1, "sample"}; pair 값 참조 pair에 저장된 데이터를 불러오려면 순서대로 .first와 .second를 사용한다. tuple은 pair의 확장 버전이라고 생각하면 된다. 2개 이상의 값을 하나로..
[C++] STL - 컨테이너 어댑터(container adapter) [stack, queue] stack 스택 컨테이너는 vector 클래스를 기반으로 한다. 스택의 메모리 구조는 LIFO(Last In First Out)를 따르는 자료구조이다. DFS(Depth First Search, 깊이 우선 탐색)나 특별한 알고리즘이 필요한 상황이 아니라 문제 상황을 구현하는 데 LIFO의 구조를 가지고 있다고 판단되는 문제를 풀 때 사용된다. #include stack 스택명; 스택의 멤버함수를 확인하면 다음과 같다. s.size() : s의 원소의 개수를 반환(메모리 용량이 아님) s.empty() : s가 비어있는지 확인, 비어있으면 true를 반환한다. s.top() : s의 제일 위에 위치한(제일 나중에 저장된) 원소를 반환 s.push(x) : s에 x값을 저장 s.pop() : s의 제일 위에..
[C++] STL - 연관 컨테이너(associate container) [set, multiset, map, multimap] 연관 컨테이너(associate container) 연관 컨테이너는 key와 value를 통해 관계있는 값을 묶어서 저장하는 컨테이너이다. 따라서 key와 value를 통해 요소에 빠른 접근은 가능하지만 연관 컨테이너는 자체적인 기준을 가지고 요소를 정렬하기 때문에 삽입되는 요소의 위치를 지정할 수 없다. 주로 균형 이진 트리(balanced binary search tree)나 해시 함수(hash function)을 사용해 구현된다. set & multiset set은 key만 가지고 있는 연관 컨테이너이다. 따라서 저장하는 값이 key가 되고 오름차순으로 정렬된 위치에 요소를 삽입하여 검색 속도가 매우 빠르기 때문에 데이터의 존재 유무를 파악하는데 유용하다. 다른 정렬 기준을 사용하고 싶다면 템플릿 ..
[C++] STL - 시퀀스 컨테이너(sequence container) [vector, deque, list] 시퀀스 컨테이너(sequence container) 특징 메모리 상에서 모든 요소가 직전 순서로 배치되어 순서가 존재해야 한다. 즉, 첫 번째 요소와 마지막 요소를 제외한 모든 요소는 앞뒤로 컨테이너의 요소가 존재해야 한다. 반복자가 이동할 때 요소의 순서가 변경되지 않음을 보장하기 위해 반복자는 최소 순방향 반복자를 사용해야 한다. 시퀀스 컨테이너는 직선 순서로 배치되어 명확한 순서가 존재하므로 특정 위치에 대한 참조가 가능해야 한다. vector 벡터는 동적 배열의 클래스 템플릿으로 가장 기본이 되는 컨테이너이다. 벡터는 데이터가 들어가고 나올 수 있는 입출구가 뒤쪽 하나이며 앞쪽은 막혀있는 형태이다. 따라서 데이터를 넣을 때도 뒤에서부터 쌓이고 데이터를 꺼낼 때는 맨 뒤에서부터 뺄 수 있다. 시퀀스..

티스토리툴바