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칸의 범위를 일정하게 움직인다처음에는 움직일 ..

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 ..

https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 백준 2018번과 비슷하게 숫자를 변수로 지정해 푸는 문제로 두 수를 더해서 특정 숫자로 만드는 경우가 몇 갠지 묻는다. 코드를 단순 구현하듯이 쓰다가 정렬을 해야지만 숫자를 포인터로 지정할 수 있겠다 싶었다. 파이썬은 sort함수를 사용하면 오름차순으로 정렬해준다. 첫 번째 숫자를 리스트의 맨 처음, 두 번째 숫자를 맨 마지막으로 지정해 준다 합해서 만들어야 하는 숫자가..

https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한www.acmicpc.net모든 경우의 수에 대해서 해당하는 가짓수를 찾을 때마다 연산을 다시 한다면 상당히 비효율적일 것이다. 따라서 이전에 했던 연산(합)을 그대로 이어나가는 방법을 이용하여 풀었다.아이디어는 그리 복잡하진 않다.  맨 처음 합(total)을 1로 저장하고 start와 end로 구간을 정한다. 그리고 start부터 end까지의 합을 total에 저장하는데 total 이면 end를 뒤로 ..