C++
Knapsack Problem
- DP 와 Knapsack Problem : 배낭 문제는, 어떤 한 사람이 갖고 있는 배낭이 있고, 그 배낭에 담을 수 있는 최대 용량이 주어지며, 이 최대 용량에 한해서, 여러개의 물건들을 집어넣고자 할때, 최대한의 가치를 뽑아내는 방법을 찾는 문제이다. 각 물건들은 무게와 값어치가 명시되어 있고 이들 중에서 배낭에 넣을 수 있으면서, 최대의 값어치를 뽑아내는 경우의 수를 찾아내면 되는 문제이다. 배낭 문제는 다시 말하면 '여러 물건이 있을때, 특정한 조건을 만족하는 조합을 구하는 문제' 라고 볼 수 있다. 배낭 문제는 두가지 유형으로 나뉜다. 물건(짐) 을 쪼갤 수 있는 경우와 물건을 쪼갤 수 없는 경우의 두 유형으로 나뉘는데, 전자의 경우 '분할가능 배낭문제' (Fractional Knapsack..
C++ STL 정리 - 정렬
C++ 의 알고리즘 라이브러리에서 제공되는 정렬은 3가지가 있다 1. sort() : 퀵소트를 기반으로하는 일반적인 정렬 방식이다. sort() 함수 사용시 주의할 점은 RandomAccessIterator 타입만 사용이 가능하다 STL 의 컨테이너 중 Vector, Deque 만 사용 가능하다. 다른 타입의 컨테이너를 사용하면 오류발생. - 기본연습문제 1. 수 정렬하기 2 www.acmicpc.net/problem/2751 (예시 코드) #include #define endl "\n" using namespace std; int n; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; vector vec(n, 0); for (int i ..
C++ STL 정리 - Stack
# Definition : Stack 은 다음과 같이 정의되어 있다 template class stack; cs Stack 은 LIFO(Last In First Out) 의 형태를 갖는 자료구조를 의미한다. 위 정의에서 T 는 타입, Container 는 Sequence Container 중 하나가 들어가야 한다 기본 컨테이너 타입은 std::deque 이다. 여기서 stack class 는 이 자체로 컨테이너가 아니라 container adapter 이다. # Header #include cs # Initialization - 초기화 stack s; // int type 의 빈 스택 생성 stack s2({1, 2, 3}); // 1,2,3 으로 초기화한 스택 생성 stack s3; // 컨테이너를 v..
C++ STL 정리 - Map
# Definition : map 컨테이너는 연관 컨테이너의 한 종류로, 아래와 같이 정의되어 있다 template class map; Colored by Color Scripter cs map 컨테이너는 key-value 형식의 데이터를 가지며, 정렬의 기준이 되는 함수는 Compare 이며, 정렬의 기준 값은 value 가 아니라 Key 이다. map 컨테이너도 set 과 마찬가지로 red-black tree 를 기반으로 하고 있다. # Header #include cs # Iterator set 컨테이너와 마찬가지로 8가지가 존재한다 begin(), cbegin(), end(), cend(), rbegin(), crbegin(), rend(), crend() #include #include #inc..
C++ STL 정리 - Set
# Definition : set 컨테이너는 연관 컨테이너의 한 종류로, 아래 같은 형태로 정의되어 있다 template class set; cs 기본적으로 set 은 중복을 허용하지 않으며, 기본 정렬 방식은 std::less 이다. set 은 red-black trees 를 기반으로 하기 때문에, 탐색, 삽입, 삭제에 대한 연산 시간복잡도가 O(logN) 이다. # Header #include cs # Iterator begin, cbegin, end, cend, rbegin, crbegin, rend, crend 8종류가 있다. #include #include using namespace std; int main() { set s = {3,1,4,5,7,1,6,3}; // s = {1,3,4,5,6..
C++ STL 정리 - Vector
# Definition template class vector; cs 벡터는 순차 컨테이너의 한 종류로, 기본적으로 동적으로 메모리가 할당된다. 정의에서 Allocator 란 컨테이너의 메모리를 관리하는 할당자 이다. (참고 : openmynotepad.tistory.com/57) # Header #include cs # 초기화 // 1. 기본 생성 (할당된 값도 없고 크기도 지정하지 않은 상태) vector vec; // 2 - 1. 크기를 지정해준 일차원 벡터 초기화 vector vec(4); /* 벡터의 크기가 4 가 되고, 각 원소의 값이 0임 (단, 전역 변수 선언시에만) vec = {0, 0, 0, 0} */ // 2 - 2. fill 로 채운 일차원 벡터 초기화 vector vec(4); f..
C++ STL 정리 - 개요
간단하게 C++ STL 의 종류와 특성에 대해서 훑어보는 포스팅이다. STL 은 Standard Template Library 의 약자로 C++ 언어를 위한 4가지 구성요소를 제공하는 라이브러리다. 4가지 구성요소는 Algorithm, Container, Iterator, Functors가 해당한다. * Algorithm Algorithm 은 Algorithm 이라는 헤더 파일에 정의되어 있으며, Container 를 다루기 위한 여러 수단을 제공한다. 예를 들면, Container 를 정렬 하기 위해 쓰는 sort() 함수나, 이진 탐색을 위해서 쓰이는 binary_search() 함수나, Container 내부의 값을 찾는 find() 함수 등 다양하게 존재한다 자세한 함수 종류는 Reference ..