[알고리즘][JS] 분할과 정복 알고리즘

분할과 정복?

분할과 정복 알고리즘이란, 엄청나게 큰 문제를 나누어서 해결한 뒤,
합쳐서 문제를 해결한다는 뜻에서 분할과 정복 알고리즘이라고 불립니다.
대표적으로는 퀵정렬,병합정렬이 있습니다.

• 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눕니다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복합니다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합합니다.

분할과 정복 알고리즘의 장점?

문제를 나누어 풀어가며 어려운 문제를 쉽게 해결 할 수 있다(효율적으로)는 장점이 있습니다.
그리고, 재귀적인 방법을 사용하기 때문에 알고리즘의 구현이 간결하고 이해하기 쉽습니다.
'병렬적'으로 문제를 풀이하는 강력한 알고리즘중 하나입니다.

분할과 정복 알고리즘의 단점?

함수를 재귀적으로 호출하기 때문에, 오버헤드가 발생하기 쉽습니다.
스택에 다양한 데이터를 보관하기 때문에, 스택에 과부하가 걸리는 스택오버플로우현상이 일어날 수 있습니다.
어떤 문제에는 다른 알고리즘보다 효율적이지만, 다른 문제에는 그렇지 않을 수 있습니다.
모든 문제에 대해 일관된 성능을 보장하지는 않는다는 뜻입니다.

예시

search([1,2,3,4,5,6],4)
search([1,2,3,4,5,6],6)
search([1,2,3,4,5,6],11)

이런식으로 호출 하지만 사실상 이진 탐색이라고 불립니다.
이는 정렬되 숫자를 지닌 배열을 취합니다.

search 함수는 이진탐색을 기반으로 작성된 함수이며,
search 함수는 2번째 인자로 받아온 값의 index를 return합니다.
만약 배열의 length보다 긴 숫자가 2번째 인자로 들어온다면 -1을 return 합니다.

해결법

function search(arr,val){
    for(let i = 0; i < arr.length; i++){
        return i
    }
      return -1
}

이 구조는 선형탐색이며 O(n)의 복잡도를 가집니다.

이진 탐색으로 해결하기