Whatever floats your boat

알고리즘 문제를 풀다보면 priority_queue에 int형이 아닌 pair를 이용하고 struct를 이용할 때가 있어서 내가 원하는 순서대로 priority_queue를 출력하려면 비교연산자를 재정의 해주어야한다. 오늘은 어떻게 priority_queue의 비교연산자를 구현하는지 알아보도록 하자. c++에서 sort 함수를 사용할 때, 사용자가 원하는 순서대로 정렬하고 싶으면 cmp 함수를 따로 만들어서 사용하였다. #include #include bool cmp(int a, int b) { return a < b; } int main() { vector v; v.push_back(1); v.push_back(3); v.push_back(2); sort(v.begin(),v.end(),cmp); } ..

알고리즘 문제를 풀다보면 정렬을 해야할 때가 많으며 대부분 c++ 라이브러리를 사용하여 정렬을 하는 경우가 많다. 이번엔 sort함수를 간단하게 알아보고 정렬하기 위해 sort의 세번째 인자로 전달해 주는 함수 사용법을 알아보도록 하겠다. sort() 란 먼저 sort()를 사용하기 위해 algorithm 헤더파일을 include 해야한다. sort 함수는 내부적으로 IntroSort라는 정렬 방법으로 구현되어있다. 이 방법은 QuickSort와 HeapSort와 InsertionSort를 합쳐놓은 방식으로 평균 nlogn, 최악의 경우 n^2의 시간 복잡도를 가지는 QuickSort와는 달리, 최악의 경우에도 nlogn을 복잡도를 보장한다. https://en.wikipedia.org/wiki/Intr..