Divide and Conquer 알고리즘

분할정복

• 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다.
• 분할정복은 시간복잡도를 어마어마하게 줄여줄 수 있다.
• 대표적으로 탐색알고리즘의 이진탐색이 있다.

값을 찾기 위해 왼쪽에서 오른쪽 끝까지 이동하기보다는,
작은 조각으로 세분하여 각 조각들을 어디로 이동시킬지 결정하는 작업

search.js

• 내 풀이

/*
	문제 - Divide and conquer (1)
	Given a sorted array of integers, write a function
	called search, that accepts a value and returns the
	index where the value passed to the function is
	located. If the value is not found, return -1.
*/

function search(arr, n) {
    let end = arr.length - 1;
    let start = 0;
    let mid;
    while (start <= end) {
        mid = Math.floor((start + end) / 2);
        if (n === arr[mid]) {
            return mid;
        } else if (n > arr[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

console.log(search([1, 2, 3, 4, 5, 6], 4)); // 3
console.log(search([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(search([1, 2, 3, 4, 5, 6], 11)); // -1
console.log(search([1, 3, 4, 5, 7, 8, 9, 10, 11], 11)); // 8
console.log(search([1, 3, 4, 5, 7, 8, 9, 10, 11], 1)); // 0

설명

• 이진탐색을 풀었던 최대한 되살려서 풀어봤다.
• 처음에 배열의 시작값, 끝값을 변수에 담아놨다.
• mid를 start + end / 2 하고 내림하여 자연수로 만들었다.
• 3갈래로 분기처리하여 start, end 값을 이동시켜주었다.

시간복잡도

• O(log(N))
• 2개씩 계속 쪼개면서 찾으니까 밑이 2인 log(N)의 시간 복잡도를 가진다.

생활에서 만나는 분할정복

술자리에서 소주뚜껑 숫자 맞추기할 때, 이진탐색을 통해 효율적으로 숫자에 접근할 수 있다.