https://www.acmicpc.net/problem/11003 티어는 플레티넘 5인데, 우선순위 큐로 너무나도 간단히 풀리는 최강 날먹(?) 문제질문 게시판을 보니, 덱을 이용해서 O(n) 에 풀 수 있도록 최적화 하는 것이 이 문제의 의도같은데, 입출력값이 너무 많아서 O(N) 으로 딱 제한을 두기가 힘든 모양이다.. 그럼에도 불구하고 파이썬 시간 제한이 9초대도 통과되는 건 너무 봐준 것 아닌가 싶기도.. 우선순위 큐 풀이는 최소힙에 (원소값, 원소 인덱스) 튜플을 저장하고, 범위가 늘어날 때마다 현재 보고 있는 원소를 우선순위 큐에 넣은 뒤, 최소힙에서 최소값을 본다.만약 본 값이 현재 최소값을 찾는 범위에 있는 값이라면 출력하고, 아니라면 최소힙에서 빼는 과정을 반복한다. 결과적으로는 N번의..
우선순위 큐 우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다. 일반적인 큐와 마찬가지로 push(), pop() 두가지 기능을 제공하지만, 우선순위 큐는 데이터를 저장할 때 단순히 데이터의 값 뿐만 아니라 데이터의 우선순위를 같이 저장하는 점이 다르다. 그래서 우선순위 큐에는 push(x, p) 와 같은 형태로 데이터를 저장한다. x 는 저장하는 데이터, p 는 저장하는 데이터의 우선순위이다. 그리고 pop을 할 때는 우선순위가 높은 데이터부터 나온다. 우선순위 큐의 구현 우선순위 큐의 개념은 간단하다. 그런데 우선순위 큐의 구현은 간단하지 않다. 만약 일반적인 큐를 구현할 때처럼 연결 리스트를 사용한다면 어떨까? 데이터를 pop 할 때, 우선순위가 높은 순부터 뽑아야 하므로 아래 2가지 방법중..
문제 소개 https://www.acmicpc.net/problem/20936 20936번: 우선순위 계산기 국렬이는 두 번씩이나 계산기 문제를 내놓고 또 계산기 문제를 냈다. 이대로라면 죽을 때까지 계산기를 우려먹을 생각이고, 당신은 귀찮지만 상금을 얻기 위해서 주어진 수식을 규칙에 맞게 계 www.acmicpc.net 2021 WINTER 신촌 연합 대학생 프로그래밍 대회(SAUPC)의 A번으로 나왔던 문제이다. 당시에는 너무 복잡해서 그냥 넘겨버렸는데, 아니나 다를까 플레티넘 문제였다ㅋㅋ 이번 SAUPC에서 구현문제를 담당하게 되어서 연습을 위해 풀어보았다. 전에 풀었던 뒤집힌 계산기와 비슷한 유형이지만, 좀 더 복잡하다. 알고리즘을 어떤 걸 써야할지 감이 잡힐 듯 말듯 해서, 결국 알고리즘 분류를..
