C++ STL2 [C++ STL] map 사용법 [C++ STL] map 기본적인 사용법 [C++ STL]에서 연관 컨테이너 중 하나인 map에 대해서 기본적인 사용법을 알아보도록 하겠습니다. map의 자료구조는 트리로 구성되어 있습니다. 정확히 말하면 레드 블랙 트리입니다. 레드 블랙 트리는 자가 균형 이진 탐색 트리로써 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하는 이진 탐색 트리입니다. 높이를 작게 유지하는 이유는 연산 과정에서 트리의 높이가 한쪽으로 치우치는 것을 막기 위함입니다. 이는 시간복잡도와 관련이 있습니다. 트리에 n개의 원소가 있을 때 O(log n)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다. *(문자열의 경우는 예외 문자열의 길이를 고려해줘야 함) 1. 기본적인 형태 : map map의 기본적인 형태는 위.. 2020. 7. 27. [C++ STL] Priority_queue 사용법 본 글은 여러 PS 문제를 접하다 보면 우선순위 큐를 적극적으로 사용해야 되는 경우가 있는데 매번 구글링을 하게 되는 것 같아 우선순위 큐에 대한 기본적인 사용법뿐만 아니라 기본적인 자료형 외에 구조체나 클래스의 객체 타입을 우선순위 큐에 저장하려고 할 때 비교 함수의 재정의 및 연산자 오버 로딩을 통한 우선순위 설정(?) 하는 방법을 알아보려고 합니다. 1. Priority_queue 란? 기본적으로 C++에서 자주 쓰이는 vector와 같은 container adaptor의 한 종류이며 C++에서 int와 같은 기본자료형으로 우선순위 큐를 사용한다면 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다 또한 우선순위 큐는 내부적으로 Heap이라는 자료구.. 2020. 6. 5. 이전 1 다음
