누적합 - 백준 11659, 2559

누적합은 말그대로 합을 누적하는건데.. 어떻게 코드를 짜느냐에 따라 시간복잡도가 엄청 달라진다..

 

먼저 가장 기본 중의 기본인 문제부터 풀어보자

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

하나의 배열이 주어지고 시작점과 끝 지점의 구간합을 구하는 문제이다.

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번: 수열

이건 그리 어렵지 않은 문제였다

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번: 인간-컴퓨터 상호작용

문자열이 주어지고 임의의 길이에 속한 문자의 갯수를 구하는 문제였다

처음에 보기에 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번: 나머지 합

이 문제 진짜 어려웠다..

나는 구간합을 구해서 나머지를 계속 계산해가는 방법으로 답을 구했는데 시간초과였다..

그리고 주어진 배열을 나머지로만 만든 다음에 구간합으로 계산해줬는데도 시간초과여서 다른사람들 풀이를 봤다..

 

구간합에서 바로 나머지를 구하는 것 까진 같은데 나머지들로만 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)

이렇게 누적합 문제를 같이 풀어봤는데

너무 안풀리면 다른사람들 풀이를 공부해서 완벽하게 이해하는 것도 좋은 방법이라고 생각한다..

물론 실무에서는 이런 스승이 없을 수도 있지만 배움에 있어서는 빠른 길인 것 같다.