[Algorithm] 알고리즘 기본 패턴 4 - Devide & Conquer

 

4. Devide & Conquer

 

여기서는 간략하게 개념만 설명하고 넘어가겠습니다.

분할 정복 알고리즘의 예시로는 이진 탐색 트리 
그리고 정렬 알고리즘으로 넘어가면 퀵 정렬과 병합 정렬이 대표적인 예가 될 수 있습니다.


이 알고리즘은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리하며,
링크드 리스트나 트리가 대상이 될 수도 있습니다.

 

이진 탐색 트리 를 보면 선형탐색으로 O(n) 의 시간을 들여 찾는 것 보다

절반으로 나누어 찾아가면 O(log n) 로 훨씬 더 효율적으로 찾는 것을 알 수 있습니다.

 

이렇게 몇몇 케이스에서 분할 정복  패턴을 사용하면 더 효율적인 결과를 얻을 수 있습니다.

 

function search(array, val) {
 
    let min = 0;
    let max = array.length - 1;
 
    while (min <= max) {
        let middle = Math.floor((min + max) / 2);
        let currentElement = array[middle];
 
        if (array[middle] < val) {
            min = middle + 1;
        }
        else if (array[middle] > val) {
            max = middle - 1;
        }
        else {
            return middle;
        }
    }
 
    return -1;
}

 

 

지난 관련글

 

1. Frequency Counter (빈도수 세기)

https://daunje0.tistory.com/190

[Algorithm] 알고리즘 기본 패턴 1 - Frequency Counter (빈도수 세기)

 

 

2. Multiple Pointers (다중 포인터)

https://daunje0.tistory.com/191

[Algorithm] 알고리즘 기본 패턴 2 - Multiple Pointers (다중 포인터)

 

3. Sliding Window

https://daunje0.tistory.com/262

[Algorithm] 알고리즘 기본 패턴 3 - Sliding Window