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 위의 숫자들에서 최솟값을 구해야..

https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”www.acmicpc.net시간초과 때문에 고생을 많이 한 문제인데 푼 방법을 보면 너무 일차원적이라서 허무했다.하지만 다시한번 생각해보면 일차원적인 방법이 더 빠르다는것을 한번에 알 수 있다.(처음 방법은 쓸데없는 과정이 있음)슬라이딩 윈도우를 이용한 풀이법으로 슬라이딩 윈도우는 일정 간격을  일정하게 움직여가며 탐색하는 방법이다. 예시로 아래 그림과 같이 3칸의 범위를 일정하게 움직인다처음에는 움직일 ..