알고리즘 강의 정리 (간략)

** 여기 나온 코드는 제가 나중에 보았을 때 기억이 날 정도로.. 작성했기 때문에 참고할 만 코드는 아닙니다!

문제 풀이 패턴

1. Frequency Counter Pattern

아나그램

array [a, a, i, y, i] → { "a" : 2, "i" : 2, "y": 1 }

2. 다중 포인터 

* 정렬된 배열이여야함

ex) 인자들의 합이 x 값인 인자 둘을 구하라 

//주어진 arr에 두 인자의 합이 10인 경우가 존재하는가
let x = 10 
let arr = [1,2,4,5,6,14,30]

let i = 0;
let j = arr.length - 1

while(i < j) {
	if(arr[i] + arr[j] > x) {
		j--
	} else if(arr[i] + arr[j] <x) {
		i++
	} else 
    	return true
}

return false

 

3. 슬라이딩 윈도우

ex) 연속된 num개의 인자의 최대합 

// 3개의 연속된 값
let a = [1,45,63,24,5,6,9,1,333,4,2]

let maxSum = a.slice(0,3).reduce((ac,cur) => (ac + cur),0)
let tmpWindow = maxSum

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

 

4. 분할 정복

문제를 나눌 수 없을 때까지 나눠서 다시 합병하여 문제의 답을 얻는 알고리즘

 1 ) divide : 문제 분할

 2) Conquer : 분할 가능할 때까지 분할, 분할 더 안될 시 문제를 해결함

 3) Combine : 2번의 Conquer한 문제들을 통합하여 원래 문제의 답을 얻음