04 문제 해결 패턴

4.1 대표적인 패턴들

  문제 해결 접근법에 이어지는 내용으로 이제는 때때로 유용하게 사용할 수 있는 몇 가지 일반적인 패턴을 살펴보려 한다. 굉장히 많은 패턴들이 존재하지만 대표적인 패턴들만 살펴보자.(공식적인 이름이 붙은 패턴들도 있지만, 그렇지 않은 패턴들도 존재한다.)

 

1. Frequency Counter 빈도수 세기 패턴 (강사님이 직접 붙인 이름이다)

2. Multiple Pointers 다중 포인터 패턴 (강사님이 직접 붙인 이름이다)

3. Sliding Window 기준점 간 이동 배열 패턴

4. Divide and Conquer 분할과 정복 패턴 (공식적인 이름이다. 실제 자주 사용됨)

5. Greedy Algorithms 탐욕 알고리즘 패턴 (실제 자주 사용됨)

 

  이 처럼 문제 해결에 유용하게 사용할 수 있는 패턴들이 많이 존재한다.

 

4.2 Frequency Counter 빈도수 세기 패턴 (공식적인 이름은 없다)

  빈도수 세기 패턴은 보통 자바스크립트의 객체를 사용해서 다양한 값과 빈도를 수집할때 유용하게 사용할 수 있는 패턴이다. 이 패턴은 여러 데이터와 입력값이 서로 비슷한 값으로 구성되어 있는지, 서로 간의 아나그램(말 장난에서 유례)인지, 값이 다른 값에 포함되는지 여부를 비교할 때 유용하다.

 

  예를들어, '2개의 배열을 허용하는 arrayCompare 라는 함수를 작성한다'고 생각해보자. 이 함수는 처음으로 입력받은 배열의 모든 값의 제곱이 두 번째로 입력받은 배열에 모두 포함되어 있는지 알기 위한 함수다. 순서는 상관없지만 두 배열의 요소 개수는 동일해야 한다.

ex) [1, 2, 3] [1, 4, 9] -> true

 

  빈도수 세기 패턴을 사용하지 않고 작성해보자

function arrayCompare(array1, array2){
    if(array1.length !== array2.length){
        return false;
    }
    for(let i = 0; i < array1.length; i++){ //오엔
        let correctInd = array2.indexOf(array1[i] ** 2) //인덱스오브가 오엔임
        if(correctInd === -1) {
            return false;
        }
    console.log(array2);
    array2.splice(correctInd,1)
    }
    return true;
}//오엔제곱 시간복잡도를 갖음

console.log(arrayCompare([1,2,3,2], [9,1,4,4]))

  위와 같이 코드를 작성하면 O(N^2) 시간 복잡도를 갖는 함수가 작성된다. 이번에는 패턴을 사용해서 작성해 보자.

function arrayCompare(array1, array2){
    if(array1.length !== array2.length){
        return false;
    }
    let freCounter1 = {}
    let freCounter2 = {}
    for(let foo of array1){
        freCounter1[foo] = (freCounter1[foo] || 0) + 1
    }
    for(let foo of array2){
        freCounter2[foo] = (freCounter2[foo] || 0) + 1        
    }
    console.log(freCounter1);
    console.log(freCounter2);
    for(let bar in freCounter1){
        if(!(bar ** 2 in freCounter2)){
            return false
        }
        if(freCounter2[bar ** 2] !== freCounter1[bar]){
            return false
        }
    }
    return true
}

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

  O(N) 시간 복잡도를 갖는 함수를 작성할 수 있다. 이를 통해 성능면에서도 뛰어난 함수를 작성할 수 있다.(사실 이렇게 강의에서 배웠지만, 너무 코드가 복잡한건 아닌가 하는 의구심은 든다..)

 

