개발일지

문제설명 입출력 예제 개념 우선순위 큐의 정렬 순서를 직접 지정하면 풀 수 있는 문제다. 구조체를 이용하여 연산자를 오버로딩하여도 되고, 단순히 비교 함수를 인자로 추가해도 된다. 풀이 #include #include #include using namespace std; bool abs_operator(int a, int b) { return abs(a) == abs(b) ? a > b : abs(a) > abs(b); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq(abs_operator); cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.e..

문제설명 입출력 예제 개념 지난 게시글인 최대 힙 문제처럼 우선순위 큐를 이용하여 풀면 쉽게 해결할 수 있다. 즉, 우선순위 큐를 최소 힙으로 정렬하면 된다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq; cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.empty()) printf("0\n"); else { printf("%d\n", pq.top()); pq.pop(); } } else pq.push(n); } }

문제설명 입출력 예제 개념 주어진 문제는 우선순위 큐의 기본적인 연산을 이해하고 있는지 묻는 문제다. 따라서 우선순위 큐를 최대 힙으로 정렬한 후, 문제의 요구 사항에 맞게 입출력을 조절하면 풀 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; priority_queue pq; cin >> N; while (N--) { cin >> n; if (n == 0) { if (pq.empty()) printf("0\n"); else { printf("%d\n", pq.top()); pq.pop(); } } else pq.push(n); } } 특이 사항..

힙(Heap)개요　우리는 힙 자료구조에 대해 이전에 컨테이너 어댑터 포스팅에서 간략하게 알아본 적이 있다. 특정한 우선순위를 갖는 이 컨테이너에 대해 더욱 자세하게 알아보는 시간을 갖도록 하자. 　힙은 다음과 같은 시간 복잡도 특징을 갖고 있다.최대/최소 원소에 접근: O(1)원소 삽입, 삭제: O(logN) 　힙은 다음과 같은 특징이 있다.부모 노드와 자식 노드의 우선순위는 항상 유지우선순위가 높은 원소는 항상 루트 노드에 존재완전 이진 트리(Perfect Binary Tree)　힙은 원소 삽입 또는 삭제에 대해 O(logN)의 시간 복잡도를 만족해야 하기 때문에 일반적으로 완전 이진트리를 사용해야 한다. 여기서 완전 이진 트리(Complete Binary Tree, 포화 이진트리)는 레벨 순서대로 왼..

문제설명 입출력 예제 개념 2751번과 마찬가지로 우선순위 큐를 이용하면 쉽게 해결할 수 있다. 이전 문제와 다르게 비교자를 less를 이용하면 내림차순으로 정렬된다는 점을 유념하자. 풀이 #include #include int main() { std::priority_queue que; std::string str; std::cin >> str; 우선순위 큐를 선언하고, 숫자를 문자열로 받아준다. for (char c : str) { que.push(c - '0'); } while (!que.empty()) { std::cout > str; for (char c : str) { que.push(c - '0'); } while (!que.empty()) { std::cout

문제설명 입출력 예제 개념 우선순위 큐(priority_queue)를 이용해 비교자를 설정하면 쉽게 해결할 수 있는 문제다. 풀이 #include #include int main() { std::priority_queue que; int n; std::cin >> n; 우선순위 큐를 초기화하고, 문제에서 오름차순으로 정렬하라 하였으므로 비교자를 greater로 설정한다. for (int i = 0; i > num; que.push(num); } while (!que.empty()) { int num = que.top(); std::cout n; for (int i = 0; i > num; que..

컨테이너 어댑터(Container Adapter)개요　앞서 살펴본 컨테이너들은 완전 바닥부터 직접 만들었다. 하지만 이미 존재하는 컨테이너를 기반으로 새로운 컨테이너를 만드는 작업, 즉, 래핑(wrapping)하여 새로운 인터페이스를 만드는 것이 더욱 효율적일 때가 있다. 이것이 바로 컨테이너 어댑터다. C++ 표준 라이브러리에서 제공하는 대표적인 컨테이너 어댑터를 간략하게 설명하고 구현하는 시간을 가져보자.std::stack 　스택(stack)은 데이터의 처리와 저장을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하는 컨테이너다. 기능적인 측면에서 스택은 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 괄호를 검사하거나, 뒤로 가기 버튼, 컴파일러를 구현할 때 사용된..