Code Etc/코딩테스트

누적합 - 백준 11659, 2559

CoderHan 2023. 4. 28. 02:22
반응형

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

 

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

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)

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

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

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

반응형