분할 정복

 분할 정복은 해결할 문제를 여러 개의 작은 부분으로 나눈 뒤, 나뉜 작은 문제들을 각각 해결한다. 

 

그 이후 해결된 해답을 모은다(필요하다면).

 

 분할 정복은 일반적으로 top-down 접근 방식을 사용한다. 일반적으로 top-down방식은 재귀 호출을 통해 분할해서 

 

문제를 해결한다. 큰 문제가 작은 문제로 나눌 수 있다면 재귀를 계속해서 호출해서 더 이상 나눌 수 없는 작은 문제가

 

되었을 때, 문제를 해결하고 필요에 따라 해결한 작은 문제들을 다시 합치게 된다.

 

 여기서 중요한 것은 나누어진 문제들이 서로 상관관계가 없어야 한다는 것이다. 즉, 나뉜 문제들이 서로의 풀이 과정에서 

 

서로에 영향을 미치지 않아야 한다. 만약 나뉜 문제들이 서로에 영향을 끼친다면 각각의 해답이나 풀이 과정이 달라질 수 

 

있기 때문이다. 나뉜 작은 문제들이 서로에 영향을 미치는 경우는 

 

다이내믹 프로그래밍(Dynamic Programming,DP)를 들 수 있다. 

 

 

 

 

 분할 정복의 대표적인 예로는 이진 검색, 병합 정렬, 퀵 정렬 등이 있다. 

 

처음의 큰 문제를 일정한 기준에 맞춰 나눈 다음 그 안에서 또 필요에 따라 나누거나 찾으려는 값을 검색, 또는 정렬하는 

 

것이다. 

 

 

 

 분할 정복에서 가장 많이 쓰이는 재귀적 호출을 바탕으로 간단하게 요약하자면 다음과 같다.

 

분할 정복은

 

- 문제를 나누고 각 문제를 해결하는 과정에서, 큰 문제와 작은 문제가 구조적으로 비슷해야 재귀적 호출에 수월하다. 

 

즉, 문제를 나눌 때 큰 문제와 비슷한 형태를 가진 모습으로 나누어 생각하는 것이다.

 

예를 들어 2^8이라는 숫자를 나누어 정복하자고 생각해 봤을 때, 

 

재귀적 호출로 주어진 값이 2의 배수라면 이를 2로 나누어 각각 다시 호출하는 방식을 들 수 있다.

 

이 경우 기존의 큰 문제는 2^8이지만 나누어진 두 개의 작은 문제는 각각 2^7이 된다. 

 

둘 다 2의 배수인 모양이 비슷하다. 이렇다면 재귀 함수 내에서 반복적으로 호출하면서 해결하기 수월해진다.

 

큰 문제에서 작은 문제들로 내려갈 때까지 동일한 재귀 함수를 호출하는 것으로 문제를 해결해 나갈 수 있는 

 

문제의 형태를 이루는 것이 중요하다.

 

- 나누어 진 문제들이 서로 영향을 미치지 않아야 한다.

 

병합 정렬을 예로 든다면, 굉장히 작아진 문제들을 다시 합치는 과정에 있어서,

 

왼쪽 배열을 정렬하는데 오른쪽 배열이 영향을 끼친다고 생각해보자.

 

왼쪽 배열을 정렬하는데 오른쪽 배열의 값을 필요로 하거나 비교 연산을 하게 된다면,

 

재귀적 호출을 실행할 때마다 필요한 값을 참조하기 위해 나눌 때마다 해당 값을 찾기 위해

 

값의 위치를 파악해야 하고, 또 엉뚱하게 정렬될 수도 있다. 

 

따라서 분할 정복의 경우에는 서로가 서로에게 영향을 미치지 않게 나누어 진 문제들을

 

정복하는 방법이라고 생각하면 된다.

 

 

 

 

 

라고 이해했다.