Posted 알고리즘 / Udemy0 visits

Udemy - 문제 해결 패턴

일반적인 문제풀이 패턴에 대해서 정리해보았다.

1️⃣  빈도수 세기 패턴

🎯 2중으로 중첩된 반복문 보다는, 단일 반복문 두 개를 사용하는 것이 훨씬 좋다.

  1. 빈도수 세기 알고리즘 패턴 (전체 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

  1. 패턴 분석 (단계별)

    • 두 배열의 길이 비교

      만약 두 배열의 길이가 다르다면? → 중복된 값이 있거나, 생략된 값이 있는 것을 의미한다.

      1
      2
      3
      4
      // 두 배열의 길이가 같지 않다면, false를 반환하고 함수를 종료한다.
      if (arr1.length !== arr2.length) {
        return false;
      }

    • 객체 생성

      for문을 활용하여 대상객체와 도구객체 하나씩을 만든다.
      “그리고 위에서도 설명했듯, 중첩 반복문 보다는 단일 반복문 여러개가 더 낫다.”

      for ... of의 이해

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      let frequencyCounter1 = {};
      let frequencyCounter2 = {};
      for (let val of arr1) {
        // 아래의 코드는 이러한 결과를 도출한다 => { val : (val or 0) + 1 }
        // 즉, 해당 값이 존재하면 그 값 +1을 해주고, 없으면 0+1을 해준다.
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
      }
      for (let val of arr2) {
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
      }

      // 이렇게 하면, 두 개의 도구대상 객체가 생성된다.

    • 반복문 내에서 도구/대상 비교하기

      객체에 대한 반복문에서는 반환값이 value가 아닌, key가 반환된다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      for (let key in frequencyCounter1) {
        // {key:1} -> {key^2:1}의 구조에서,
        // key^2의 값이 fC2의 키값에 존재하는지 체크하는 조건문
        if (!(key ** 2 in frequencyCounter2)) {
          return false;
        }
        // {key^2 : n}에서 n값이 fC1의 {key: n}에서의 n값과 같은지 같지 않은지 체크
        if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
          return false;
        }
      }
      // 이 모든 조건문을 통과하면 => true를 리턴한다.

  2. for ... in vs for ... of

    • for ... in : 객체에서도 사용 가능하다.
    • for ... of : 객체에서 사용 불가능하다 (문자열, 배열, Set 등등)

  3. ✏️  예제 ( 애너그램 함수 )

    위의 빈도수 체크 알고리즘을 활용해 두 문자열을 비교하는 함수를 만들어보자. (소문자만 고려)

    1. 객체 만들기

      객체 생성

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      function validAnagram(a, b) {
        if (a.length !== b.length) {
          return false;
        }
        let aObj = {};
        let bObj = {};
        for (let val of a) {
          aObj[val] = (aObj[val] || 0) + 1;
        }
        for (let val of b) {
          bObj[val] = (bObj[val] || 0) + 1;
        }
        console.log(aObj, bObj);
      }

    2. 객체의 key와 value 일치여부 각각 체크하기

      1
      2
      3
      4
      5
      6
      7
      8
      for (let key in aObj) {
        if (!(key in bObj)) {
          return false;
        }
        if (aObj[key] !== bObj[key]) {
          return false;
        }
      }

    3. 💡 최종 솔루션 (1)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      function validAnagram(a, b) {
        if (a.length !== b.length) {
          return false;
        }
        let aObj = {};
        let bObj = {};
        for (let val of a) {
          aObj[val] = (aObj[val] || 0) + 1;
        }
        for (let val of b) {
          bObj[val] = (bObj[val] || 0) + 1;
        }
        for (let key in aObj) {
          if (!(key in bObj)) {
            return false;
          }
          if (aObj[key] !== bObj[key]) {
            return false;
          }
        }
        return true;
      }

    4. 💡 이외의 솔루션 (2)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      function validAnagram(first, second) {
        if (first.length !== second.length) {
          return false;
        }

        const lookup = {};

        for (let i = 0; i < first.length; i++) {
          let letter = first[i];
          lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
        }

        for (let i = 0; i < second.length; i++) {
          let letter = second[i];
          // 만약 a를 예로 들면, {a : 0}이어도, 객체에선 이를 존재하지 않는다고 계산한다.
          if (!lookup[letter]) {
            return false;
          } else {
            lookup[letter] -= 1;
          }
          // value가 0이면 false로 인식하기 때문에, 굳이 마지막에 모든 key의 value들이 0인지 더블체킹 할 필요는 없다.
        }
        return true;
      }

2️⃣  다중 포인터 패턴

