[백준] 12847번 : 꿀 아르바이트 - 파이썬

백준 12847

아이디어 : 슬라이딩 윈도우

ChatGPT : 슬라이딩 윈도우

슬라이딩 윈도우(Sliding Window) 알고리즘은 연속적인 부분 문자열(substring)을 처리하는데 사용되는 알고리즘입니다. 이 알고리즘은 윈도우(Window)라고 불리는 고정 길이의 부분 문자열을 유지하면서, 문자열을 왼쪽에서 오른쪽으로 한 칸씩 이동시키면서 처리합니다.

슬라이딩 윈도우 알고리즘은 다양한 문제에서 활용될 수 있습니다. 예를 들어, 문자열에서 특정 조건을 만족하는 최소 혹은 최대 길이의 부분 문자열을 찾는 문제, 또는 배열에서 연속된 부분합이 주어졌을 때 특정 조건을 만족하는 부분합의 개수를 찾는 문제 등이 있습니다.

슬라이딩 윈도우 알고리즘의 기본적인 아이디어는 다음과 같습니다.
1. 윈도우를 초기화합니다. 즉, 문자열에서 첫 k개의 문자를 포함하는 윈도우를 만듭니다.
2. 윈도우를 한 칸씩 이동시키면서, 각 위치에서 윈도우 내부의 부분 문자열을 처리합니다.
3. 윈도우를 이동할 때마다, 윈도우의 왼쪽 끝에 있는 문자를 제거하고, 오른쪽 끝에 새로운 문자를 추가합니다.
4. 처리 결과를 수집합니다.

슬라이딩 윈도우 알고리즘은 일반적으로 O(n) 시간 복잡도를 가지며, 상수항은 윈도우의 크기와 처리하는 함수에 따라 달라집니다. 이 알고리즘은 빠른 속도와 적은 메모리 사용량으로 효율적인 처리를 가능하게 합니다.

문제 해결 과정

연속된 m 개의 숫자 합의 최대 값을 구하는 문제

n개의 수가 주어졌을 때, 최대 값을 구하기 위해 n * m 을 하면 O(n*m) 된다.

따라서, 슬라이딩 윈도우 알고리즘 개념을 이용하여 시간 복잡도를 줄인다.

슬라이딩 윈도우는 기존 연속된 수의 합에서 연속된 수의 시작값을 빼고, 다음 연속된 값을 더하면서 최대값을 찾는 알고리즘이다.

즉, sum = A[i] + A[i+1] + A[i+2]

max = sum

sum = sum - A[i] + A[i+2]

if max < sum

이다.

 

나의 답안

# -*- coding: utf-8 -*- 
# [12847] 꿀 아르바이트
# 누적 합, 슬라이딩 윈도우
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
array = list(map(int, input().split()))

sum = 0

i = 0
max = 0
sum = 0

for i in range(m):
    sum = sum + array[i]

max = sum

i = m
s = 0
while i < n:
    sum = sum - array[s]
    sum = sum + array[i]
    i = i + 1
    s = s + 1
    if max < sum:
        max = sum

print(max)

https://www.acmicpc.net/status?user_id=timo15&problem_id=12847&from_mine=1 

채점 현황