누적 합 누적 합이란 수열에 대해 각 인덱스까지의 구간의 합을 구하는 것을 의미합니다. 모든 구간에 대해 단순하게 반복하여 하나씩 더해가는 방법을 사용하게 되면 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있습니다. 하지만 이전 인덱스까지의 누적합에 현재 값을 더하는 방식인 누적 합을 사용하면 O(n)의 시간 복잡도를 가질 수 있습니다. 배열에 따라 누적합을 저장해놓은 뒤, 구하고자 하는 범위까지의 누적합에서 해당 범위에 포함되지 않는 범위를 빼주면 구할 수 있습니다. 따라서 배열의 특정 범위의 구간 합을 구하고자 한다면, 해당 알고리즘이 매우 유용할 수 있습니다. 예시 백준 11659 문제인 구간 합 구하기 4를 통해 누적합에 대해 알아보겠습니다. 우선 5 4 3 2 1에 대한 누적합을 구하고 배..
[Silver III] 블로그 - 21921 문제 링크 성능 요약 메모리: 84696 KB, 시간: 92 ms 분류 누적 합, 슬라이딩 윈도우 문제 설명 찬솔이는 블로그를 시작한 지 벌써 N일이 지났다. 요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다. 찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 입력 첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다. 둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다. 출력 첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대..
[Gold IV] 부분합 - 1806 문제 링크 성능 요약 메모리: 76292 KB, 시간: 48 ms 분류 누적 합, 두 포인터 문제 설명 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 풀이 투 포인터 문제로, 배열을 정렬한..
