백준 2559번 - 수열 - 파이썬(Python)

문제 링크

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

문제

 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,
3 -2 -4 -9 0 3 7 13 8 -3
모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.
또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.
매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

 

입력 조건

• 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력 조건

• 첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

 

입력 예시1

10 2
3 -2 -4 -9 0 3 7 13 8 -3

출력 예시1

21

입력 예시2

10 5
3 -2 -4 -9 0 3 7 13 8 -3

출력 예시2

31

 

풀이 전 생각

 문제에서 주어진 대로 파이썬의 인덱싱을 이용하여 온도합을 구하고 마지막에 최대값을 출력하면 간단히 해결될 것이라고 생각했지만, 시간 초과 문제가 발생했다.

예제 코드(시간 초과)

n,k=map(int,input().split())
list = [int(x) for x in input().split()]
result = []
for i in range(n-k+1):
    result.append(sum(list[i:i+k]))
print(max(result))

 이 문제에서도 시간 초과가 발생했다. 그래서 찾아보니 '슬라이딩 윈도우'라는 기법이 있었고, 이름은 거창하지만 간단하다. 위 코드처럼 반복문을 돌면서 k만큼의 요소들을 계속 더해주는 방식이 아니라 k만큼의 합을 한번 더하고 나서 그 뒤로는 더하기 연산을 줄이기 위해 앞의 요소를 하나 제거하고 뒤의 요소를 하나 더해주는 간단한 방식이다. 이를 적용한 후의 예제코드는 아래와 같다. 이 둘의 시간복잡도 차이에 대해서는 포인트에 설명하도록 하겠다.

예제 코드

 

n,k=map(int,input().split())
list = list(map(int,input().split()))
current_sum = sum(list[:k])
max_sum = current_sum
for i in range(1,n-k+1):
    current_sum = current_sum - list[i-1] + list[i+k-1] 
    max_sum = max(current_sum,max_sum)
print(max_sum)

 

포인트

 내가 기존에 작성한 코드와 '슬라이딩 윈도우'를 적용한 후의 시간복잡도 차이에 대해 자세히 다뤄보고자 한다.

 

시간 초과가 발생한 기존 코드에서

for i in range(n - k + 1): # O(N - K + 1) ≈ O(N)

    result.append(sum(list[i:i+k])) # O(K) 연산을 반복

• sum(list[i:i+k])는 리스트의 i번째부터 i+k-1번째까지 합을 계산 → O(K)
• for 루프는 (N-K+1)번 실행되므로 O(N-K+1) ≈ O(N)

=> 총 복잡도: O(N) × O(K) = O(NK)

즉, 최악의 경우 N = 100,000, K = 100,000이면 O(10,000,000,000) (100억 번 연산) 

이 문제의 시간 제한은 1초인데, 백준에서 1초는 약 1억번의 연산이 가능한 시간이라고 한다. 따라서 시간 초과가 발생하게 되었다.

 

'슬라이딩 윈도우'를 적용한 코드에서

for i in range(n - k + 1): # O(N - K + 1) ≈ O(N)

    current_sum = current_sum - arr[i] + arr[i + k]   #  O(1)

• current_sum을 업데이트하는 연산은 덧셈, 뺄셈, 리스트 인덱싱 세 가지로 이루어짐.
• 각각 O(1) 연산이므로, 한 번 반복 시 O(1).

=>총 복잡도: O(N - K) ≈ O(N)

생각

  사실 문제를 풀면서 아직 시간복잡도에 관한 문제는 생각하지 않고 그냥 생각나는 대로 풀고 있는데, 최근 몇 문제에서 시간 초과 문제가 발생하다보니 내가 작성한 코드의 실행 시간은 얼마나 걸리게 될 지, 백준의 채점 기준인 시간 제한을 통과할 수 있을지에 관심이 생기면서 관련 정보를 찾아보았다. 우선 당분간은 1초에 1억번 정도의 연산을 할 수 있다는 정도만 기억해두고 나중에 또 문제가 발생한다면 더 깊이 찾아보아야겠다.