큐는 FIFO 성질을 가진 자료구조다. 즉 먼저 들어간 데이터가 먼저 나오게 된다. 스택 2개를 활용해서 큐를 구현할 수 있다. 스택 하나는 push 용도, 나머지 하나는 pop할 때 이용된다. 만일 pop 명령이 들어온다면 push 때 담긴 스택을 위에서부터 빼서 스택 2번에 넣을 수 있다. 그리고 스택 2에서 위에서부터 pop하면 큐와 똑같이 동작시킬 수 있다

최소 힙을 구현해서 새로운 데이터가 들어가는 시간복잡도를 lgN으로 처리해야만 한다 문제: https://www.acmicpc.net/problem/1715 깃허브주소: https://github.com/surinoel/boj/blob/master/1715.cpp

우선순위 큐는 '우선순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용된다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 최대힙은 부모가 자식보다 값이 큰 이진 트리를 의미한다 1. 우선순위 큐의 삽입 1) 배열 맨 끝에 삽입한다 2) 부모와 비교해서 swap을 한다. 가능하다면 루트까지 진행한다 3) 상향식 구조 2. 우선순위 큐의 삭제 1) 0번 인덱스를 추출한다 2) 맨 마지막 원소를 0번으로 넣는다 3) 하향식 구조로 자식들을 비교하면서 0번 인덱스의 기존 위치를 찾는다 #include #define SIZE 1000 typedef struct { int heap[SIZE]; int count; } Pri..

기수 정렬은 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다. 데이터가 총 N개가 있고, 데이터 중 최대 자릿수가 D라고 할 때, 시간복잡도 O(DN)을 가지게 된다. 계수 정렬과 달리 자릿수가 큰 데이터에 대해서도 정렬이 가능하다. 하지만 조금은 느리다는 특징은 있다 단점은 계수 정렬과 마찬가지로 -값이 있을 때는 인덱스를 옮기는 수고를 해야한다

https://noel-embedded.tistory.com/495 기존 priority_queue STL 세번째 인자인 class Compare = std::less 함수를 만들기 위해서 cmp 클래스를 만들고, 그 안에 연산자를 만들어서 오버로딩을 했다. 이는 다양한 연산자 오버로딩을 구분할 수 있어서 좋다 하지만 하나의 연산자만 구현한다면 클래스 없이