https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 우선순위 큐를 2개 이용하는 문제로 왼쪽은 최대힙, 오른쪽은 최소힙으로 구현하여 중앙값을 구했다. 양쪽 힙의 len이 같을때는 왼쪽에 heappush를 하고 나머지는 오른쪽에 넣어준다. 이때 왼쪽의 최댓값이 오른쪽의 최솟값보다 크면 둘의 위치를 바꿔준다. 위의 과정을 반복하므로써 중앙값을 우선순위 큐를 이용하여 구할 수 있다. 손으로 예시를 들어서 직접 써보면 이해하기..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 사람마다 느끼는 난이도는 다르겠지만, 나한텐 개어려웠다. 처음에 min_heap과 max_heap을 다 만들어놓고 한쪽에서 삭제된걸 어떻게 삭제할까 하다가 그냥 remove()써서 삭제했더니 당연히 시간초과... 이 remove함수를 대체하여 다른것을 생각해내는데 시간이 매우 오래결렸다. (2틀동안 이것만 붙잡고 있었음) max_heap을 구현하는데 (-num,num) 의 튜플형태로 구현하여 ..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 브루트포스 알고리즘, 즉 완전탐색을 이용하여 풀었다. 단순한 풀이긴 하지만 이것말고 생각나는 방법이 없었다. 1부터 1000000까지 만들수 있는 숫자들을 모두 구하고 그 숫자들과 이동할 채널의 차를 구해서 최솟값을 구하였다. 그리고 직접 (+, -) 버튼을 이용하여 이동하는 경우도 포함하여 마지막에 min함수로 비교해주었다. 완전탐색이라는 것만 안다면 별로 어렵지 않은 문제인거 ..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이 문제는 파이썬의 우선순위 큐 자료구조가 무엇인지 안다면 어렵지 않게 해결할 수 있다. 파이썬에서는 우선순위 큐 자료구를 heapq모듈을 이용하여 사용할 수 있다. 스택: 가장 나중에 삽입된 데이터가 가장 먼저 나옴 큐: 가장 먼저 삽입된 데이터가 가장 먼저 나옴 우선순위 큐: 우선순위가 가장 높은 데이터가 가장 먼저 나옴 힙: 완전 이진트리의 일종으로 항상 루트 노드를 제..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 특정 숫자보다 큰 수를 구하는 이번문제는 처음에 단순 while문으로 구현하였지만 역시나 시간초과가 떴다. 다시 생각하다가 두 수의 크기를 비교하는 과정에서 큐/스택을 잘 활용하는 방안이 생각났다. (백준 11003번 에서 큐/스택을 이용하여 최솟값을 찾아봤었다.) 오큰수가 없는 경우에는 -1을 출력해야하므로 답을 제출할 리스트에 -1을 미리 세팅해두었다. 예를 들어 오큰수를 구하고 싶은 리스트 a = [7..

https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제를 처음 보고 떠올린 것은 최솟값을 구해야 하는 구간에서 정렬하거나 min()함수를 이용하는 방법인데 시간초과 날것이 뻔했다 (파이썬에서 sort()의 시간복잡도는 O(NlogN)이다) 그래서 배열을 훑으면서 바로바로 최솟값을 찾아내야겠다고 생각했다. 슬라이딩 윈도우와 큐, 스택을 활용하여 최솟값을 구하였다. 2 1 5 4 2 6 위의 숫자들에서 최솟값을 구해야..