백준일지14 [C++] STL 자료구조: Set, Map set, map은 자가 균형 이진 탐색 트리(BBST, self-balancing binary search tree)로 구현되어있는 자료구조이다. BBST의 일종인 레드-블랙 트리(Red-black tree)로 구현되어 있다. 이는 원소들이 정렬되어 있다는 이진 탐색 트리의 성질과 트리의 높이를 최대한 작게 유지한다는 균형 이진 트리의 성질을 모두 지닌다. (만약 set, map을 직접 구현해야 한다면 보통 red-black tree 대신 treap, skip-list, splay tree 등을 이용한다.) 대소관계가 정의된 자료형의 삽입, 삭제, 검색을 O(logn)에 처리할 수 있다. 단, S[i]나 S.begin() + i와 같은 연산을 지원하지 않아서 i번째 원소에 빠르게 접근할 수 없다.set.. 2024. 5. 7. [C++] STL 자료구조: List list는 양방향 연결 리스트(doubly-linked list)로 구현되어있는 자료구조로 임의 위치의 삽입과 삭제를 O(1)에 지원한다.- 이전 노드와 다음 노드에 대한 링크를 각 노드마다 저장하고 있다. list의 각 노드들은 메모리 상에서 떨어진 위치에 존재하며 한 노드를 삽입하거나 삭제해도 다른 노드들의 위치에는 영향이 없다. 삽입, 삭제 시 변화하는 값은 오직 이전 노드와 다음 노드를 가리키는 링크들로, 한 노드를 삽입 또는 삭제하는 경우 자신과 그 주변 노드들의 링크만 수정하면 된다. 이를 이용해 list는 원소의 삽입, 삭제가 이루어진다.노드들이 메모리 상에 인접해있지 않다는 성질때문에 list는 i번째 원소에 바로 접근하는 연산을 지원하지 않는다. 원소의 삽입, 삭제는 해당 원소의 위치를.. 2024. 5. 2. [C++] STL 자료구조: Priority queue 이전에 배웠던 vector, stack, queue, deque가 연속된 위치에 일렬로 데이터를 세워둔 것과 달리 priority_queue는 이진 트리 구조를 갖는 heap을 이용해서 데이터를 저장한다. 내부 구조는 달라도 queue와 비슷하게 pop, push 연산을 지원한다.priority_queue는 주로 1)원소를 추가하는 연산이 있으면서 2)우선순위 큐 내의 원소 중 최댓값(또는 최솟값)을 빠르게 구해야 하고, 3)해당 원소를 삭제하는 연산이 있는 경우 주로 사용한다. 이때 최댓값만을 구할 수 있으며 이외의 값들은 정렬되어있지 않고, 접근할 수도 없다는 점을 주의해야 한다.우선순위 큐는 PQ.top()에 최댓값(또는 최솟값) 원소가 오도록 유지하면서 새로운 원소의 삽입과 최댓값(또는 최솟값).. 2024. 4. 29. [C++] STL 자료구조: Deque deque는 시작 위치와 마지막 위치의 삽입, 삭제를 O(1)에 처리할 수 있는 stack과 queue를 합쳐놓은 느낌의 자료구조이다. 또한 std::deque는 [] 연산자.. 2024. 4. 7. 이전 1 2 3 4 다음
