[알고리즘] 문제 해결 패턴과 도전과제 (자바스크립트)

지난 게시글 문제 해결 접근법과 이어지는 글입니다.

 

문제 해결 패턴

1. 빈도 카운터 (Frequency Counter)

자바스크립트 객체의 키-값 제어를 통해 다양한 값과 빈도를 수집

 

 

문제1 두 배열이 주어졌을 때, 한 배열 원소값들의 제곱을 담고 있는 다른 배열로 이루어진 경우 참을 반환하는 "Same" 함수를 작성하시오. (원소의 순서는 상관 없음)

 

해결1 이중 루프를 이용한 일반적인 해법, O(N^2)

function same(arr1,arr2){
    // 두 배열의 길이가 다른 경우 1차적으로 필터링
    if(arr1.length !== arr2.length){
        return false
    }

    for (let i=0;i<arr1.length;i++){
        // arr1 원소 값의 제곱이 arr2 배열 내부에 존재하는 인덱스를 반환
        // 존재하지 않을 경우 -1을 반환
        let correctIndex = arr2.indexOf(arr1[i]**2)

        // 존재하지 않는 경우 -1을 반환받았으므로, false 반환하며 코드 종료
        if(correctIndex === -1){
            return false
        }

        // 비교를 끝낸 원소는 제거
        arr2.splice(correctIndex,1)
    }
    return true
}

 

해결2 빈도 카운터 패턴을 활용한 문제 해결, O(N)

function same(arr1,arr2){
    if(arr1.length !== arr2.length){
        return false
    }

    // 빈도수를 측정할 빈 객체 생성
    let arr1_frequency = {}
    let arr2_frequency = {}

    // 배열1,2의 빈도수를 측정하여 객체에 저장
    for(let val of arr1){
        arr1_frequency[val] = (arr1_frequency[val] || 0) + 1
    }
    
    for(let val of arr2){
        arr2_frequency[val] = (arr2_frequency[val] || 0) + 1
    }

    // 객체 Key 비교
    for(let key in arr1_frequency){
        // 배열1 Key의 제곱의 빈도수와 배열2 Key 빈도수가 불일치할 경우, false
        if(!(key ** 2 in arr2_frequency)){
            return false
        }
        // Key는 동일하지만 빈도수가 다른 경우, false
        if(arr2_frequency[key**2] !== arr1_frequency[key]){
            return false
        }
    }
    return true
}

---

문제2 두 개의 문자열을 입력으로 받으며 두 문자열이 서로의 애너그램이면 참을 반환하는 validAnagram() 함수를 작성하시오.

 

해결 빈도 카운터 패턴을 이용한 문제 해결

function validAnagram(str1,str2){
    str1 = str1.toLowerCase()
    str2 = str2.toLowerCase()

    let str1_freq = {}
    let str2_freq = {}

    // 문자열을 한 글자씩 순회하는데, 추가된 적 있었던 글자일 경우 기존값에 +1
    // 처음 마주친 글자일 경우 1로 설정
    for(let key of str1){
        str1_freq[key] = (str1_freq[key] || 0) + 1
    }

    for(let key of str2){
        str2_freq[key] = (str2_freq[key] || 0) + 1
    }

    console.log(str1_freq, str2_freq)

    // 유효성 검사
    for(var key in str1_freq){
        if(!(key in str2_freq)){
            return false
        }
        if(str1_freq[key] !== str2_freq[key]){
            return false
        }
    }
    return true
}

validAnagram('aa z','z aa')

---

 

2. 다중 포인터 (Multiple Pointers)

배열 등의 선형 요소에 인덱스나 위치에 해당하는 두 개의 포인터 혹은 값을 만든 다음 특정 조건에 따라 중간 지점에서 시작해 시작 지점 / 끝 지점 / 양쪽 지점을 향해 이동

 

 

문제1 오름차순으로 정렬되어 있는 배열을 입력받아 두 원소의 합이 0이 되는 쌍을 반환하는 함수 sumZero()를 작성하시오

 

해결1 이중 루프를 이용한 일반적인 해법, O(N^2)

첫 번째 원소부터 시작하여 두 번째 루프에서 모든 원소를 순회하며 합이 0이 되는 원소를 탐색한다. 합이 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]]
            }
        }
    }
}

 

해결2 다중 포인터를 사용한 문제 해결, O(N)

한 포인터는 인덱스 0에서 시작하고, 다른 포인터는 배열의 마지막 인덱스에서 역순으로 탐색한다. 합이 0이 되는 쌍을 찾는 것이기 때문에 큰 값부터 탐색하는 것이 효율적이다.

 

루프 중첩이 필요 없다는 것이 장점이고, 첫 번째 루프의 역할을 Left 포인터가, 두 번째 루프의 역할을 Right 포인터가 대신한다.

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

---

문제2 숫자로 이루어진 배열이 주어졌을 때, 중복을 제외한 숫자의 갯수를 반환하는 함수 countUniqueValues()를 작성하시오.

주어진 조건에 따라 두 포인터의 초기값과 진행 방향을 다르게 지정해줄 수 있는데, 본 문제에서는 두 포인터 모두 시작 인덱스에 위치한다.

 

해결1 다중 포인터를 사용한 해결

function countUniqueValues(arr){
    let left = 0;
    let right = left + 1;

    if(arr.length === 0){
        return 0
    }
    
    while(right < arr.length){
        if(arr[left] === arr[right]){
            right++;
        } else{
            left++;
            arr[left] = arr[right];
            right++;
        }
    }
    return left;
}

빈도 카운터 패턴으로 접근하여 문제를 해결할 수도 있을 듯 하다.

---

 

3. 슬라이딩 윈도우 (Sliding window)

배열이나 문자열과 같은 일련의 데이터를 입력하거나 연속적인 데이터의 하위 집합을 찾는 경우

 

문제1 숫자로 이루어진 배열 주어졌을 때, 연속된 n개 숫자의 합이 가장 큰 값을 반환하는 maxSubarraySum() 함수를 작성하시오.

 

해결

function maxSubarraySum(arr,n){
    let maxSum = 0;
    let tempSum = 0;

    if(arr.length < n) return null;

    for (let i = 0; i < n; i++){
        maxSum += arr[i];
    }
    tempSum = maxSum;

    for (let i = n; i < arr.length; i++){
        tempSum = tempSum - arr[i-n] + arr[i];
        maxSum = Math.max(maxSum, tempSum);
    }
    return maxSum;
}

n개의 원소 합을 구한 maxSum 변수는 array.slice와 array.sum 메서드를 활용해 구현해도 좋을 듯 하다.

컴퓨터 비전 공부할 때도 슬라이딩 윈도우를 자주 접했었는데, 개념은 비슷해 보인다.

 

본 코드는 배열을 전체적으로 한 번 순회하기 때문에 O(N)의 시간 복잡도를 갖는다.

---

 

4. 분할과 정복 패턴

퀵정렬과 병합 정렬, 이진 탐색 등이 해당 패턴에 속한다.

분할 / 정복 패턴은 주로 배열이나 문자열 같은 큰 규모의 데이터셋을 처리할 때 사용된다.

배열을 작은 조각으로 소분하여 이들을 어디로 이동할지 결정하는 흐름으로 구성된다.

 

분할 / 정복 패턴과 관련된 상세한 학습은 추후 섹션에서 다룰 예정.

---

Javascript 알고리즘 / 자료구조 마스터 (유데미) 강의 수강 후 복습하며 정리한 내용입니다. 원 강의는 이곳에서 수강할 수 있습니다.