본문 바로가기

728x90
반응형

STL

[C++] vector container 정리 및 기본 사용법과 응용 [목차] 1. vector란? 2. vector의 장단점 3. vector 사용 준비 4. vector 생성자 5. vector 멤버 함수 6. 2차원 vector 7. vector의 응용 그동안 PS를 하면서 vector가 반드시 필요한 문제를 접하지 못해서 그런지, 항상 그동안 익숙했던 배열을 이용해 왔다. 하지만 vector를 이용하면 훨씬 편리하다는 주변의 조언에 따라 이제라도 최대한 vector를 이용하려고 한다. (사실 처음에 vector가 indexing이 안 되는 줄 알고 사용을 안 했는데, 배열과 똑같이 indexing이 되니 배열을 쓸 이유가 없는 것 같긴 하다....) 1. vector란? C++ STL에는 크게 두 개의 container가 있다. 배열처럼 원소들을 순서대로 보관하는 ..
[C++] lower_bound & upper_bound STL에서 제공하는 lower_bound와 upper_bound에 대해서 알아보자. LIS(Longest Increasing Subsequence)를 공부하다가 알게 된 개념이다. 필자 개인적으로는 STL에 대해서 잘 몰랐는데, 처음으로 STL이 매우 유용하다는 것을 깨닫게 해준 함수이다. (이를 계기로 계속 STL을 이용하려고 노력중이다) 우선 lower_bound와 upper_bound는 이진 탐색(Binary Search)을 기반으로 탐색하는 함수이다. 따라서 배열이나 리스트, 벡터 등이 기본적으로 정렬이 되어있어야 하고, 시간복잡도는 O(logn)이다. 기본적으로 이진 탐색은 찾고자 하는 원소가 있는지, 있다면 어디에 위치해 있는지를 찾는다면, lower_bound와 upper_bound는 이진 ..
[C++] STL - sort STL에서 제공하는 sort 함수를 알아보자. 우선 sort 함수를 이용하기 위해서는 헤더 파일을 include 해주어야 한다. sort함수는 퀵정렬을 기반으로 하므로 O(nlogn)의 평균 시간 복잡도를 가진다. sort 함수의 형태는 아래와 같다. 1 2 3 4 5 template void sort(T start, T end); //default 오름차순 template void sort(T start, T end, Compare comp); //compare 함수 정의 가능 위처럼 정렬 기준이 되는 함수 (comp) 를 추가하지 않는다면 기본적으로 '오름차순'으로 정렬해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; ..
[C++] STL - 스택(Stack) & 큐(Queue) 우선 스택(Stack)과 큐(Queue)의 기본 원리는 생략한다. STL에서는 스택과 큐를 템플릿 클래스로 제공하고 있다. [Stack] stack은 기본적으로 LIFO구조이며, STL에서는 default로 deque(덱) 컨테이너를 사용한다. 즉, 실제로 내부적으로는 deque 구조로 구현되어 있지만, stack과 같이 이용할 수 있도록 제공하는 것이다. stack container을 이용하기 위해서는 헤더를 include 시켜주어야 한다. 1. stack container 선언(생성자)은 다음과 같다. stack< [data type] > 이름 만약 내부 컨테이너 구조를 바꾸고 싶다면 다음과 같이 선언하면 된다. stack< [data type] , [container type] > 이름 1 2 3 ..