공부/C, C++

개요 특징 vector와 deque와 같은 Sequence Container의 한 종류이다. 이중 연결 리스트라고 잘 알려져 있는 자료구조를 구현해놓은 컨테이너이다. 다른 Sequence Contianer와 달리 멤버 함수로 sort()와 merge() 그리고 splice()가 있다. 이중 연결 리스트 자료구조의 특성상 노드 기반 컨테이너이므로 임의 접근이 불가능하다. (a[3], a.at(3)) 중간에 원소를 삽입(insert), 제거(erase)하는 작업은 O(1)의 시간 복잡도를 가진다. 값의 비교로 원소를 제거하는 remove()와 remove_if()를 제공한다. 자세히 알아보기 선수 항목 #include using namespace std; 선언 std::list 이름; (using names..

lower_bound 개요 특징 이진 탐색(binary_search)의 근간이 된다. algorithm 헤더에 포함되어 있다. 설명 이진 탐색 기반의 탐색이므로, 배열 또는 리스트가 오름차순 정렬되어 있어야 한다. 찾으려고 하는 key 값이 없으면, key 값 이상인 값들 중, 가장 작은 값을 찾는다. 그리고 그 위치를 반환한다. (값 반환 X) 값을 얻기 위해서는 * 연산자를 사용한다. (예: *lower_bound(v.begin(), v.end());) 같은 수가 여러 개 존재하여도 상관 없다. 자세히 알아보기 선수 항목 #include using namespace std; 사용 일반적인 사용 : lower_bound(Iterator first, iterator last, 찾으려는 value); 또 ..

문제 인식 C++ STL의 vector는 push_back()을 통해 배열의 원소를 계속 늘릴 수 있다. 그러나, vector가 처음 선언될 때 예약되어 있던 '용량'을 초과해버리면, 그보다 더 '큰' (2배 정도) 용량의 메모리를 할당한 후 기존의 원소를 모두 복사하고, 기존의 메모리는 해제하는 작업을 거친다. 즉, 이 작업에는 할당 -> 복사 -> 해제의 비용이 들어간다. 이 작업의 시간 복잡도는 O(1)로 알려져있으나 이는 엄연히 Amotized Analysis 즉, 분할 상환 분석법을 통해 구해진 시간 복잡도일 뿐이며, 최악의 경우 O(N)까지 시간 복잡도가 커질 수 있다. 한 마디로, 재할당이 많이 일어나면 일어날 수록 성능이 매우 떨어진다는 의미이다. 실제로 BOJ 문제에서 이로 인해 시간 초..