안녕하세요! 이번 강좌에서는 파이썬을 활용한 알고리즘 문제 중 하나인 연속 합 구하기에 대해 다루어 보겠습니다. 이 문제는 다양한 경로로 접근할 수 있으며, 알고리즘을 공부하는 데 매우 유용합니다. 문제를 풀기 위해 필요한 기초 이론부터 해결 과정까지 자세히 설명할 것입니다.
문제 설명
주어진 정수 배열 arr가 있을 때, 이 배열 내에서 연속된 k개의 요소의 합을 최대화하는 알고리즘을 작성하시오. 배열의 길이는 n으로 주어지며, k는 1 이상 n 이하의 정수입니다. 즉, 우리는 배열 내에서 연속된 k개의 원소의 합을 구하고 이 값의 최대값을 반환해야 합니다.
입력
- 첫 번째 줄에 배열의 크기
n(1 ≤ n ≤ 100,000) - 두 번째 줄에
n개의 정수로 이루어진 배열arr(-109 ≤ arri ≤ 109) - 세 번째 줄에
k(1 ≤ k ≤ n)
출력
연속된 k개의 요소의 합의 최대값을 출력합니다.
예제 입력
5 1 2 3 4 5 3
예제 출력
12
설명
주어진 배열에서 연속된 3개의 요소의 합을 구해보면, 3+4+5=12로 가장 큰 값을 가집니다.
문제 풀이 과정
이 문제를 풀기 위해서는 연속합을 계산할 수 있는 알고리즘이 필요합니다. 단순하게 배열을 순회하며 모든 연속된 k개의 원소를 합산하고 최대값을 구한다면, 시간복잡도가 O(n*k) 가 되어 최대 n이 100,000일 경우 불가능합니다. 따라서 더욱 효율적인 방법으로 해결해야 합니다.
슬라이딩 윈도우 기법
이 문제를 해결하기 위한 유용한 기법 중 하나는 슬라이딩 윈도우(Sliding Window)입니다. 슬라이딩 윈도우는 주어진 배열 또는 리스트에서 특정 크기를 가진 연속적인 부분 배열을 빠르게 계산하는 방법입니다. 이 기법을 사용하면 시간 복잡도를 O(n)으로 줄일 수 있습니다.
알고리즘 설명
- 처음
k개의 원소를 합산하여 현재의 최대합으로 설정합니다. - 그 다음,
k개의 요소에 초점을 맞추고 하나의 요소를 제거하고 새롭게 추가된 요소를 추가하여 합을 갱신합니다. - 이 과정을 배열의 끝까지 반복하며 최대합을 갱신합니다.
구현 코드
이제 이 알고리즘을 파이썬으로 구현해 보겠습니다. 다음은 슬라이딩 윈도우를 사용한 구현입니다:
def max_sum_k_elements(n, arr, k):
# 초기 윈도우 합산
current_sum = sum(arr[:k])
max_sum = current_sum
# 슬라이딩 윈도우를 사용하여 나머지 원소 탐색
for i in range(k, n):
current_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, current_sum)
return max_sum
# 입력값 처리
n = int(input())
arr = list(map(int, input().split()))
k = int(input())
# 최대 연속합 출력
print(max_sum_k_elements(n, arr, k))
코드 설명
코드의 각 부분을 자세히 살펴보겠습니다:
def max_sum_k_elements(n, arr, k):– 함수 선언 부분으로 입력받은 배열과k를 사용하여 최대 합을 계산합니다.current_sum = sum(arr[:k])– 초기 윈도우의 합을 계산합니다.max_sum = current_sum– 현재의 최대합을 초기화합니다.for i in range(k, n):– 슬라이딩 윈도우를 위해k부터n까지 반복합니다.current_sum += arr[i] - arr[i - k]– 새로운 원소를 포함하고, 제외된 원소를 빼며 현재 합을 갱신합니다.max_sum = max(max_sum, current_sum)– 최대 합을 업데이트합니다.return max_sum– 최종 최대 합을 반환합니다.
결론
이제 우리는 배열에서 연속된 k개의 원소의 합을 최대화하는 문제를 해결했습니다. 슬라이딩 윈도우 기법을 사용함으로써 시간 복잡도를 효과적으로 줄일 수 있었고, 이는 실제 취업 코딩테스트에서 매우 유용한 테크닉입니다.
추가적으로, 이 문제는 다른 형태로도 변형될 수 있기 때문에, 다양한 예제를 통해 더욱 연습하시길 추천드립니다.