알고리즘/알고리즘 풀이

99클럽 코테 스터디 5일차 TIL : 누적합 문제

매룬어 2025. 4. 4. 23:31

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

백준 2559번 문제 풀이. 

오늘의 학습 키워드

 오늘은 시간제한이 빡빡한 관계로 '누적합'을 사용했다.

 

핵심 개념 설명

누적합 설명

 그림을 보자. 배열에 숫자들을 더하고 싶다. 

  • 방법1. 기존처럼 더하기
    • 0번째 인덱스값 + 1번째 인덱스 값 + ... n번째 인덱스값
  • 방법2. 누적해서 계산 : 이전값들의 누적값 + 현재 값 인 것을 '누적합' 이라 부른다
    • 1. 0번째 인덱스값
    • 2. 1번 + 1번째 인덱스값
    • 3. 2번 + 2번째 인덱스값....

  저 그림에서 1번째 인덱스~ 4번째 인덱스 값을 더해보자.

누적합 예시

  • 방법1 : 1번째 인덱스 + 2번째 인덱스 + 3번째 인덱스 + 4번째 인덱스
  • 방법2(누적합) : 보라색 - 노란색 = 4번째까지의 누적합 - 0번째까지의 누적합. 

 방법1은 4번이나 하고 방법2는 1번의 연산으로 구할 수 있다.

 

 

공부 내용

<처음 문제풀이>

n , k = map(int, input().split())
array_text = input()
array = [int(i) for i in array_text.split(" ")]
res = -101

for i in range(0, len(array)-k+1):
    tmp_sum = 0

    start_idx = i
    end_idx = i+k -1
    tmp_array = array[start_idx:end_idx+1]
    for j in tmp_array:
        tmp_sum += j
    if tmp_sum > res:
        res = tmp_sum
#print('res : ' , res)
print(res)

 처음에는 윈도우 슬라이싱으로 문제를 풀었었다. 하지만 시간초과가 발생했었다.

그러면 이중 for문 대신 다른 방법으로 했어야했다.

 

<두번째 문제> 

n , k = map(int, input().split())
array_text = input()
array = [int(i) for i in array_text.split(" ")]
s = []
s.append(sum(array[:k])) #0번째 순서 누적합

for i in range(n-k):
    s.append(s[i] + array[k+i] - array[i])
#print('res : ' , res)
print(max(s))

 

누적합을 이용해서 풀었다.

 

알고리즘 설명

 

s.append(sum(array[:k])) #0번째 순서 누적합

 저 그림의 노란색 부분을 나타낸 코드다.

 

for i in range(n-k):
    s.append(s[i] + array[k+i] - array[i])

현재 누적합에서 다음번째 누적합을 s 리스트에 삽입하는 부분이다.

그림을 보면 노란색(0번째 순서 누적합) 과 초록색(1번째 순서 누적합)을 쉽게 구할 수 있다. 
노란색의 가장왼쪽 인덱스를 빼고, 초록색의 가장 오른쪽 인덱스를 더하면 된다.

 

그런식으로 n-k 전까지 반복한다.

 

오늘 회고

 오늘은 누적합 알고리즘을 다시 한번 떠올리는 계기가 되었다... 

이걸 사용하지 않은지 오래되어서 깜빡 잊고 있었던 것이다.

그리고 시간제한을 다시한번 엄수해야겠다.

댓글수0