개발일지

문제설명 입출력 예제 개념 우선순위 큐의 정렬 순서를 직접 지정하면 풀 수 있는 문제다. 구조체를 이용하여 연산자를 오버로딩하여도 되고, 단순히 비교 함수를 인자로 추가해도 된다. 풀이 #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); } }

문제설명 입출력 예제 개념 문서의 개수와 중요도가 주어졌을 때, 큐에서 M번째에 해당하는 문서가 몇 번째로 출력되는지 묻는 문제다. 프린터 대기열은 큐 자료 구조를 사용한다는 점과, 문서의 중요도가 필요하다는 점에서 문서의 이름과 중요도를 자료형 pair로 받아 처리해야 한다는 점을 유의하자. 풀이 #include #include #include using namespace std; int main() { int T, N, M, n; cin >> T; 테스트 케이스의 수 T, 문서의 개수 N, 출력 순서가 궁금한 정수 M, 중요도 n을 초기화한다. while (T--) { int index = 0; cin >> N >> M; queue q; pair ans; for (int i = 0; i < N; ++..

문제설명 입출력 예제 개념 예제 (7,3) 요세푸스 순열이 생성되는 과정은 다음과 같다. 따라서 K번 만큼 수를 뒤로 보낸 후 수를 뽑으면 요세푸스 순열이 생성된다. 즉, 선입선출의 구조를 갖고 있으므로 큐 자료구조를 활용하면 쉽게 풀 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; queue q; for (int i = 1; i

문제설명 입출력 예제 개념 큐의 기본적인 구조를 잘 이해하고 있는지 묻는 문제다. 기존의 스택(10828) 문제처럼 입력받은 문자열에 맞게 큐의 동작을 수행하게끔 작성하면 해결할 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; cin >> N; queue q; while (N--) { string str; cin >> str; if (str == "push") { cin >> n; q.push(n); } else if (str == "front") { if (q.empty()) cout

문제설명 입출력 예제 개념 1부터 N까지 정렬되어 있는 시퀀스에서 맨 앞에 수를 뽑고, 앞 뒤를 바꿔갔을 때, 마지막에 남는 카드가 무엇일지 구하는 문제다. 먼저 들어간 요소가 뽑힌다는 관점에서 queue를 적절히 활용하면 해결할 수 있는 문제다. 풀이 #include #include using namespace std; int main() { int N, n; cin >> N; queue q; for (int i = 1; i

문제설명 입출력 예제 개념 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, 후입선출) 구조를 사용하는 컨테이너다. 기능적인 측면에서 스택은 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 괄호를 검사하거나, 뒤로 가기 버튼, 컴파일러를 구현할 때 사용된..