케이스윔의 개발 블로그

STL의 여러 컨테이너를 사용해보면서 내부적으로 어떻게 구현이 되어있는지에 대한 고민을 해보지 않았던 것 같다. 그래서 vector를 사용해서 push_back()을 할 때에는 당연히 삽입이므로 시간복잡도가 O(1)일 거라 생각했다. 이번에 한 문제를 풀면서 O(N)이라는 걸 알게 됐다. STL에서 삽입, 삭제에 시간복잡도가 O(1)로 사용할 수 있는 컨테이너는 list다. list는 들어만 보고 vector나 queue를 쓰면 되니까 크게 필요성을 느끼지 못했었다. 그런데 시간복잡도에 대한 고려를 해보면서 시간제한이 있는 문제를 풀 때는 list를 써야된다는 것을 알았다. list 는 시퀀스 컨테이너이고, 노드 기반의 컨테이너이다. (vector와 deque는 배열 기반 컨테이너)따라서 list는 중간..