백준

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/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/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이 되면 원래 나누기 전의 수끼..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 이 문제는 백준 11659번의 상위 문제로 구간합의 성질을 2차원 배열에서 이용한 문제다. 문제를 처음 봤을때 잘 이해가 안갔었는데 밑의 표에서 (2,2)부터 (3,3)까지의 합을 구하라고 한다면 (2,2), (2,3), (2,4), (3,1), (3,2). (3,3) 으로 모두 더하는 문제로 잘못 이해했다. (이래서 예시를 잘 봐야하는....) 하이튼 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 물론 입력받는 숫자들을 리스트에 다 넣어서 구간을 다 더하는 방법도 있겠지만, 구간 합을 구하는 성질을 이용하면 효율적으로 문제를 해결할 수 있다. 고등학교 시절 수열을 배울 때 수열의 합(S)을 구하고 구간을 다루는 연습을 했었다. 비록 규칙이 있는 수들이 아닐지라도 구간을 다루는 방법은 똑같으므로 떠오른다면 문제푸는데 도움이 될 것이다. 그래서 사용할 방법은 구간 합 배..