2026-02-03 | 8 min read | 144 | 코딩 테스트 알고리즘 분할 정복 슬라이딩 윈도우

8-9. 코딩 테스트: 문제 해결 패턴 (분할 정복, 슬라이딩 윈도우)

1. 분할 정복 (Divide and Conquer)

분할 정복은 문제를 더 작은 하위 문제로 나누어 해결하고, 하위 문제의 해를 결합하여 원래 문제의 해를 구하는 알고리즘 설계 패러다임입니다. 마치 거대한 퍼즐을 맞추기 위해 더 작은 조각으로 나누어 해결하는 것과 같습니다. 이 전략은 문제의 크기를 줄여 복잡도를 낮추는 데 효과적이며, 많은 알고리즘의 핵심 원리로 사용됩니다.

1) 개념 및 배경

분할 정복은 세 단계로 이루어집니다.

분할(Divide): 문제를 하나 이상의 하위 문제로 분할합니다. 하위 문제는 원래 문제와 동일한 유형이어야 하지만, 크기가 작아야 합니다.
정복(Conquer): 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작아지면, 직접 해결할 수 있는 기반(base case)에 도달합니다.
결합(Combine): 하위 문제의 해를 결합하여 원래 문제의 해를 구합니다.

분할 정복은 재귀적인 특성을 가지며, 문제의 크기를 기하급수적으로 줄여 시간 복잡도를 개선하는 데 기여합니다.

2) 핵심 원리

분할 정복의 효율성은 하위 문제로의 분할, 하위 문제의 해결, 그리고 해의 결합 단계에서 결정됩니다. 각 단계의 효율성이 전체 알고리즘의 성능에 영향을 미칩니다.

분할: 문제의 균형 잡힌 분할이 중요합니다. 불균형한 분할은 한쪽 하위 문제의 크기가 너무 커져 전체 성능을 저하시킬 수 있습니다.
정복: 하위 문제를 해결하는 데 걸리는 시간도 중요하지만, 충분히 작은 크기까지 분할하는 것이 핵심입니다.
결합: 하위 문제의 해를 결합하는 과정은 문제에 따라 매우 다양합니다. 이 과정의 복잡도 역시 전체 알고리즘의 성능에 영향을 미칩니다.

분할 정복의 대표적인 예시로는 병합 정렬(Merge Sort)이 있습니다. 병합 정렬은 다음과 같이 작동합니다.

분할: 정렬할 배열을 두 개의 하위 배열로 나눕니다.
정복: 각 하위 배열을 재귀적으로 병합 정렬합니다. 하위 배열의 크기가 1이 되면 정렬된 것으로 간주합니다.
결합: 정렬된 두 개의 하위 배열을 병합하여 정렬된 하나의 배열을 만듭니다.

병합 정렬의 시간 복잡도는 $O(n \log n)$으로, 퀵 정렬과 더불어 효율적인 정렬 알고리즘으로 널리 사용됩니다.

병합 정렬 설명 뒤

3) 응용 및 활용 사례

분할 정복은 다양한 문제에 적용될 수 있습니다.

퀵 정렬(Quick Sort): 피벗(pivot)을 기준으로 배열을 분할하고, 각 분할된 부분을 재귀적으로 정렬합니다.
이진 탐색(Binary Search): 정렬된 배열에서 중간 값을 기준으로 탐색 범위를 반으로 줄여 원하는 값을 찾습니다.
행렬 곱셈(Matrix Multiplication): 슈트라센 알고리즘(Strassen's algorithm)과 같은 분할 정복 기반 알고리즘은 행렬 곱셈의 시간 복잡도를 개선합니다.
최대 부분 배열 문제(Maximum Subarray Problem): 배열의 최대 부분 배열 합을 구하는 데 분할 정복을 사용할 수 있습니다.

4) 주의사항과 트러블슈팅

분할 정복을 사용할 때는 다음과 같은 사항에 유의해야 합니다.

기저 조건(Base Case): 재귀 호출을 멈추는 기저 조건을 올바르게 설정해야 합니다. 기저 조건이 없으면 무한 재귀에 빠질 수 있습니다.
분할의 균형: 분할 과정에서 하위 문제의 크기가 균형을 이루도록 해야 합니다. 불균형한 분할은 알고리즘의 성능을 저하시킬 수 있습니다.
결합의 효율성: 하위 문제의 해를 결합하는 과정이 효율적이어야 합니다. 결합 과정이 복잡하면 전체 알고리즘의 시간 복잡도가 증가할 수 있습니다.
메모리 사용: 재귀 호출은 스택 메모리를 사용하므로, 깊은 재귀 호출은 스택 오버플로우를 발생시킬 수 있습니다.

2. 슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우는 연속적인 데이터의 부분 집합을 처리하는 데 사용되는 알고리즘 기법입니다. "윈도우"는 데이터의 특정 구간을 의미하며, 이 윈도우를 데이터 위에서 이동시키면서 문제를 해결합니다.

1) 개념 및 배경

