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를 뒤로 ..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제를 딱 보자마자 드는 생각은 모든 경우의 수를 m으로 나누고 나누어 떨어지면 answer += 1 하는 생각이 들었지만 당연히 이렇게 하면 시간초과가 뜰게 뻔하다. 그래서 고등학교 때 수학에서 배웠던 것들을 사용하여 풀었다. 고등학교 때 수열을 하면서 부분합을 배웠었고, 어떤 두 수를 나누었을 때 나머지끼리 빼서 0이 되면 원래 나누기 전의 수끼..