문제 해결 패턴

유용하게 쓰일 수 있는 일반적인 패턴 몇가지를 학습하면 도움이 된다.

패턴은 코드를 작성하는 일반적인 접근법, 즉 원형

Frequency Counters

빈도 카운터라고 부르는데 꼭 이렇게만 불리지는 않음.

배열이나 객체의 값의 포함 유무나 빈도를 모을때 쓴다

중첩 반복문이나 O(n^2)를 피할 수 있어서 유용하다.

두 배열을 비교해서, 하나의 배열의 요소들을 각각 제곱한 값을 요소로 가지는 다른 배열이면 true,

그렇지 않으면 false를 리턴하는 함수를 만들어야 한다.

빈도 카운터를 쓰지 않은 ‘나이브’한 솔루션.

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;
        }
        console.log(arr2);
        arr2.splice(correctIndex,1)
    }
    return true;
}

same([1,2,3,2], [9,1,4,4])

for문 안에 indexOf가 들어있기 때문에 시간복잡도는 O(n^2) 이다.

indexOf의 기능은 중첩된 루프이다.

빈도카운터를 쓰면 이렇게 할 수 있다.

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        
    }
    console.log(frequencyCounter1);
    console.log(frequencyCounter2);
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

same([1,2,3,2,5], [9,1,4,4,11])

for문이 중첩되지 않고 여러개 나열되면 2n, 3n → 그래봐야 O(n)이다.

객체를 만들어 배열의 요소를 키, 빈도를 값으로 만들고 비교한다.

if(변수 in 객체) 로 쓸수 있는 것도 체크.

시간복잡도가 O(n^2) vs O(n)이다.

배열의 길이가 1000이라면 1,000,000 vs 3000 이 된다. 비교가 안될만큼 속도 차이가 난다.

Multiple pointer

다중 포인터. 오피셜한 이름은 아님.

인덱스나 위치에 해당하는 포인터 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것입니다.

‘오름차순으로 정렬된 배열을 받아서 합해서 0이 되는 쌍을 찾는 함수’

다중 포인터를 사용하지 않은 나이브한 솔루션.

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

sumZero([-4,-3,-2,-1,0,1,2,5])

이중 반복문을 사용한다. 시간복잡도는 O(n^2)

다중포인터를 사용한 코드

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]];  // 합이 0이면 반환
		} else if(sum > 0) {   // 합이 0보다 크면 뒤쪽 포인터를 앞으로 땡김.
				right--;
		} else {               // 합이 0보다 작으면 앞쪽 포인터를 뒤로 땡김.
				left++;
		}
	}
}

중첩 반복문을 사용하지 않았기 때문에 시간복잡도는 O(n)이다.

Sliding Window

슬라이딩 윈도우는 배열이나 문자열 같은 일련의 데이터를 입력하거나

특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다.

‘배열과 정수를 받아서 해당 정수 갯수만큼 인접하는 요소들의 합이 가장 큰 값을 반환하는 함수’를 찾을때

나이브 솔루션

function maxSubarraySum(arr, num) {
  if ( num > arr.length){
    return null;
  }
  var max = -Infinity;  // 배열의 요소가 전부 음수일수도 있기 때문에 -무한대로 시작한다. 0으로 시작X
  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;
}

maxSubarraySum([2,6,9,2,1,8,5,6,3],3)

시작점부터 더하기 위해 다시 반복문을 돌린다. 중첩 반복문 시간복잡도 O(n^2)

슬라이딩 윈도우를 쓰면

function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {  // 맨앞에서 max값을 구한다.
    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;
}

maxSubarraySum([2,6,9,2,1,8,5,6,3],3)

맨 앞에서 합을 구한다음 맨 앞에 요소 만큼 빼고, 맨 뒤에 요소만큼 더한다. 시간복잡도 O(n)

분할정복(divide and conquer)

이건 진짜 있는 이름이다.

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

값을 찾기 위해 배열의 왼쪽에서 시작하여 오른쪽 끝까지 이동하기 보다

배열을 작은 조각으로 세분하여 각 조각들을 어디로 이동시킬지 결정하는 작업부터 한다.

‘정렬된 배열과 정수를 입력받아 해당 정수의 인덱스를 반환하는 함수’

나이브 솔루션

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

왼쪽부터 오른쪽끝까지 훑는다. 시간복잡도는 O(n). 하지만 배열의 길이 10억이 넘는다면?

이런 구조를 선형 탐색이라고 한다. Linear 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;
}

이건 이진 탐색 Binary Search이다. 시간복잡도는 O(log n)

전체 배열에 중간점을 찾아 큰지 작은지 비교 → 절반은 버리고 나머지 절반에서 찾는다. 반복

전체를 다 비교할 필요 없이 절반씩만 찾으면 된다.

큰 데이터셋을 취해 작은 하위셋으로 분할하고 다른 부분은 무시하는 것!