4.3 아나그램 

  아나그램이란 일종의 말장난으로 어떠한 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 말한다. 즉, 'apple'을'elpap'처럼 물론 말은 되지만 같은 문자들을 가지고 있지만, 순서가 다른것을 아나그램이라고 한다. 우리가 여기서 풀어야 할 문제는 두 개의 문자열을 입력받아 두 문자열이 서로의 아나그램이면 참을 아나그램이 아니라면 거짓을 반환하는 함수를 구성하는것이 목표다. 이때 활용할 수 있는 것이 바로 문자열 세기 패턴이다. 패턴을 이용해서 아나그램 함수를 만들어보자.

function anagram(string1,string2){
    if(string1.length !== string2.length){
        return false;
    }
    let strObject1 = {};
    let strObject2 = {};
    for(let i of string1){
        strObject1[i] = (strObject1[i] || 0) + 1; // 객체안에 접근 할 프로퍼티가 없으면, undefined를 반환하므로 falsy가 되고 false값으로 암묵적 타입 변환되어 뒤의 값이 반환됨
    }
    for(let i of string2){
        strObject2[i] = (strObject2[i] || 0) + 1;
    }
    for(let i in strObject1){
        if(!(i in strObject2)){
            return false;
        }
        if(strObject2[i] !== strObject1[i]){
            return false;
        }
    }
    return true;
}

console.log(anagram("cat","bus")); // false

 즉, 위 코드처럼 문자열이나 배열안에 들어있는 값들이 몇 개 있는지 카운트하여 객체로 만들고 비교하는게 빈도 수 세기 패턴이다. 반복문을 적용하여 만든 객체를 사용하고 중첩되지 않은 두 번째 반복문을 사용해야 한다. 그렇게 만든다면 O(N) 시간 복잡도를 유지할 수 있다. 

 

  다시 말해 첫 번째 입력받은 값을 세분화하여 객체에 각 문자 또는 요소의 개수를 카운트해서 프로퍼티로 만들고, 두 번째 값과 비교해 가면서 하나 하나 지워나가면서 비교하는것이 바로 빈도수 세기 패턴 방법이다. 이러한 빈도수 세기 패턴은 숫자가 같은 숫자로만 구성되어 있고, 순서만 다른지 확인해야 하는 경우 등에 응용이 가능한 패턴이다. 즉 두 값을 비교할 때 비교가 용이하다.

 

4.4 다중 포인터 패턴 (공식적인 이름이 없는 패턴이다)

  이 패턴의 정의는 인덱스나 위치에 해당하는 포인터를 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점, 또는 양쪽 지점을 향해 이동시키는 것이다. 핵심은 두 개의 포인터를 사용한다는 것이다.

 

  예를 들어, 정렬된 배열을 입력받아 sumZero 함수를 만든다고 해보자. 이 함수는 합계가 0인 첫 번째 쌍 즉, 한 숫자를 가져와 다른 숫자에 더하면 0이 되는 한 쌍을 찾는 함수이다. 주의해야 할 점은 정렬된 배열을 입력받아야 하며, 오름차순으로 되어 있어야 한다.

ex)

[-3, -2, -1, 0, 1, 2, 3] -> [-3, 3]을 반환함

[-2, 0, 1, 3] -> undefined를 반환함(합이 0인 쌍이 없으므로)

 

  패턴을 사용하지 않고 코드를 작성해 보자.

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

 

  위 코드는 반복문을 중첩해서 사용하여 O(N^2)시간 복잡도를 갖는 함수가 된다. 즉, 하나의 요소를 기준으로 모든 요소들을 하나 하나 다 비교하게 된다.

 

  다중 포인터 패턴을 적용해서 코드를 작성해 보자.

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

  위의 다중 포인터 패턴을 이용하면 O(N)시간 복잡도를 갖는 코드를 작성할 수 있다. 즉 두 개의 포인터를 만들어서 두 값의 합이 영보다 작다면 왼쪽 포인터를 한 칸 움지이고, 두 값의 합이 0보다 크다면 오른쪽 포인터를 앞으로 이동하면서 두 요소의 합이 0인 배열을 반환한다.

 

