서론
오늘 이야기 할 것은 Divide and Conquer(분할과 정복)이다. 분할과 정복은 보편적으로 많이 쓰이는 패턴으로 공식적인 알고리즘 패턴이다. 큌 정렬, 힙 정렬, 이진 탐색, 이진 탐색 트리 등등의 정렬과 탐색에 많이 사용되고 주로 배열이나 문자열의 큰 규모의 데이터셋을 처리하는데 많이 쓰인다고 한다. 과연 어떤 방식으로 동작하는지 간단하게 알아보려고 한다.
본론
분할과 정복은 말 그대로 큰 데이터를 작은 데이터들로 분할해서 처리하는 방식이다.
arr = [1, 2, 3, 4, 5, 6, 7, 11, 12, 17, 20, 21, 22, 24]배열 arr에서 숫자 20을 탐색하는 로직을 작성해야한다면 어떤 식으로 접근해야할까?
첫번째로, for루프를 이용해 접근하는 방법이있다.
배열의 처음부터 끝까지 왼쪽부터 오른쪽으로 하나하나 데이터를 비교하면서 맞는 숫자가 나올때까지 루프를 진행한다. 그럼 O(n)의 시간복잡도의 로직이 완성된다. 위의 배열은 짧은 편이어서 괜찮지만 데이터가 10만개가 넘어가는 큰 배열을 만나면 O(n)이라고 해도 오랜 시간이 걸릴 것이다.
두번째로, 위와 같이 순서대로 정렬된 데이터라면 분할과 정복을 이용해 접근하는 방법이 있다.
분할과 정복은 말 그대로 큰 데이터를 분할하고 정복하는 것이다! 위 배열의 중간은 7이 될 것이다. 우리가 찾고자 하는 숫자는 20이다. 배열은 정렬되어 있으니 우리는 7이상의 숫자만 보면 됨으로 그 이전은 완전히 배제 할 수 있다. 그러고서 남은 데이터의 중간을 선택한다. 20이 선택되었다. 이렇게 첫번째 접근법으로는 11번의 연산 후에 찾아 낼 수 있는 것을 이 방법으로 두 번 만에 찾아냈다. 분할과 정복을 이용하면 O(logN)의 시간복잡도가 소요된다. O(n)보다 훨씬 빠르고 효율적인 수치이다.
내일은 위의 예시를 코드를 구현하면서 분할과 정복을 한 번 더 복습할 예정이다.
참고
