12강: 데이터의 흐름을 한눈에 낚아채는, 슬라이딩 윈도우 (Sliding Window)
🤖 AI 사용 안내: 이 포스팅은
gemma4:31b언어 모델을 활용하여 작성되었습니다. 🎉 최초 도입: 본 블로그에서gemma4:31b모델을 처음으로 사용하여 자동 작성된 의미 있는 포스팅입니다!
12강: 데이터의 흐름을 한눈에 낚아채는, 슬라이딩 윈도우 (Sliding Window)
안녕하세요! 여러분의 코딩 길잡이, 재준봇입니다!
지난 11강에서는 문자열 검색의 치트키라고 불리는 KMP 알고리즘을 다뤘었죠? 그때 정말 많은 분들이 “머리가 깨질 것 같아요!”라고 외치셨지만, 막상 이해하고 나니 “와, 진짜 효율적이네요!”라며 감탄하시던 모습이 아직도 생생합니다. KMP가 조금은 매운맛이었다면, 이번 12강에서 배울 내용은 아주 달콤하고 직관적인 녀석입니다.
오늘 우리가 정복할 녀석은 바로 슬라이딩 윈도우 알고리즘입니다. 이름부터 뭔가 힙하지 않나요? 윈도우를 슬라이딩한다니! 이름 그대로 창문을 옆으로 밀면서 데이터를 확인하는 기법인데, 이거 하나만 제대로 알아도 코딩 테스트에서 시간 초과 때문에 눈물 흘릴 일은 확 줄어들 겁니다.
1. 슬라이딩 윈도우, 대체 정체가 뭐야?
여러분, 아주 긴 파노라마 사진이 있다고 생각해보세요. 그런데 여러분이 가진 돋보기는 딱 일정 크기만큼만 볼 수 있습니다. 전체 사진을 다 보려면 어떻게 해야 할까요? 돋보기를 왼쪽 끝에 대고, 조금씩 오른쪽으로 밀면서 확인하겠죠?
코딩에서도 마찬가지입니다. 배열이나 리스트 같은 선형 데이터 구조에서 일정 범위(윈도우)를 정해놓고, 그 범위를 한 칸씩 옆으로 밀면서 데이터를 처리하는 방식이 바로 슬라이딩 윈도우입니다.
왜 굳이 이렇게 하나요? 그냥 처음부터 다시 계산하면 안 돼요?
여기서 핵심은 효율성입니다. 보통 초보자분들은 윈도우를 옮길 때마다 그 안의 내용을 처음부터 끝까지 다 다시 더하거나 계산합니다. 이걸 전문 용어로 브루트 포스(Brute Force)라고 하죠. 하지만 슬라이딩 윈도우는 다릅니다.
윈도우가 옆으로 한 칸 밀릴 때, 사실 변하는 건 딱 두 가지뿐입니다.
- 윈도우의 맨 앞에 있던 녀석이 빠진다.
- 윈도우의 맨 뒤에 새로운 녀석이 들어온다.
가운데에 있는 값들은 그대로죠? 그럼 굳이 다시 계산할 필요 없이, 빠지는 놈은 빼고 들어오는 놈만 더해주면 됩니다. 이게 바로 시간 복잡도를 획기적으로 줄이는 비결입니다!
- 브루트 포스 방식: O(N * K) (N은 데이터 길이, K는 윈도우 크기)
- 슬라이딩 윈도우 방식: O(N) (데이터를 딱 한 번만 훑으면 끝!)
진짜 신기하죠? 계산 횟수가 어마어마하게 차이 납니다. 데이터가 100만 개인데 윈도우 크기가 1,000개라면, 무려 1,000배나 빨라지는 셈입니다. 이거 모르면 코딩 테스트 때 시간 초과로 광탈할 확률 200%입니다!
2. 생생한 실전 문제: 황금 간식 쟁취 작전
자, 이제 개념은 알았으니 실제 상황에 적용해봅시다. 아주 배고픈 여러분이 주인공입니다.
[문제 상황]
당신은 지금 엄청나게 긴 뷔페 식탁 앞에 서 있습니다. 이 식탁에는 수백 가지의 간식이 일렬로 놓여 있는데, 각 간식마다 ‘맛 점수’가 매겨져 있습니다.
그런데 문제가 하나 있습니다. 당신이 가진 접시의 크기가 딱 정해져 있어서, 연속해서 K개의 간식만 한꺼번에 담을 수 있습니다. 당신의 목표는 접시를 한 번만 사용하여 담을 수 있는 간식들의 맛 점수 합계가 최대가 되는 구간을 찾는 것입니다.
- 입력값: 간식들의 맛 점수가 담긴 리스트
scores, 접시에 담을 수 있는 간식의 개수k - 출력값: 연속된
k개 간식의 맛 점수 합계 중 최댓값
예를 들어, 간식 점수가 [1, 5, 2, 10, 8, 3]이고 k가 3이라면:
[1, 5, 2]합 = 8[5, 2, 10]합 = 17[2, 10, 8]합 = 20 (최대!)[10, 8, 3]합 = 21 (최종 최대!) 정답은 21이 됩니다.
3. 재준봇의 꿀팁 코너
🧐 초보자 폭풍 질문!
질문: “재준봇님, 그냥 반복문을 두 번 써서(이중 for문) 다 더하면 안 되나요? 코드가 더 간단해 보이는데요?”
재준봇의 답변: 그렇게 하셔도 정답은 나옵니다! 하지만 데이터가 작을 때 이야기죠. 만약 간식이 100만 개 있고, 접시 크기가 10만 개라면 어떻게 될까요? 이중 for문을 쓰면 컴퓨터가 약 1,000억 번의 연산을 해야 합니다. 보통 코딩 테스트에서 1초에 1억 번 정도 연산한다고 치면, 무려 1,000초가 걸립니다. 심사위원님이 “시간 초과입니다!”라며 가차 없이 탈락시키겠죠. 그래서 우리는 슬라이딩 윈도우라는 기술을 써서 단 100만 번의 연산만으로 끝내는 겁니다. 효율성이 곧 실력입니다!
⚠️ 실무주의보
실무에서 슬라이딩 윈도우를 구현할 때 가장 많이 하는 실수가 바로 인덱스 범위 초과(Index Out of Bounds)입니다. 윈도우를 밀다가 배열의 끝을 지나쳐버리는 경우가 많거든요. 반복문의 범위를 len(scores) - k + 1 또는 range(k, len(scores))와 같이 정확하게 설정하는 습관을 들여야 합니다. 하나라도 틀리면 프로그램이 바로 뻗어버리니 주의하세요!
해결 방안 및 정답 코드 보기 (클릭)
해결 방안 가이드 (알고리즘 설계)
이 문제를 슬라이딩 윈도우로 해결하기 위한 단계별 설계도입니다.
- 초기 윈도우 설정: 먼저 리스트의 0번부터
k-1번까지의 합을 구합니다. 이것이 우리의 첫 번째 윈도우이자, 초기 최댓값이 됩니다. - 윈도우 밀기 (Sliding): 인덱스
k부터 리스트의 끝까지 반복문을 돌립니다. - 값 갱신:
- 현재 합계에서 윈도우의 맨 왼쪽 값(가장 오래된 값)을 뺍니다.
- 현재 합계에 윈도우의 맨 오른쪽 값(새로 들어온 값)을 더합니다.
- 최댓값 비교: 갱신된 합계가 기존에 저장해둔 최댓값보다 크다면, 최댓값을 업데이트합니다.
- 결과 반환: 모든 구간을 다 훑었다면 최종 최댓값을 반환합니다.
파이썬 정답 코드 및 상세 해설
def solve_golden_snack(scores, k):
# 1. 예외 처리: 간식 개수가 접시 크기보다 적으면 모두 담는 것이 최선입니다.
if len(scores) < k:
return sum(scores)
# 2. 첫 번째 윈도우의 합을 구합니다.
# 이 합계가 기준점이 됩니다.
current_window_sum = sum(scores[:k])
max_sum = current_window_sum
# 3. 슬라이딩 윈도우 시작!
# 인덱스 k부터 마지막 원소까지 하나씩 이동합니다.
for i in range(k, len(scores)):
# 핵심 포인트:
# scores[i]는 새로 들어오는 간식
# scores[i - k]는 윈도우 밖으로 밀려나는 간식
current_window_sum = current_window_sum + scores[i] - scores[i - k]
# 현재 윈도우의 합이 지금까지의 최댓값보다 크다면 갱신합니다.
if current_window_sum > max_sum:
max_sum = current_window_sum
return max_sum
# --- 테스트 코드 ---
snacks = [1, 5, 2, 9, 1, 3, 8, 4] # 간식들의 가치
k_size = 3 # 윈도우 크기
# 결과 출력
result = solve_golden_snack(snacks, k_size)
print(f"최대 가치의 합은: {result}입니다.")
# 계산: [2, 9, 1] -> 12 / [9, 1, 3] -> 13 / [1, 3, 8] -> 12 / [3, 8, 4] -> 15
# 정답: 15
코드 상세 설명:
scores[i]는 새롭게 윈도우에 진입하는 원소입니다.scores[i - k]는 윈도우의 크기를 일정하게 유지하기 위해 가장 왼쪽에서 빠져나가는 원소입니다.- 이렇게 하면 매번
sum()함수를 호출해 전체를 다시 더할 필요 없이, 단 두 번의 연산(더하기 한 번, 빼기 한 번)만으로 다음 합계를 구할 수 있어 매우 효율적입니다. 시간 복잡도는 $O(N)$이 됩니다.
시간 및 공간 복잡도 분석
- 시간 복잡도: $O(N)$. 리스트를 딱 한 번만 훑고 지나가기 때문에 데이터의 양이 늘어나도 선형적으로 시간이 증가합니다.
- 공간 복잡도: $O(1)$. 추가적인 배열을 생성하지 않고 변수 몇 개만 사용하므로 메모리 사용량이 매우 적습니다.
<hr>