분할정복 - 병합 정렬(merge sort)

재귀(recursive) 알고리즘에 대해 자주 접하게 될 것인데, 재귀 알고리즘은 주로 반복적(Iterative) 알고리즘과 비교되는 개념이다. (그렇다고 반대되는 개념이란 것은 아니다!)

이번에 소개할 분할 정복 알고리즘은 재귀 알고리즘에 해당된다. C언어 공부를 해보았다면, 재귀 함수는 '자기 자신을 계속 호출하는 함수'라는 것은 잘 알고 있을 것이다. https://www.acmicpc.net/problem/17478 -재귀 함수가 뭔가요?

정신나갈것같애!!정신나갈것같애!!

정신나갈것같애!! 그런 재귀함수중에서도 각각 구간을 쪼개서 자기 자신을 호출하는 놈들이 있다.

그게 바로 분할 정복이다. 분할 정복(Divide & Conquer) 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식 이름에서 바로 눈치챌 수 있는데, 해결해야 할 문제를 작고 쉬운 문제들로 분할(divide) 시키고 정복(conque...