이진 탐색과 분할 정복이란?
이진 탐색(Binary Search)은 실행 시간 복잡도가 O(log n)으로 매우 빠른 탐색 알고리즘입니다. 이 알고리즘은 분할 정복(Divide and Conquer) 원리를 기반으로 동작하며, 정상적으로 작동하려면 탐색 대상 데이터가 반드시 정렬된 상태여야 합니다.
이진 탐색은 컬렉션의 가운데 요소와 찾고자 하는 값을 비교하는 방식으로 특정 항목을 찾습니다. 두 값이 일치하면 해당 요소의 인덱스를 반환하고, 가운데 요소가 찾는 값보다 크면 왼쪽 하위 배열에서, 그렇지 않으면 오른쪽 하위 배열에서 탐색을 이어갑니다. 이 과정은 하위 배열의 크기가 0이 될 때까지 반복됩니다.
이번 글에서는 이러한 분할 정복(이진 탐색) 접근 방식을 응용하여, 배열에서 연속된 구간의 합이 가장 큰 값을 의미하는 최대 하위 배열 합(Maximum Subarray Sum)을 구하는 C++ 프로그램을 살펴보겠습니다.
알고리즘
시작
두 정수 중 최댓값을 구하는 정수형 함수 maximum()을 선언한다.
val1, val2를 정수형으로 선언하고 매개변수로 전달한다.
val1과 val2 중 더 큰 값을 확인한 뒤 그 값을 반환한다.
종료
시작
하위 배열의 중간 지점을 포함하는 최대 합 구간을 찾는 정수형 함수 MCS()를 선언한다.
배열 array[]와 변수 l, m, h를 정수형으로 선언하고 매개변수로 전달한다.
변수 s, sum_of_left_part를 정수형으로 선언하고 각각 0과 -1로 초기화한다.
for (int i = m; i >= l; i--) // 왼쪽 부분 순회
s = s + array[i]
if (s > sum_of_left_part)
sum_of_left_part = s
변수 sum_of_right_part를 정수형으로 선언하고 -1로 초기화한다.
for (int i = m+1; i <= h; i++) // 오른쪽 부분 순회
s = s + array[i]
if (s > sum_of_right_part)
sum_of_right_part = s
sum_of_left_part + sum_of_right_part를 반환한다.
종료
시작
최대 하위 배열 합을 구하는 정수형 함수 MaximumSum_of_SubArray()를 선언한다.
배열 array[]와 변수 l, h를 정수형으로 선언하고 매개변수로 전달한다.
변수 m을 정수형으로 선언한다.
if (l == h) // 원소가 하나뿐인 경우
return array[l]
m = (l + h) / 2 // 중간 지점 계산
return maximum(
maximum(MaximumSum_of_SubArray(array, l, m),
MaximumSum_of_SubArray(array, m+1, h)),
MCS(array, l, m, h))
종료
시작 (main)
변수 number_of_elements, i를 정수형으로 선언한다.
"배열의 원소 개수를 입력하세요: "를 출력하고 값을 입력받는다.
정수형 배열 a[number_of_elements]를 선언한다.
for (i = 0; i < number_of_elements; i++)
"원소를 입력하세요"를 출력하고 배열의 원소를 입력받는다.
"하위 배열의 최대 합은: "와 함께
MaximumSum_of_SubArray(a, 0, n-1)의 결과를 출력한다.
종료.C++ 예제 코드
#include<iostream>
using namespace std;
// 두 정수 중 최댓값을 반환하는 함수
int maximum(int val1, int val2) {
return (val1 > val2)? val1 : val2;
}
// 하위 배열의 중간 지점(m)을 반드시 포함하는 최대 합 구간을 찾는 함수
int MCS(int array[], int l, int m, int h) {
int s = 0;
int sum_of_left_part = -1;
// 왼쪽 부분의 최대 누적 합 계산
for (int i = m; i >= l; i--) {
s = s + array[i];
if (s > sum_of_left_part)
sum_of_left_part = s;
}
s = 0;
int sum_of_right_part = -1;
// 오른쪽 부분의 최대 누적 합 계산
for (int i = m+1; i <= h; i++) {
s = s + array[i];
if (s > sum_of_right_part)
sum_of_right_part = s;
}
// 중간 지점 기준 왼쪽 합과 오른쪽 합을 더해 반환
return sum_of_left_part + sum_of_right_part;
}
// 분할 정복으로 전체 배열의 최대 하위 배열 합을 구하는 함수
int MaximumSum_of_SubArray(int array[], int l, int h) {
int m;
// 원소가 하나뿐이면 그 값 자체가 최대 합
if (l == h)
return array[l];
m = (l + h) / 2;
// 왼쪽 절반, 오른쪽 절반, 중간을 가로지르는 경우 중 최댓값 반환
return maximum(maximum(MaximumSum_of_SubArray(array, l, m),
MaximumSum_of_SubArray(array, m+1, h)),
MCS(array, l, m, h));
}
int main() {
int number_of_elements, i;
cout<<"배열의 원소 개수를 입력하세요: ";
cin>> number_of_elements;
cout<<endl;
int a[number_of_elements];
for(i = 0; i < number_of_elements; i++) {
cout<<"원소 "<<i+1<<" 입력: ";
cin>>a[i];
}
// 최대 하위 배열 합 출력
cout<<"\n하위 배열의 최대 합: "<<MaximumSum_of_SubArray(a, 0, number_of_elements - 1);
return 0;
}실행 결과
배열의 원소 개수를 입력하세요: 5 원소 1 입력: 12 원소 2 입력: 45 원소 3 입력: 56 원소 4 입력: 48 원소 5 입력: 75 하위 배열의 최대 합: 236
코드 동작 원리
이 프로그램은 다음 세 가지 경우를 재귀적으로 비교하는 방식으로 동작합니다.
- 왼쪽 절반(l ~ m): 왼쪽 하위 배열의 최대 하위 배열 합을 재귀적으로 구합니다.
- 오른쪽 절반(m+1 ~ h): 오른쪽 하위 배열의 최대 하위 배열 합을 재귀적으로 구합니다.
- 중간을 가로지르는 경우: MCS() 함수가 중간 지점(m)을 반드시 포함하면서 좌우로 뻗어 나가는 최대 합을 계산합니다.
세 값 중 가장 큰 값이 해당 구간의 정답이 되며, 이 과정을 배열의 크기가 1이 될 때까지 재귀적으로 반복하면 전체 배열의 최대 하위 배열 합을 얻을 수 있습니다. 예제 실행에서는 모든 원소가 양수이므로 배열 전체의 합인 236(12+45+56+48+75)이 결과로 출력됩니다.
시간 복잡도
이 알고리즘의 점화식은 T(n) = 2T(n/2) + Θ(n)이며, 마스터 정리(Master Theorem)에 따라 전체 시간 복잡도는 O(n log n)입니다. 참고로 카데인(Kadane) 알고리즘을 사용하면 O(n)의 시간 복잡도로 동일한 문제를 더 효율적으로 해결할 수 있습니다.
참고 사항
예제 코드의 int a[number_of_elements]는 가변 길이 배열(VLA)로, 표준 C++ 규격에는 포함되지 않는 GCC 확장 기능입니다. 코드의 이식성을 높이려면 std::vector<int> a(number_of_elements);처럼 std::vector를 사용하는 것이 좋습니다.