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

빈도수 패턴

객체를 사용해서 다양한 값과 빈도수를 모음

• 여러 데이터와 입력값이 서로 비슷한지
• 서로간의 아나그램인지.
• 값이 다른 값에 포함되는지
• 데이터를 빈도와 비교할 때

예시 1) 2개의 배열을 허용하는 함수 same. 두번째 배열은 첫번째 배열의 제곱값들을 가지고 있어야 한다.
Ex) [1,2,3 ] , [1,4,9] 이면 true 리턴.

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)임)
  
  예시 2) 아나그램확인 함수

function validAnagram(str1, str2) {
  let str1Counter = {};
  let str2Counter = {};
  for(let char of str1){
    str1Counter[char] = (str1Counter[char] || 0) +1
  }
  for(let char of str2){
    str2Counter[char] = (str2Counter[char] || 0) +1
  }
  for(let key in str1Counter) {
    if(str1Counter[key] !== str2Counter[key]) {
      return false
    }
  }
  return true
}

다중 포인터 패턴

특정 인덱스 혹은 위치에 해당하는 포인터나 값을 만들고 조건에 따라 중간지점에서 시작, 끝, 혹은 둘 모두의 지점으로 이동시키는 패턴

• 한 쌍의 값이나 조건을 충족시키는 무언가를 찾을 때

예시1) 하나의 정렬된 배열에서, 서로 더해서 0이되는 첫번째 페어를 찾는다. 없다면 undefined를 반환한다.
Ex) [-3, -2, -1, 0, 1, 2, 3] // [-3, 3]

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)중복되지 않는 수 갯수를 체크하는 함수

function countUnique(arr) {
  // 정렬된 배열이 전달되면, 중복되지 않는 값의 개수를 리턴한다.
   if(arr.length === 0) return 0;
    var i = 0;
    for(var j = 1; j < arr.length; j++){
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j]
        }
    }
    return i + 1;
}

슬라이딩 윈도우 패턴

단일 변수, 하위 배열, 다른 문자열이 되는 창문을 하나 만들고, 조건에 따라 창문을 이동시킨다.

• 배열, 문자열같은 데이터를 입력
• 특정 방식으로 연속적인 해당 데이터의 하위집합을 찾을 때

예시) 배열과 자연수가 주어질때, 자연수만큼의 연속된 요소의 합 중 가장 큰 합을 리턴할 것

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

배열의 첫 num개의 요소를 더해주고, 맨 앞의 요소 한개를 빼고 맨 뒤의 요소의 인덱스+1 의 요소를 더해줌. 이를 반복해줌

분할과 정복 패턴

데이터셋을 작게 쪼갠 다음 어떠한 행동을 그 작은 단위의 데이터들로 반복하는 것.

• 시간복잡도를 극도로 감소시킬 수 있다.