누적합 - 백준 11659, 2559
누적합은 말그대로 합을 누적하는건데.. 어떻게 코드를 짜느냐에 따라 시간복잡도가 엄청 달라진다..
먼저 가장 기본 중의 기본인 문제부터 풀어보자
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
하나의 배열이 주어지고 시작점과 끝 지점의 구간합을 구하는 문제이다.
import sys
input = sys.stdin.readline
n,cases = map(int,input().rstrip().split())
li = list(map(int,input().rstrip().split()))
#누적합을 저장할 배열 d를 생성한다.
d = [0] * (n+1)
#d에 각 구간에 따른 합을 만든다
for i in range(n) :
d[i+1] = d[i] +li[i]
#start와 end지점에 따라 slice를 이용해 값을 계산한다
for i in range(cases) :
s,e = map(int,input().rstrip().split())
print(d[e]-d[s-1])
http://acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
이건 그리 어렵지 않은 문제였다
import sys
input = sys.stdin.readline
#전체 날짜n, 타겟 날짜t
n,t = map(int,input().rstrip().split())
li = list(map(int,input().rstrip().split()))
answer = []
#시작점부터 타겟날짜까지 합을 sumNum에 할당하고 answer에 입력
sumNum = sum(li[0:t])
answer.append(sumNum)
#t부터 시작해서 더해주고 앞으로 이동하면서 빠지는 날짜의 값을 빼준다.
for j in range(t,n) :
sumNum += li[j]
sumNum -= li[j-t]
answer.append(sumNum)
#최대값 출력
print(max(answer))
http://acmicpc.net/problem/16139
16139번: 인간-컴퓨터 상호작용
첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째
www.acmicpc.net
문자열이 주어지고 임의의 길이에 속한 문자의 갯수를 구하는 문제였다
처음에 보기에 a만 있어서 입력된 문자 하나만 계속 물어보는 줄 알았는데
그게 아니였다..ㅋㅋ그래서 dict를 활용해서 문자열을 key로 문자열의 구간합을 value로하는 dict를 통해 해결했다..
import sys
input = sys.stdin.readline
string = input().rstrip()
cnt = int(input().rstrip())
ans = {}
for i in range(cnt) :
#대상문자열v, start,end
v,s,e = map(str,input().rstrip().split())
#v가 ans.key배열에 존재하지 않으면 if문 실행
if v not in ans.keys() :
#문자열 v에 따른 누적합 d배열 생성
d = [0] *(len(string)+1)
for j in range(1,len(string)+1) :
if string[j-1] == v :
d[j] = d[j-1]+1
else :
d[j] = d[j-1]
#문자열을 ans의 key로, d배열을 value로 삽입
ans[v] = d
#정답출력
print(ans[v][int(e)+1]-ans[v][int(s)])
https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
이 문제 진짜 어려웠다..
나는 구간합을 구해서 나머지를 계속 계산해가는 방법으로 답을 구했는데 시간초과였다..
그리고 주어진 배열을 나머지로만 만든 다음에 구간합으로 계산해줬는데도 시간초과여서 다른사람들 풀이를 봤다..
구간합에서 바로 나머지를 구하는 것 까진 같은데 나머지들로만 d배열을 만들어서 또 거기에서 조합을해서
정답을 풀어나가는 방법..한 수 배웠다..
import sys
input = sys.stdin.readline
#배열의 길이n 나누는 숫자t
n,t = map(int,input().rstrip().split())
li = list(map(int,input().rstrip().split()))
d = [0]*t
num = 0
#li 순회
for i in li :
num += i
#num을 t로 나눠준 나머지의 인덱스에 해당하는 값에 1을 더해준다
d[num%t] += 1
#여기서 d[0]은 t로 나눠떨어진 갯수를 의미한다.
answer = d[0]
#d를 순회한다
#j는 인덱스에따라 나머지가 1인 갯수, 2인갯수...를 갖는다
for j in d :
#j*(j-1)//2 전체 갯수j에서 2개만 고르는 jC2의 식이다
#이게 무슨말이냐면 나머지가 1인게 2개라면 하나는 더하고 하나는 빼주면
#나머지가 0이 되므로 조건 t로 나눴을때 0을 만족하는 배열이 된다.
#이게 핵심이다..
answer += j*(j-1)//2
print(answer)
이렇게 누적합 문제를 같이 풀어봤는데
너무 안풀리면 다른사람들 풀이를 공부해서 완벽하게 이해하는 것도 좋은 방법이라고 생각한다..
물론 실무에서는 이런 스승이 없을 수도 있지만 배움에 있어서는 빠른 길인 것 같다.