C++ STL

[C++ STL] map 기본적인 사용법[C++ STL]에서 연관 컨테이너 중 하나인 map에 대해서 기본적인 사용법을 알아보도록 하겠습니다. map의 자료구조는 트리로 구성되어 있습니다. 정확히 말하면 레드 블랙 트리입니다. 레드 블랙 트리는 자가 균형 이진 탐색 트리로써 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하는 이진 탐색 트리입니다. 높이를 작게 유지하는 이유는 연산 과정에서 트리의 높이가 한쪽으로 치우치는 것을 막기 위함입니다. 이는 시간복잡도와 관련이 있습니다. 트리에 n개의 원소가 있을 때 O**(log n**)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다.*(문자열의 경우 예외 문자열의 길이를 고려해줘야 함) 1. 기본적인 형태 : mapmap의 기본적인 형태는 위..

본 글은 여러 PS 문제를 접하다 보면 우선순위 큐를 적극적으로 사용해야 되는 경우가 있는데 매번 구글링을 하게 되는 것 같아  우선순위 큐에 대한 기본적인 사용법뿐만 아니라 기본적인 자료형 외에 구조체나 클래스의 객체 타입을 우선순위 큐에 저장하려고 할 때 비교 함수의 재정의 및 연산자 오버 로딩을 통한 우선순위 설정(?) 하는 방법을 알아보려고 합니다.   1. Priority_queue 란? 기본적으로 C++에서 자주 쓰이는 vector와 같은 container adaptor의 한 종류이며 C++에서 int와 같은 기본자료형으로 우선순위 큐를 사용한다면 큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다 또한 우선순위 큐는  내부적으로 Heap이라는..