👊🏻 문제 해결 패턴

알고리즘의 해결하기 어려운 문제에 어떻게 접근할까?

1. 우선 문제를 해결하기 위한 계획을 수립해 보자.
2. 일반적인 문제 해결 패턴을 습득하자

🌌 빈도수 세기 패턴

자바스크립트의 객체를 사용해 다양한 값과 빈도를 수집한다.

a Native solution.

시간복잡도 O(n^2)

function same(arr1, arr2){
	if(arr1.length !== arr2.length){ return false;}
    for(let i = 0; i < arr1.length; i++){
    	let correctIndex = arr2.indexOf(arr1[i] ** 2)
        if(correctIndex === -1){
        	return false;
            }
        arr2.splice(correctIndex, 1)
    }
    return true;
}

Refactored.

시간복잡도 O(n)

function same(arr1, arr2){
	if(arr1.length !== arr2.length){ return false;}
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}
    for(let val of arr1){
    	frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }
    for(let val of arr2){
    	frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
    }
    for(let key in frequencyCounter1){
    	if(!(key ** 2 in frequencyCounter2)){
        	return false;
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
        	return false
        }
    }
    return true;
}

🌌 다중 포인터 패턴

인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라
중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 패턴.
한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다는 개념.

a Native solution.

시간복잡도 O(n^2) 공간복잡도 O(1)

function sumZero(arr){
	for(let i = 0; i < arr.length; i++){
    	for(let j = i+1; j < arr.length; j++){
        	if(arr[i] + arr[j] === 0){
            	return [arr[i], arr[j]];
            }
        }
    }
}

Refactored.

시간복잡도 O(n) 공간복잡도 O(1)

function sumZero(arr){
	let left = 0;
    let right = arr.length -1;
    while(left < right){
    	let sum = arr[left] + arr[right];
        if(sum === 0){
        	return [arr[left], arr[right]];
        }else if(sum > 0){
        	right--;
        }else{
        	left++;
        }
    }
}

🌌 기준점 간 이동 배열 패턴 (Sliding window)

배열이나 문자열과 같은 일련의 데이터를 입력하거나
특정방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다.

a Native solution.

시간복잡도 O(n^2)

function maxSubarraySum(arr, num){
	if(num > arr.length) {
    	return null;
    }
    let max = -Infinity;
    for(let i = 0; i < arr.length - num + 1; i++){
    	temp = 0;
        for(let j = 0; j < num; j++){
        	temp += arr[i + j];
        }
        if(temp > max) {
    		max = temp;
    	}
    }
    return max;
}

Refactored.

시간복잡도 O(n)

function maxSubarraySum(arr, num){
	let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
    for (let i = 0; i < num; i++){
    	maxSum += arr[i];
    }
    tempSum = maxSum;
    for(let i = num; i < arr.length; i++){
    	tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(maxSum, tempSum);
    }
    return maxSum;
}

🌌 분할과 정복 패턴

배열이나 문자열 같은 큰 규모의 데이터셋을 처리.

a Native solution.

시간복잡도 O(N)

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

Refactored.

시간복잡도 Log(N)-Binary search

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;
}