길이가 $N$인 수열 ${a_n}$에서 연속되는 $K$개의 원소의 합 중 가장 큰 값을 구하여라. 보기에는 간단해 보이는 이 문제, 어떻게 해결할 수 있을까? 방법1: 모두 계산해보기 가장 먼저 떠오르는 방법은 반복문을 이용해 모두 다 계산해보는 방법이다. 가능한 모든 범위에 대해 합을 구한 후, 최댓값을 출력하면 정답이 나오게 된다. answer = -float('inf') for i in range(N - K + 1): answer = max(answer, sum(a[i:i+K])) print(answer) 위 방식의 시간 복잡도는 $O(NK)$이다. 방법2: 불필요한 연산 줄이기 (슬라이딩 윈도우) 방법1의 방법을 표로 나타내면 아래와 같다. $i = 0$에서 $i = 1$로 갈 때, 식에서 $a[..
