(BOJ)-2559, Python

문제 요약

출처: (BOJ)2559 - 수열

수열 N이 주어졌을 때, K일 연속된 원소의 합이 가장 큰 값을 찾는 문제이다.

• N: 원소의 수
• K: 연속된 원소의 수

접근 과정

1. 완전탐색 접근

리스트를 순회하며, 각 인덱스 i부터 i+K-1까지의 부분합을 모두 구하고 가장 높은 값을 찾아내자!

코드 구현

N, K = map(int, input().split())
arr = list(map(int, input().split()))
answer = []
for i in range(N+1):
    sum = 0
    if i+K-1 == len(arr)-1: 
        for j in range(i, i+K):
            sum += arr[j]
        answer.append(sum)
        break
    else:
        for j in range(i, i+K):
            sum += arr[j]
        answer.append(sum)
        
print(max(answer))

2. 누적합 접근

위의 완전탐색 방법은 직관적이지만, 각 인덱스마다 구간의 부분합을 매번 계산하므로 비효율적인 문제가 있었음을 알 수 있었다. 이를 해결하기 위해 누적합(prefix sum) 을 이용할 수 있는데, 누적합은 각 원소의 합을 누적하여 계산해둔 배열이다. 이를 통해 반복적인 부분합 계산을 줄일 수 있다는 점만 이해하면 된다. 예제를 통해 어떻게 사용되는지 알아보도록 하자!

수열: [1, 2, 3, 4, 5]
누적합: [1, 3, 6, 10, 15]

위 수열에서, 누적합의 각 값은 다음과 같이 계산된다 :

• 1: 1
• 3: 1 + 2
• 6: 1 + 2 + 3
• 10: 1 + 2 + 3 + 4
• 15: 1 + 2 + 3 + 4 + 5

입력값으로 N=5, K=2와 위 수열이 주어졌다고 하자. 여기서, 길이가 2이고 연속된 구간합의 최대값을 구하는 문제이기에, 답은 쉽게 9(4+5)임을 알 수 있다. 이를 누적합으로 풀어보면, 누적합에서 5번째 원소는 15이고, 누적합에서 3번째 원소는 6이다. 따라서, 구간 [4, 5]의 합은 누적합[5]-누적합[5-2(=K)]로 계산할 수 있다!

코드 구현

N, K = map(int, input().split())
arr = list(map(int, input().split()))
prefix = [0 for _ in range(N+1)] 

for i in range(N):
    prefix[i+1] = prefix[i] + arr[i]
    
answer = []
for k in range(K,N+1):
    answer.append(prefix[k] - prefix[k-K])  
    
print(max(answer))

회고

같은 문제에 대해 다양한 접근 방법으로 문제를 풀어보면서, 바라보는 시야를 조금이나마 넓힐 수 있었다. 그리고 누적합이라는 간단하면서도 효율적인 아이디어를 얻어간 것 같다!