문제 해결 패턴

문제 해결 패턴 소개

프로그래밍 문제를 효과적으로 해결하기 위해 다양한 문제 해결 패턴이 존재합니다. 이 글에서는 대표적인 문제 해결 패턴을 소개하고, 각 패턴에 대한 예시와 코드 리팩토링을 통해 성능을 개선하는 방법을 설명합니다.

 

빈도수 세기 패턴 (Frequency Counters)

빈도수 세기 패턴은 값의 빈도를 수집하기 위해 객체나 집합을 사용하는 방법입니다. 이를 통해 배열이나 문자열에서 중첩 루프(O(N^2))를 사용하지 않고 효율적으로 문제를 해결할 수 있습니다.

 

예시 문제

두 개의 배열을 입력으로 받는 same이라는 함수를 작성하세요.
이 함수는 첫 번째 배열의 모든 값이 두 번째 배열에서 제곱된 값과 일치하면 true를 반환해야 합니다.
값의 빈도수도 동일해야 합니다.

same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // 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;
        }
        arr2.splice(correctIndex, 1);
    }
    return true;
}

시간복잡도: O(N^2)

 

리팩토링 후

빈도수 세기 패턴을 적용한 리팩토링된 코드입니다.

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

시간 복잡도: O(N)

 

다중 포인터 패턴 (Multiple Pointers)

다중 포인터 패턴은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 사용하여 특정 조건에 따라 시작 지점이나 끝 지점을 이동시키며 문제를 해결하는 방법입니다. 최소한의 공간 복잡도로 문제를 해결하는 데 매우 효율적입니다.

 

예시 문제

정렬된 정수 배열을 입력으로 받아들이는 sumZero라는 함수를 작성하세요.
이 함수는 합이 0이 되는 첫 번째 쌍을 찾아야 합니다.
합이 0이 되는 두 값을 포함하는 배열을 반환하거나, 그런 쌍이 존재하지 않는 경우 undefined를 반환해야 합니다.

sumZero([-3,-2,-1,0,1,2,3]) // [-3,3] 
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined

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

시간 복잡도: 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]];
        } else if(sum > 0){
            right--;
        } else {
            left++;
        }
    }
}

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

 

슬라이딩 윈도우 패턴 (Sliding Window)

슬라이딩 윈도우 패턴은 배열이나 문자열 등의 데이터 부분 집합을 추적하는 데 매우 유용한 패턴입니다. 특정 조건에 따라 윈도우가 증가하거나 이동하며 문제를 해결합니다.

 

예시 문제

정수 배열과 n이라는 숫자를 입력으로 받아 n개의 연속된 요소들의 최대 합을 계산하는 maxSubarraySum 함수를 작성하세요.

maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null

function maxSubarraySum(arr, num) {
  if ( num > arr.length){
    return null;
  }
  var 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;
}

시간 복잡도: 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++) {
    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;
}

시간 복잡도 O(N)

 

분할과 정복 패턴 (Divide and Conquer)

분할과 정복 패턴은 데이터 세트를 더 작은 조각으로 나누고, 그런 다음 데이터의 부분 집합에 대해 프로세스를 반복하는 방법입니다. 이를 통해 시간 복잡도를 크게 줄일 수 있습니다.

예시 문제

정렬된 정수 배열을 입력으로 받아 주어진 값을 찾아 그 값이 위치한 인덱스를 반환하는 search 함수를 작성하세요. 값이 발견되지 않으면 -1을 반환해야 합니다.

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

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

시간 복잡도: O(N)

 

리팩토링 후

분할과 정복 패턴을 적용한 리팩토링된 코드입니다.

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

시간 복잡도: O(Log N)