슬라이딩 윈도우는 주로 배열, 문자열, 또는 리스트와 같은 선형 자료구조에서 사용됩니다. 윈도우의 크기는 고정되거나 가변적일 수 있으며, 문제의 요구 사항에 따라 결정됩니다. 윈도우를 이동시키는 과정은 일반적으로 윈도우의 시작점과 끝점을 조정하는 방식으로 이루어집니다.

슬라이딩 윈도우는 중복 계산을 피하고 시간 복잡도를 개선하는 데 효과적입니다. 예를 들어, 윈도우 내의 합을 계산하는 경우, 윈도우를 한 칸 이동할 때 이전 합을 재사용하여 새로운 합을 계산할 수 있습니다.

2) 핵심 원리

슬라이딩 윈도우의 핵심은 윈도우의 시작점과 끝점을 효율적으로 조정하는 것입니다. 윈도우의 크기가 고정된 경우, 시작점과 끝점을 동시에 이동시키면서 문제를 해결합니다. 윈도우의 크기가 가변적인 경우, 윈도우를 확장하거나 축소하는 로직이 필요합니다.

슬라이딩 윈도우 알고리즘의 일반적인 단계는 다음과 같습니다.

초기화: 윈도우의 시작점과 끝점을 초기화하고, 필요한 변수(예: 윈도우 내의 합, 최대 길이 등)를 초기화합니다.
확장: 윈도우의 끝점을 이동하여 윈도우를 확장합니다. 윈도우 내의 조건을 확인하고, 필요에 따라 변수를 업데이트합니다.
축소(선택 사항): 윈도우 내의 조건이 충족되지 않으면, 윈도우의 시작점을 이동하여 윈도우를 축소합니다.
반복: 윈도우를 이동하고, 윈도우 내의 조건을 확인하는 과정을 반복합니다.
결과: 문제의 요구 사항에 따라 결과를 반환합니다.

슬라이딩 윈도우의 효율성은 윈도우의 이동과 조건 확인 과정의 복잡도에 따라 결정됩니다.

슬라이딩 윈도우 알고리즘 설명 뒤

3) 응용 및 활용 사례

슬라이딩 윈도우는 다양한 문제에 적용될 수 있습니다.

최대/최소 합 부분 배열: 주어진 배열에서 크기가 k인 부분 배열의 최대 합 또는 최소 합을 구합니다.
고정된 크기의 부분 문자열: 문자열에서 특정 문자를 포함하는, 고정된 크기의 부분 문자열을 찾습니다.
가변 크기의 부분 문자열: 문자열에서 특정 조건을 만족하는, 가변 크기의 부분 문자열을 찾습니다. (예: 중복 문자를 포함하지 않는 가장 긴 부분 문자열)
연속된 k개의 원소의 합: 배열에서 연속된 k개의 원소의 합이 특정 값과 같은 부분 배열을 찾습니다.
최대 빈도수: 주어진 배열에서 k번 이하로 바꿀 수 있을 때, 가장 긴 연속된 문자의 길이를 구합니다.

4) 주의사항과 트러블슈팅

슬라이딩 윈도우를 사용할 때는 다음과 같은 사항에 유의해야 합니다.

윈도우 크기: 윈도우의 크기가 고정된 경우, 시작점과 끝점을 올바르게 이동해야 합니다. 윈도우의 크기가 가변적인 경우, 윈도우를 확장하고 축소하는 로직을 정확하게 구현해야 합니다.
조건 확인: 윈도우 내의 조건을 올바르게 확인해야 합니다. 윈도우 내의 조건이 충족되지 않으면, 윈도우를 축소해야 합니다.
경계 조건: 윈도우의 시작점과 끝점이 배열의 범위를 벗어나지 않도록 경계 조건을 처리해야 합니다.
효율성: 슬라이딩 윈도우의 효율성은 윈도우의 이동과 조건 확인 과정의 복잡도에 따라 결정됩니다. 효율적인 알고리즘을 설계하기 위해 노력해야 합니다.
자료구조 선택: 문제의 특성에 따라 윈도우 내의 데이터를 효율적으로 관리할 수 있는 자료구조를 선택해야 합니다. 예를 들어, 윈도우 내의 합을 계산하는 경우, 이전 합을 재사용하는 방식을 고려할 수 있습니다.

3. 분할 정복과 슬라이딩 윈도우의 비교

분할 정복과 슬라이딩 윈도우는 모두 문제 해결을 위한 효과적인 기법이지만, 적용되는 문제 유형과 해결 방식에 차이가 있습니다.

특징	분할 정복	슬라이딩 윈도우
목적	문제를 작은 하위 문제로 나누어 해결.	연속적인 데이터의 부분 집합을 효율적으로 처리.
자료 구조	재귀적 구조, 배열, 트리 등 다양한 자료 구조.	주로 배열, 문자열, 리스트와 같은 선형 자료 구조.
접근 방식	문제를 재귀적으로 분할하고, 하위 문제의 해를 결합.	윈도우를 이동시키면서 윈도우 내의 데이터를 처리.
시간 복잡도	$O(n \log n)$, $O(n^2)$, $O(n^3)$ 등 문제에 따라 다름.	$O(n)$, $O(n \log n)$ (윈도우 이동과 조건 확인에 따라 달라짐).
주요 활용	정렬, 탐색, 행렬 곱셈, 최대 부분 배열 문제 등.	최대/최소 합 부분 배열, 고정/가변 크기의 부분 문자열, 연속된 k개의 원소의 합 등.

