[알고리즘] 문제해결패턴

지난 시간 문제 해결을 위한 일반적인 접근 방법에 관한 내용에 이어서 일반적인(general) 패턴에 관한 내용.

대표적으로 4가지를 이야기해 볼 수 있다.

 

1. Frequency counters

Python에서 Counter 함수를 생각하면 된다. Python에서도 따로 내장함수로 만들어 뒀고, 강의에서도 일반적인 패턴으로 소개하는 것으로 보아 String 관련 문제에서 정말 많이 쓰이는 것 같다.

String, Array 등 내의 각 element 개수를 세는데 이용하자.

• JavaScript 코드

function frequencyCounter(str) {
  let counterObject = {};
  for (let val of str) {
    counterObject[val] = (counterObject[val] || 0) + 1;
  }
  return counterObject;
}

time complexity - O(n).(인듯?)

다양한 상황에서 활용할 수 있는 Counter 객체

 

2. Multiple pointers

quick sort에서 쓰이는 two pointer를 떠올려보자. 확실히 반복을 줄일 수 있는 방법으로는 다양한 추가적인 변수를 사용하는 것이 있는 것 같다. 평소에 자주 사용하는 count 변수도 비슷한 맥락으로 이해할 수 있을 것 같다. 꼭 해당 Array 안에서만 모든 것을 해결해야 하는 것이 아니라 추가적인 변수로 해결하듯이 index pointer도 1개만 아니라 다양한 pointer로 array 등의 내부를 자유롭게 왔다갔다하면서 접근하는 것

다만, 정렬된 배열이 들어오는 상황일 때 이용해주자.

• JavaScript 코드 예시

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

time complexity - O(n)인듯? 최악으로 한쪽으로만 몰려도 n번 순회니까

버블 정렬 등에서 temp에 저장하고 array 계속 도는 것 보다 접근하는 index를 여러개 두는 포인트를 잘 생각하자.

3. Sliding window

재밌는 개념? 네이밍이라 할 수 있겠다. 항상 감으로만 있던 개념이 일반적인 개념으로 구체화된 시간이었다. Array, String 등에서 연속된 Subsequence 즉, 하위 Array, String 등을 다루기에 좋은 해결 패턴이다(예를 들어 "hello world"에서 "hel", "worl" 등이 Subsequence라고 할 수 있다.). 

Sliding window 말 그대로 내가 바라보고 있는 창문? 프레임? 등이 미끄러진다고 생각하면 된다. Array가 움직이는 게 아니라 우리가 쳐다보는 카메라 자체가 미끄러지는 것.

문제로 이해해보자

4. Divide and Conquer 분할과 정복

굳이 따로 말하지 않아도 너무 유명한 분할과 정복이다. 다른 것 필요없고 다음 그림부터 보자.

 

출처: 파이썬 알고리즘 인터뷰|날짜: 2020-09-10|저작자: 책만 출판사|저작권: CC BY-NC 2.0 KR

 

말 그대로 한가지 문제를, 배열을 나누고, 나누고, 나눠서 가장 간단하게 해결 할 수 있을 때 정복을 하고 다시 합쳐나가는 것이다. 앞으로 계속 다루게 될 것이라고 간단하게만 정리해줬다. O(log N)을 보장.