4.5 Sliding Window 패턴 기준점 간 이동 배열 패턴

  슬라이딩 윈도우 패턴은 단일 변수, 하위 배열, 또는 필요한 경우 문자열을 입력받아 조건에 따라 윈도우(창문)을 시동시키며 해당 데이터의 하위 집합을 찾는 경우에 유용하다.(시작 위치에서 시작하면 보통 왼쪽에서 오른쪽으로 이동, 반대로도 가능하다)

ex)가장 긴 시퀀스를 찾아라 "hellomyworld" -> "hel/lomyw/orld" -> "lomyw"가 가장 긴 시퀀시이다. 이런 경우에 적용하기 유용한 패턴이 바로 슬라이딩 윈도우 패턴이다.

 

예제문제) 배열에서 조건에 맞는 합이 가장 큰 시퀀스의 합은 무엇인가?

  ex) maxSum([1, 2, 5, 2, 8, 1, 5], 2) -> 10이다(2개의 연속하는 요소들 중 가장 합이 큰 요소의 합을 반환하는 함수를 호출 함)

패턴을 사용하지 않고 함수를 만들어 보자.

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

  O(N^2) 시간 복잡도를 갖는 함수를 통해 해당 문제를 해결할 수 있다.(반복문 중첩 사용)

 이번에는 패턴을 사용하여 문제를 해결해 보자.

function maxSum(array, number){
    let max = 0;
    let temp = 0;
    if (array.length < number) return null;
    for (let i = 0; i < number; i++) {
        max += array[i];
    }
    temp = max;
    for (let i = number; i < array.length; i++) {
        temp = temp - array[i - number] + array[i];
        max = Math.max(max, temp);
    }
    return max;
}

  패턴을 사용하여 O(N) 시간 복잡도를 갖는 효율적인 코드를 작성할 수 있다.

 

4.6 Divide and Conquer 분할과 정복 (공식화된 이름이다)

  이 알고리즘은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다. 바로 어떤 패턴인지 예제를 통해 확인해 보자.

예제) indexSearch([1, 2, 3, 4, 5, 6], 4) // 3반환 (요소인 4가 위치하는 인덱스 번호를 반환하는 함수를 호출했음)

분할과 정복 패턴을 사용하지 않고 함수를 만들어 보자.

function indexSearch(array, foo){
    for(let i = 0; i < array.length; i++){
        if(array[i] === foo){
            return i;
        }
    }
    return -1;
}

O(N) 시간 복잡도를 갖는 함수를 만들어 해결할 수 있다. 다음은 패턴을 사용하여 해결하는 방법이다.

function indexSearch(array, foo) {
 
    let min = 0;
    let max = array.length - 1;

    while (min <= max) {
        let mid = Math.floor((min + max) / 2);
        let currentEle = array[mid];

        if (array[mid] < foo) {
            min = mid + 1;
        }
        else if (array[mid] > foo) {
            max = mid - 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}

  위의 코드가 작동되는 방법을 확인해 보자. 예를들어 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]의 배열에서 9를 찾아 인덱스를 반환해야 한다면 중간인 5를 선택하고 찾아야하는 9보다 작기 때문에 5를 포함하는 아래 요소들은 다 무시한다. 그리고 나머지 6부터 10까지의 하위 배열을 살펴본다. 그리고 다시 6에서 10사이의 중간인 7을 선택해서 확인하고 9보다 작기 때문에 하위배열의 7아래로는 다 무시한다. 나머지의 중간인 9를 선택하고 해당 값을 찾았기 때문에 해당값의 인덱스 번호를 반환한다. 즉, 큰 배열이나 문자열에서 특정 요소나 문자를 찾을 때 하나 하나 다 비교하는것이 아니라 중간 지점을 찾아 필요없는 부분은 무시하고 비교하고, 또 나머지 하위배열 또는 문자열에서 중간 지점을 선택해서 비교하여 원하는 요소 또는 문자에를 찾는 방법이다. 한 마디로 큰 데이터셋을 취해 작은 하위셋으로 분할하여 원하는 값을 찾는 것이다.