분할 정복은 문제를 재귀적으로 분할하여 해결하는 방식이며, 슬라이딩 윈도우는 연속적인 데이터의 부분 집합을 처리하는 데 특화된 기법입니다. 두 기법은 문제의 특성과 요구 사항에 따라 적절하게 선택하여 사용하거나, 필요에 따라 함께 활용할 수도 있습니다. 예를 들어, 슬라이딩 윈도우를 사용하여 배열의 부분 집합을 처리하고, 각 부분 집합에 분할 정복을 적용하는 방식으로 문제를 해결할 수도 있습니다.

4. 실전 문제 해결 전략

코딩 테스트에서 분할 정복과 슬라이딩 윈도우 기법을 효과적으로 활용하기 위한 몇 가지 전략을 제시합니다.

1) 문제 분석

문제 유형 파악: 문제에서 요구하는 사항이 분할 정복 또는 슬라이딩 윈도우 기법을 적용할 수 있는 유형인지 판단합니다. 예를 들어, 정렬, 탐색, 부분 배열, 부분 문자열 관련 문제인 경우 해당 기법을 고려할 수 있습니다.
입력 데이터 분석: 입력 데이터의 크기, 형태, 제약 조건을 파악합니다. 특히, 데이터 크기가 큰 경우 시간 복잡도를 고려하여 효율적인 알고리즘을 선택해야 합니다.
문제 분해: 문제를 작은 하위 문제로 분해할 수 있는지, 또는 윈도우를 사용하여 문제를 해결할 수 있는지 분석합니다.

2) 알고리즘 설계

분할 정복:
- 기저 조건 설정: 재귀 호출을 멈추는 기저 조건을 명확하게 정의합니다.
- 분할 방법 결정: 문제를 어떻게 하위 문제로 분할할지 결정합니다. 균형 잡힌 분할을 통해 성능을 최적화합니다.
- 결합 방법 구현: 하위 문제의 해를 어떻게 결합하여 원래 문제의 해를 구할지 구현합니다.
슬라이딩 윈도우:
- 윈도우 크기 결정: 윈도우의 크기가 고정인지, 가변인지 결정합니다.
- 윈도우 이동 로직 설계: 윈도우의 시작점과 끝점을 어떻게 이동시킬지 결정합니다.
- 조건 확인 로직 구현: 윈도우 내의 조건을 어떻게 확인할지 구현합니다.
시간 복잡도 분석: 설계한 알고리즘의 시간 복잡도를 분석하여 효율성을 확인합니다.

3) 코드 구현 및 디버깅

코드 작성: 설계한 알고리즘을 기반으로 코드를 작성합니다.
테스트 케이스 활용: 다양한 테스트 케이스를 사용하여 코드를 테스트합니다.
디버깅: 예상치 못한 오류가 발생하면 디버깅 도구를 사용하여 문제를 해결합니다.
예외 처리: 입력 데이터의 예외 상황을 처리합니다.

4) 실전 문제 예시

예시 1: 최대 부분 배열 문제 (분할 정복)

배열 nums가 주어졌을 때, 최대 부분 배열의 합을 구하는 문제입니다.

분할: 배열을 반으로 나눕니다.
정복: 각 하위 배열에서 최대 부분 배열의 합을 재귀적으로 구합니다.
결합:
- 왼쪽 하위 배열의 최대 부분 배열 합
- 오른쪽 하위 배열의 최대 부분 배열 합
- 중앙을 가로지르는 최대 부분 배열 합 (중앙에서 시작하여 왼쪽과 오른쪽으로 확장)
- 위 세 가지 중 가장 큰 값을 반환합니다.

최대 부분 배열 문제 설명 뒤

예시 2: 길이가 k인 부분 문자열의 최대 합 (슬라이딩 윈도우)

문자열 s와 정수 k가 주어졌을 때, s의 길이가 k인 부분 문자열의 최대 합을 구하는 문제입니다.

초기화: 윈도우의 시작점과 끝점을 초기화하고, 윈도우 내의 합을 계산합니다.
이동: 윈도우를 한 칸씩 오른쪽으로 이동합니다.
갱신: 윈도우에서 가장 왼쪽에 있는 문자를 빼고, 가장 오른쪽에 있는 문자를 더합니다. 윈도우 내의 합을 갱신합니다.
최댓값 갱신: 현재 윈도우의 합이 최대 합보다 크면, 최대 합을 갱신합니다.
반복: 위 과정을 반복합니다.

5. 결론

분할 정복과 슬라이딩 윈도우는 코딩 테스트에서 매우 유용한 문제 해결 기법입니다. 이 두 가지 기법을 이해하고, 다양한 문제에 적용하는 연습을 통해 코딩 테스트 실력을 향상시킬 수 있습니다. 문제 유형을 파악하고, 적절한 알고리즘을 선택하는 능력이 중요하며, 꾸준한 연습을 통해 문제 해결 능력을 향상시킬 수 있습니다.