[기초]분할 정복

음.. 재귀와 함께 알고리즘에서 자주 보이는 분할 정복에 대해서

대충 써보면..

기본적인 컨셉은 큰 하나의 것을 작은 여러개로 분리해서 작은 것들을 전부 끝내고 그것을 합해서 하나로 만드는 것을 말하는 것이다.

이렇게 써 놓으면 뭐 씨뷁하는 생각밖에 들지 않을테고, 알고리즘 책에서도 자주 예를 드는 병합정렬을 예로 들어보면,(여기서는 간단하게 보여주기만 할 것이고, 알고리즘 폴더에 정확한 것을 써 놓을 것이다)

XXXXXXXXXXX 라는 배열을 정렬한다고 했을 때

1.XXXXX 2.XXXXXX 둘로 나누고

1.XX 2.XXX 1.XXX 2.XXX 둘로 나눈 것을 다시 둘로 나누고

1.X 2.X 1.X 2.XX 1.X 2.XX 1.X 2.XX 다시 둘로 나눠서

X X X X X X X X X X X 이렇게 각자 하나가 될 때까지 나누면 하나

의 원소는 정렬된 것이므로 이것들을 합하면서 정렬시키는 것이다.

그래서 저렇게 나눠진 것을 합해서 정렬된 배열이 나타나는데,

이런 식으로 큰 부분을 작게 나누고 작게 나눠진 부분에서 계산이나 실행을 끝내고 합하는 것을 분할 정복이라고 한다.

뭐 잘 이해가 안가는 설명이었는지도 모르겠지만, 나의 설명의 한계는 이정도이므로 여기서 끝낸다..