다중 포인터 패턴이란, 배열 또는 문자열 등의 index를 가리키는 포인터가 두 개 이상 활용되는 알고리즘 패턴을 의미한다.

  1. 🏋️ 서로의 합이 0이 되는 숫자 조합 찾기
    • 내가 평소에 사용하던 중첩 for문 : O($n^2$)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      function pointer(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) 버전
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      // arr이 정렬되어 있음을 가정한다.
      // [-4,-3,-2,-1,0,1,2,3,10]
      function pointer2(arr) {
        let start = 0;
        let end = arr.length - 1;
        while (start < end) {
          let sum = arr[start] + arr[end];
          if (sum === 0) {
            return [arr[start], arr[right]];
          } else if (sum > 0) {
            // end가 상대적으로 더 크다는 뜻이고, 일단 start에 맞는 값이 있는지 없는지 체크해야 되기 때문에 end--를 한다.
            end--;
          } else {
            // sum < 0이 되어버리면 이전 start에 맞는 end값이 존재하지 않는다는 뜻이다.
            // 따라서 start++ 해준다.
            start++;
          }
        }
      }
  2. 고유 숫자 세기 (Count Unique Nums)
    • 시간 복잡도 O(N)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      function countUniqueValues(arr) {
        // arr이 텅 빈 배열이라면 그냥 0을 반환
        if (arr.length === 0) {
          return 0;
        }
        let first = 0;
        let second = first + 1;
        while (second < arr.length) {
          // 두 값이 같으면 두번째 포인터를 한 칸 우측으로 이동
          if (arr[first] === arr[second]) {
            second++;
          } else {
            // 두 값이 같지 않으면 ? => 두 포인터를 모두 한 칸 우측으로 옮기고, 두 번째 포인터가 가리켰던 값을 first의 다음 자리에 원래값과 치환시킨다.
            second++;
            first++;
            arr[first] = arr[second - 1];
          }
        }
        return first + 1;
      }
    • for문 활용 ( 더 간결한 코드 )
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      function countUniqueValues(arr) {
        if (arr.length === 0) return 0;
        let i = 0;
        for (let j = 1; j < arr.length; j++) {
          if (arr[i] !== arr[j]) {
            i++;
            arr[i] = arr[j];
          }
        }
        return i + 1;
      }

3️⃣  기준점 이동 배열 패턴 ( Sliding Window )

평소에 자주 접했던, 배열을 한 묶음씩 묶어서 체크하는 반복문을 활용한 알고리즘 패턴이다.

  1. 🤔  배열 내에서 N개로 묶은 묶음의 합 중 가장 큰 값을 구하시오

    • 시간복잡도 : O($n^2$)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      function maxSubarraySum(arr, num) {
        if (num > arr.length) {
          return null;
        }
        let max = -Infinity;
        for (let i = 0; i < arr.length - num + 1; i++) {
          sum = 0;
          for (let j = 0; j < num; j++) {
            // num 묶음의 서브 배열의 총합을 구한다.
            sum += arr[i + j];
          }
          if (sum > max) {
            // 만약 그 총합의 값이 max보다 크면, 해당 값을 max에 대입하여 갱신한다.
            max = sum;
          }
        }
        return max;
      }

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

    • 시간복잡도 : O(n) → Sliding Window

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      function maxSubarraySum(arr, num) {
        let maxSum = 0;
        // tempSum은 일시적 합을 의미한다.
        let tempSum = 0;
        // num의 값(묶음의 단위)이 배열의 길이보다 크다면 그냥 null을 반환한다.
        if (arr.length < num) return null;
        // 우선 maxSum의 초기값을 첫 묶음의 총합으로 설정한다.
        for (let i = 0; i < num; i++) {
          maxSum += arr[i];
        }
        // 일시적 합인 tempSum의 초기값도 이와 일치시켜준다.
        tempSum = maxSum;

        for (let i = num; i < arr.length; i++) {
          // 일시적 합 = 기존값 - 기존 묶음에서의 가장 첫번째 요소의 값 + 새로운 그 다음 값
          tempSum = tempSum - arr[i - num] + arr[i];
          // 두 수 중에 더 큰 값이 maxSum이 된다
          maxSum = Math.max(maxSum, tempSum);
        }
        return maxSum;
      }

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

4️⃣  분할 점령 ( Divide and Conquer )

퀵 정렬과 합병 정렬 등에도 사용될 만큼, 활용도가 높은 알고리즘 패턴이다.
이름 그대로, 데이터를 분할해서 → 점령(활용)한다.
ex) 큰 배열을 더 작은 단위로 쪼개서 다음 단계로의 이동을 더욱 효율적으로 가져간다.

  1. 이진탐색(Binary Search)에서의 활용 : O($log_n$)

    1
    2
    3
    4
    5
    6
    7
    // arr에 11이 포함되는지 찾기
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];

    // arr의 중간값 도출 -> 중간값보다 찾는 값이 큰지 작은지 체크
    // 작으면 arr = 0~중간값;
    // 크면 arr = 중간값~arr.length-1
    // 이런 과정을 계속 반복하면서 효율적으로 원하는 값을 탐색한다.

Udemy - 문제 해결 패턴

https://hoonjoo-park.github.io/algorithm/udemy/4. Solution_Pattern/

Author

Hoonjoo

Posted on

2022-01-10

Updated on

2022-02-07

Licensed under

#

Comments

Catalogue

×