[#2559] 수열

RookieAND·2022년 8월 25일

누적합 백준 코테 투포인터

BaekJoon

목록 보기

30/42

❓ Question

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

📖 Before Start

누적 합을 사용하여 연속하는 수열 중 최댓값을 찾는 문제였다.

이번 문제는 투 포인터를 활용하여 수열의 합 중 최댓값을 구하는 문제였다.
투 포인터라는 개념을 전혀 모르고 있었기에, 이번 기회로 알고자 했다.

✒️ Design Algorithm

누적 합을 응용하면서, 다음 연속하는 수열의 합을 효율적으로 구한다.

N 개의 정수가 담긴 수열에서, 길이가 K 인 연속하는 수열의 합을 구해야 한다.
처음 문제를 풀 때는 단순하게 앞의 인덱스부터 K 개만큼의 숫자를 차례대로 뽑아
합을 구하고, 기존의 최댓값과 대소비교를 통해 상태를 업데이트 할지 결정하였다.

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline
N, K = map(int, read().split())
numbers = list(map(int, read().split()))

result = 0
for i in range(N - K + 1):
    result = max(sum(numbers[i:i+K]), result)

print(result)

역시나 바로 시간 초과가 떴다. 예상했던 결과라 놀랍진 않았지만..

100,000 개나 되는 숫자를 일일히 완전탐색으로 검사하는 건 역시 무리였다.
결국 누적 합이 무엇인지 궁금해 개인적으로 자료를 찾아보며 원리를 이해했다.

✅ Correct Code

import sys

read = sys.stdin.readline
N, K = map(int, read().split())
numbers = list(map(int, read().split()))

result = [sum(numbers[:K])]
for i in range(N - K):
    result.append(result[i] - numbers[i] + numbers[K + i])

print(max(result))

각 구간의 누적 합을 리스트에 넣고, 다른 영역의 값을 더하거나 빼서 구한다.
이렇게 두 인덱스 (포인터) 를 활용하는 방식을 투 포인터 라고 한다.

상당히 흥미롭고 놀라운 풀이 과정이었다. 공통된 영역의 누적 합은 그대로 유지하면서
영역이 달라지는 양 끝의 값에 대한 검수만 추가적으로 진행하면 그만이었으니까...

먼저 0 번째 인덱스부터 K - 1 번째 인덱스까지의 합을 구하고, 이를 List 에 넣는다.
이후 반복문으로 다음 연속하는 수열인 1 번째 인덱스부터 K 번째 인덱스를 구하는데,
이때 이전의 연속 수열의 합을 불러온 뒤, 두 수열이 겹치지 않는 값들을 빼거나 더해준다.

i 번째부터 시작하는 수열의 누적합에서, 이후의 연속하는 수열의 누적합을 구하는 방법은 아래와 같다.