1. 맵에서 비교 연산자 재정의하기#include #include // std::pair의 비교 연산자를 재정의하여 첫 번째 요소를 기준으로 정렬struct PairCompare { bool operator()(const std::pair& a, const std::pair& b) const { return a.first , std::string, PairCompare> myMap; myMap[{1, 2}] = "One Two"; myMap[{3, 4}] = "Three Four"; myMap[{2, 1}] = "Two One"; for (const auto& entry : myMap) { std::cout PairCompare을 비교 연산자로 사용한 ..

Stack LIFO(Last In First Out) 속성을 가진 자료구조이다. 책 쌓기처럼 가장 마지막에 push된 데이터가 pop된다. front에서 push, pop 모두 일어나며 벡터와 비슷한 메서드를 사용한다. Queue FIFO(First In First Out) 속성을 가진 자료구조이다. 줄 서기처럼 먼저 push된 데이터가 pop된다. front에서 pop, back에서 push가 일어나며 벡터와 비슷한 메서드를 사용한다. Priority_queue priority_queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 우선순위 큐 자료구조이다. priority_queue로 정의한다. container는 디폴트로 vector을 사용한다. deque로 사용할 수 있다. co..

2 7 I 16 I -5643 D -1 D 1 D 1 I 123 D -1 9 I -45 I 653 D 1 I -642 I 45 I 97 D 1 D -1 I 333 answer : EMPTY 333 -45 이중 우선순위 큐는 우선순위를 최대와 최소로 두 개 가지고 처리하는 우선순위 큐이다. 우선순위 큐를 두 개 선언하는 방법과 맵을 쓰는 방법 멀티 셋을 쓰는 방법을 떠올렸다. 맵을 떠올린 이유는 입력하는 원소가 중복이 될 수 있어서 키를 원소로 하고 value를 해당 원소의 개수로 하려고 했는데 굳이 짜보진 않았다. 우선순위 큐와 멀티 셋 중 고민하다가 우선순위 큐 두 개를 쓰는 것보다 멀티 셋 하나로 처리하는 게 공간적으로 이득을 보는 것 같아서 멀티 셋으로 짰다. set 컨테이너 사용법과 포인터와 주소..

예제 1 3 1 3 2 6 answer : 16 예제 2 4 2 4 2 3 1 answer : 19 n개의 카드에 대해 어떤 두 카드의 숫자를 그 두 카드의 합으로 바꾸는 것을 m번 진행한 뒤 n개의 카드의 숫자 합이 최소가 되게 하는 문제이다. 먼저 그리디 하게 매 턴마다 가장 작은 숫자 두 개를 고르면 된다고 생각했다. 매 턴마다 그리디 하게 숫자를 고르는 것까지는 문제가 없어 보였고, 구현 부분은 우선순위 큐를 이용해 간단히 우선순위를 내림차순으로 하고, pop 두 번 후 두 숫자를 더한 값을 push 두 번 하는 식으로 구현했다. 여기까지는 쉬웠지만 주의할 점이 하나 있었다. n개의 카드가 최대 1,000개이고 15 * n번의 턴이 진행되며 각 카드의 숫자는 최대 1,000,000여서 int 자료..

힙 최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다. 완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다. 최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다. 힙 구현 힙 특성 유지하기(heapify) 배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다. heapify(A, i){ l ..