[99클럽 코테 스터디 5일차 TIL] 백준 2559 수열 Python 투포인터

오늘의 학습 키워드

투포인터

공부한 내용 본인의 언어로 정리하기

문제

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

코드

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
temp = list(map(int, input().split()))
result = 0
for i in range(0, n - k):
    sums = 0
    for j in range(i, i + k):
        sums += temp[j]
    if sums > result:
        result = sums
print(result)

 

처음에는 모든 케이스마다 합을 구하고 해당 케이스가 기존 값보다 클 경우 갱신하는 이중 for문으로 문제를 풀었지만 시간초과로 실패하였다. 따라서 이중for문을 사용하지 않고도 문제를 푸는 방법인 투포인터를 활용하였다. 

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
temp = list(map(int, input().split()))
result = 0
sums = 0
for i in range(0, k):
    sums += temp[i]
    result = sums

for i in range(k, n):
    sums -= temp[i-k]
    sums += temp[i]
    if sums > result:
        result = sums

print(result)

 

먼저 0~k까지 첫번째 합을 구한다. 그후 두번째 합부터 기존에 구해둔 합에 이전값을 제거하고 새로운 값을 추가하며 합을 지속적으로 갱신한다. 이후 최대값을 찾으면 이를 갱신한다. 

 

• 첫 윈도우의 합을 미리 구해놓기
• 윈도우를 한 칸씩 밀면서 (이전 값 제거 + 새로운 값 추가) 합을 업데이트하기
• 최대값을 갱신하면서 진행하기

 

오늘의 회고

1. 투 포인터(Two Pointers)란?

투 포인터 알고리즘은 두 개의 포인터를 활용해 배열이나 리스트를 효율적으로 탐색하는 기법으로 이중 반복문(브루트포스)보다 빠르게( O(N) O(N) O(N) ) 문제를 해결할 수 있는 경우에 많이 사용된다.

 

투 포인터의 기본 원리:

• 두 개의 포인터를 활용해 문제를 해결
• 한 번의 순회(혹은 제한된 이동)로 원하는 결과를 찾음
• 불필요한 반복을 줄여 시간 복잡도를 개선 (주로 O(N2)→O(N)O(N^2) → O(N)O(N2)→O(N) 으로 줄임)

2. 투 포인터가 사용되는 유형

1. 정렬된 배열에서 두 수의 합 찾기 (ex: 두 수의 합이 특정 값이 되는 경우 찾기)
2. 연속된 부분 수열 찾기 (ex: 합이 특정 값이 되는 부분 수열 찾기)
3. 슬라이딩 윈도우 (ex: 연속된 K개의 원소 중 최댓값 찾기)
4. 두 개의 리스트(배열) 병합 (ex: 정렬된 두 리스트를 하나로 합치기)

투포인터에 대해 배울 수 있었다. 막연하게 투포인터에 대한 문제는 풀었어도 개념을 완벽하게 이해하고 풀지는 않았는데 해당 문제에 대해 배울 수 있어서 좋았다.