서론
어제는 분할과 정복의 개념에 대해서 공부했다. 분할과 정복은 여러 알고리즘의 기본이 되는 접근법인데, 어제는 탐색로직에 분할과 정복을 도입하며 원리에 대해서 이해하는 시간을 가졌다. 오늘은 그걸 코드로 구현하려고 한다.
본론
문제
정렬된 숫자 배열과 값을 받고, 값과 일치하는 배열의 인덱스를 반환하는 search를 작성하시오.
search([1,2,3,4,5,6],4)//3 search([1,2,3,4,5,6],6)//5 search([1,2,3,4,5,6],11)//-1 ``
Navie한 해결책
이 문제를 해결할 수 있는 다양한 해결책들이 모두 머리에 떠 올랐을 것이다. 나는 이 문제를 보고 indexOf를 사용해 간결하게 풀이하는 방법을 떠올랐다. 다음과 같이 말이다!
function search(arr, val){
if(arr === null || arr.length<=0) return '빈 배열'
return arr.indexOf(val);
}이렇게 하면 O(n)의 시간복잡도의 코드가 구현이 되었다. 또 다른 방법으로는 indexOf가 아닌 for루프만을 이용해서 해결하는 방법이 있을것이다. 코드의 길이나 모습은 다르지만 둘의 원리는 똑같다. 배열의 왼쪽에서 오른쪽으로 하나하나 차근차근 비교하는 것이다.
function search(arr, val){
if(arr === null || arr.length<=0) return '빈 배열'
for(let i = 0 ; i<arr.length; i++){
if(arr[i] === val){
return i;
}
}
return -1;
}Refactory
위의 코드들을 분할과 정복의 원리를 이용해서 리팩토링 하면 다음과 같다.
function search(arr, val){
if(arr === null || arr.length<=0) return '빈 배열'
let min = 0;
let max = arr.length - 1;
while(main<=max){
//배열의 중간의 인덱스를 구함
let middle = Math.floor((min+max) / 2);
let currentElement = arr[middle];
if(currentElement < val){
//배열의 중간값이 val보다 작을때
//중간 값 이하의 데이터는 무시.
min = middle + 1
}else if(currentElement > val){
//배열의 중간값이 val보다 클 때
//중간 값 이상의 데이터는 무시.
max = middel-1;
}else{
//일치하는 경우
return middle;
}
}
return -1;
}이렇게 하면 Log(N)의 시간복잡도의 코드가 구현이 된다. 위의 코드들 처럼 처음부터 데이터를 하나하나 비교하지 않기 때문이다. 짧은 데이터라면 크게 차이가 나지 않더라도 큰 데이터가 되면 이 차이는 무시하지 못할 정도로 커진다.
나이브한 해결책이라고 하더라도 무조건 나쁜것은 아니다. 정렬되어있지 않은 배열이라면 for루프나 indexOf를 이용하는게 더 나을 수도 있다는 생각이 든다. 왜냐면 정렬되어있지 않다면 배열을 정렬하는 과정을 한 번 더 거쳐야 할 것이기 때문이다. 여러 방법을 시기적절하게 사용하는것이 중요한거 같다.
참고
https://www.udemy.com/course/best-javascript-data-structures/learn/lecture/28559793#search
