연관 컨테이너(associative container)란?이전에 배운 시퀀스 컨테이너가 단순하게 순차적으로 자료를 저장하는 구조라면, 연관 컨테이너는 각 원소가 키(key) - 값(value)의 구조를 가지는 컨테이너다. 특정한 키를 넣으면 이에 대응되는 값을 돌려준다.연관 컨테이너는 대표적으로 다음과 같은 작업을 수행한다.특정 키가 연관 컨테이너에 존재하는가?특정 키에 대응되는 값은 무엇인가?첫 번째 작업에는 셋(set)과 멀티셋(multiset), 두 번째 작업에는 맵(map)과 멀티맵(multimap)을 사용한다.맵의 경우 셋보다 사용하는 메모리가 많으므로 단순히 키의 존재 유무만 궁금하다면 셋을 사용하는 것이 좋다.나머지는 차차 알아보도록 하고, 먼저 셋부터 알아보자.개요셋은 원소들을 저장하지만 ..

파이썬으로 알고리즘 문제를 풀기 시작해서 얼마 안 돼 C++로 전환했는데, 이상하게 시간 초과가 뜨는 문제가 많이 보였다. 간단한 문제임에도 계속 시간 초과가 나서 하루 종일 해결을 못 했는데, 알고보니 C++의 cin, cout이 문제였다. cin과 cout은 scanf와 printf보다 현저히 느리다고 한다. 이런 경우에는 다음 코드를 사용하면 cin과 cout의 속도를 개선할 수 있다고 한다.// include와 네임스페이스 using 지시문 생략ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);또한 endl보다 \n를 사용하는 것이 더 빠르다. (백준 1874번 문제를 이거 때문에 시간 초과 떠서 하루 종일 못 풀었었다;;) 다만 주의할 점이 있..

개요벡터와 비슷하지만 양방향으로 원소를 삽입 / 제거할 수 있는 컨테이너시간 복잡도임의 위치 원소 접근: O(1)맨 앞/뒤에 원소 추가 및 제거: O(1)중간에 원소 삽입 및 제거: O(n)벡터보다 빠르게 동작함주요 기능 및 특징벡터보다 빠른 이유 (덱의 구조)덱은 벡터와 다르게 원소들이 실제로 메모리 상에서 연속적으로 존재하지 않는다. 이 때문에 원소들이 어디에 저장되어 있는 지에 대한 정보를 보관하기 위해 추가적인 메모리를 더 필요로 한다. (즉, 덱은 속도를 위해 메모리를 희생함)덱의 원소들은 일정 크기로 잘려서 각각의 블록에 저장된다. 그리고 그 블록들의 시작 주소를 가리키는 포인터들의 벡터가 존재한다.  크기를 늘리는 경우에서도 차이를 보이는데, 벡터의 경우 벡터가 가득 찬 상태에서 새로운 원소..

개요양방향 연결 구조를 가진 자료형양방향 연결 리스트와 같은 구조 벡터와 달리 임의의 위치에 있는 원소에 접근할 수 없음리스트는 시작 원소와 마지막 원소의 위치만 기억하고 있기 때문시작 또는 마지막 위치에서 반복자가 한 칸씩 움직이는 방식으로만 접근할 수 있다. 양방향 연결 리스트와 같이 각각의 원소들이 링크로 이어져 있기 때문에 실제 메모리 상에서 연속적으로 존재하지 않을 수 있다.시간 복잡도중간에 원소 삽입 / 제거:O(1)연결 관계만 바꿔주면 되기 때문에 매우 빠름주요 기능 및 특징반복자리스트의 반복자의 타입은 BidirectionalIterator 타입이다.이 반복자는 양방향으로 이동할 수 있되, 한 칸씩만 이동 가능하다.++ / -- 연산리스트의 반복자에 ++, --를 사용해 반복자를 왼쪽 / ..

개요컨테이너에서 원소에 접근할 수 있게 하는 포인터같은 객체벡터에서 []을 사용해 원소에 접근할 수 있지만, 반복자를 사용해 접근하는 것이 올바른 방법이다.STL에 있는 컨테이너들에는 iterator 멤버 타입으로 정의되어 있다. 이후 내용은 벡터를 통해 반복자를 설명한다.begin()과 end()begin(): 컨테이너의 첫 번째 원소를 가리키는 반복자를 리턴end(): 컨테이너의 마지막 원소 한 칸 뒤를 가리키는 반복자를 리턴빈 벡터를 begin() == end()로 표현하기 때문에 한 칸 뒤를 가리키게 함// 반복자 사용 예시#include #include int main() { std::vector vec; vec.push_back(10); vec.push_back(20); ..

개요가변 길이 배열이라고 생각하면 된다.벡터 내부의 원소들이 실제로 메모리에서 연속적으로 저장되어 있다.시간 복잡도임의 위치 원소 접근 (at, []): O(1)맨 뒤에 원소 삽입 및 제거 (push_back, pop_back): O(1)엄밀하게 말하자면 amortized O(1) (amortized는 분할 상환이라는 뜻)보통 벡터는 현재 가지고 있는 원소의 개수보다 더 많은 공간을 미리 할당해 놓음 (부족할 때마다 2배씩 늘리는 방식)이런 상태에서 원소를 삽입하면 O(1)로 작동하지만, 만약 벡터가 꽉 차서 벡터의 공간을 늘려야 하는 경우 크기가 두 배인 새로운 벡터를 만들고 기존 벡터에 있는 모든 값들을 복사하는 작업을 하게 되므로 O(n)의 시간 복잡도가 소요됨다만, 이것을 평균적으로 보았을 때는 ..

각각의 주제에 대해서는 다른 글에서 자세히 설명하는 것으로 하고, 간단한 개념과 종류만 가볍게 살펴 보자. C++의 STL은 보통 세 개의 라이브러리를 의미한다.임의 타입의 객체를 보관할 수 있는 컨테이너(container)컨테이너에 보관된 원소에 접근할 수 있는 반복자(iterator)반복자들을 가지고 일련의 작업을 수행할 수 있는 알고리즘(algorithm)컨테이너 (Container)C++ STL 컨테이너는 크게 두 가지로 구분할 수 있다.배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(sequence container)키와 대응되는 값을 찾아주는 연관 컨테이너(associative container)C++ STL 컨테이너의 종류는 다음과 같다벡터 (std::vector)리스트 (std::li..