분할정복
주어진 2개 이상의 부분으로 문제를 나눈 뒤, 각 부분 문제에 대한 답을 재귀적으로 호출하여 계산하고, 답으로부터 전체 문제의 답을 계산해내는 알고리즘이다.
쉽게 말해, 큰 문제를 작은 문제로 분할하여 문제를 해결하는 방법
지금하는 분할정복은 단순히 문제를 분할한 뒤에 최대값만 찾는것이지, 다시 정렬하는 병합과정을 수행하는 것이 아니다!!
분할 -> 정복 -> 통합의 과정은 이 다음 장인 병합정렬에서 한다
-
분할(Divide) : 주어진 문제를 두 개 혹은 그 이상의 형식으로 나눈다
-
정복(Conquer) : 나누어진 문제를 재귀적으로 해결해서 나누어진 문제를 더 이상 나누어서 문제가 필요없을 때까지 계속 분할한다
-
통합(Combine) : 나누어서 해결한 문제들을 통합해서 원래 문제의 해답을 생성한다
- 배열을 사용 할 경우, 배열의 크기가 1이 될때까지 분할한다
-> 재귀함수를 사용하기 때문에 이 조건은 재귀를 탈출하는 조건이 된다
-> left == right 의 조건은 서로 같은 곳을 가리키고 있다는 것 (크기가 1)
-> 재귀를 탈출하는 조건이 가장 위에 있어야한다 !!
-> return 한 값은 해당 배열의 값
- 배열을 계속 반으로 나누어 왼쪽재귀와 오른쪽재귀로 분할할 것 이다
-> 왼쪽재귀와 오른쪽재귀를 실행하기 위해선 가운데 값을 알아야한다
-> middle값은 (left + right) / 2
-> middle 값도 재귀가 실행될때마다 계속 값이 갱신되어 새로운 값이 된다
-
재귀를 계속 실행하다가 배열의 크기가 1이 된 경우에는 (left == right) 재귀함수를 종료하고 해당 값을 반환한다
-> 해당 값을 반환하기 전에 최대값을 반환해야하는데, 배열의 크기가 1이고, 하나의 원소만 들어있기에 그 자체로 최대값인 것 이다 (그대로 반환해서 올라감)
-> 올라간 뒤 바로 maxLeft maxRight 비교
-> 이 코드에서는 20과 99가 반환된다
-
맨 아래의 재귀함수가 끝난 뒤 반환되어 위의 재귀함수로 들어온다.
위의 재귀함수들도 아직 코드를 끝마치지 못했으니 로직을 마저 수행해야 한다
값을 비교하여 반환
전체코드
#include <iostream>
#define SIZE 4
using namespace std;
int Find(int list[], int left, int right)
{
// 탈출할 수 있는 코드가 먼저 와야한다
if (left == right)
{
return list[left];
}
else
{
int middle = (left + right) / 2;
int maxLeft = Find(list, left, middle);
int maxRight = Find(list, middle + 1, right);
if (maxLeft < maxRight)
{
return maxRight;
}
else
{
return maxLeft;
}
}
}
// 분할 정복
int main()
{
#pragma region 분할 정복
int list[SIZE] = { 20, 15 , 99, 1 };
cout << "list의 최대값 : " << Find(list, 0, SIZE - 1) << endl;
#pragma endregion
return 0;
}
출력값:
분할정복 시간복잡도
- 병합정렬을 배우기 전인 분할정복 단계에서 최대값을 구하는 과정을 거쳤는데
이 과정에서 시간복잡도는 O(N)이다
-> 1. 실제로 분할되는 과정은 반씩 계속 쪼개진다
-> 하지만, logN깊이인것 이지 실제로 반만 남는 것은 아님!!!
-> 2. 분할되고 난 뒤 각 배열의 원소끼리 비교 연산을 수행하여 최대값을 return하여 이전 재귀함수로 돌려보낸다
-> 3. 실제 각 부분의 배열에서 반환된 최대값을 비교하는 연산은 O(1)이 걸리지만, 그 부분 배열 안에서 최대값을 찾는 과정이 결국 전체 배열을 다 비교하는 것이기때문에 O(N)이 걸리게 된다
결과적으로 깊이logN, 비교N이며, 빅오 표기법으로 O(N)이 된다
분할정복의 기초가 이진탐색인데 이진탐색의 시간복잡도는 logN이다
-> 이진탐색은 탐색범위를 반으로 줄이는 과정 (분할:logN)이고, 탐색범위를 반으로 줄인만큼 연산범위도 반으로 줄어든 것. 그래서 (연산:logN)
분할정복 다시해보기
- 재귀를 쓸때, 꼭 재귀함수를 종료할 수 있는 코드를 가장 위에 적어야한다
- 재귀함수를 쓰는 부분에 while문으로 조건 썼었는데 할 필요없는 짓
// 분할정복
int Find(int list[], int left, int right)
{
int middle = (left + right) / 2;
// 재귀 탈출
if (left == right)
{
return list[left];
}
int maxLeft = Find(list, left, middle);
int maxRight = Find(list, middle + 1, right);
if (maxLeft > maxRight)
{
return maxLeft;
}
else
{
return maxRight;
}
}
int main()
{
int list[SIZE] = { 1,10,99,5,23,42,11,33 };
cout << "최대값 : " << Find(list, 0, SIZE - 1) << endl;
return 0;
} 분할정복 후기
분할정복의 예시로 최대값을 찾는 방법을 구현했는데, 시간복잡도가 O(N)이 걸렸다
근데 최대값을 찾는방법은 선형탐색법으로도 시간복잡도가 O(N)이 걸리기 때문에, 굳이 분할정복으로 찾을 필요는 없어보인다
분할 정복법과, 선형 탐색법은 시간복잡도는 O(N)으로 서로 같지만, 접근 방식이 다르다
- 선형 탐색법은 배열을 한 번 순차적으로 탐색하면서 최대값을 찾는다
- 분할 정복법은 배열을 재귀적으로 분할 하고, 병합하면서 최대값을 찾는다
