algorithm

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칸의 범위를 일정하게 움직이는 방법이다. 1 ..

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 투 포인터를 사용하는 문제로 백준 1940번과 상당히 유사한 문제이다. 글쓴이 같은 경우는 투 포인터를 사용하기 위해 수들을 정렬해주고 더해서 나와야하는 수를 pop하여 저장했다가 반복이 끝나면 insert로 다시 추가하는 방식을 사용했다. 투 포인터에 대한것은 1940번에서 했기 때문에 생략한다. 코드는 다음과 같다. import sys input = sys.stdin.readline N = int(input()) num ..