케이스윔의 개발 블로그

와 방금 알고리즘문제를 풀다가 모르는 부분이 있어서 아는 선배한테 물어봤는데 너무 신기한 알고리즘아닌 알고리즘을 들었다. 그 문제를 풀기위해 필요한게 c++에서는 해시맵이라고 친절히 알려주셔서 오늘은 해시맵 관련 컨테이너들을 공부하도록 하겠다! (이 글을 써둔게 2018.5.17 였는데 이어서 추가 및 수정한다.) 해시맵은 연관 컨테이너 중 하나이다. 예를 들어 vector나 list와 같은 컨테이너는 순서에 따라 값을 저장하지만 연관 컨테이너는 어떠한 key와 짝을 이루어서 값을 저장한다. 따라서 값을 넣고, 찾을 때에는 key가 필요하다! 대량의 자료를 저장하고 빠르게 검색하기 위해 사용된다고 한다. hash table을 만들어두면 O(1)로 검색을 할 수 있듯이 비슷한 것같다.(아니 그 개념을 적용..

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