2020. 3. 1. 14:18ㆍ알고리즘
문제 해결 기법
1. frequency counter
-
uses objects or sests to collect values/frequencies of values
-
빈도수를 측정하는 객체를 만든다.
Problem : 두 개의 배열을 받아서 첫 번째 배열의 모든 값들의 제곱값이 두번째 배열에 존재할때 true를 반환하는 함수(same)를 만드시오.
ex)
- same([1,2,3],[4,1,9]) --> true
- same([1,2,3], [1,9]) --> false
그냥 풀었을 때
function same(arr1, arr2){
if(arr1.length !== arr2.length)
return false;
for(let val of arr1){
let index = arr2.indexOf(val**2);
// indexOf -> 반복문을 돈다. -> O(n^2)
if(index === -1)
return false;
// 해당 키가 존재하지 않는다
arr2.splice(index, 1)
// 빈도수가 같아야하기 때문에 일치하는 키는 없앤다.
}
return true;
}시간 복잡도는 O(n^2)
frequency counter 기법을 이용했을 때
function same(arr1, arr2){
let arr1Count = {};
let arr2Count = {};
if(arr1.length !== arr2.length)
return false;
for(let val of arr1){
arr1Count[val] = (arr1Count[val] || 0) + 1;
}
// arr1 값이 없다면 1로 설정, 없다면 이미 있는 값에 +1
for(let val of arr2){
arr2Count[val] = (arr2Count[val] || 0) + 1;
}
// 위와 동일
for(let val in arr1Count){
if(!arr2Count[val**2])
return false;
// 상응하는 키가 있는지 검사
if(arr1Count[val] !== arr2Count[val**2])
return false;
// 상응하는 키가 있다면 빈도수가 같은지 검사
}
return true;
}시간 복잡도는 O(n^2)
해설 : arr1과 arr2의 각 값들의 빈도를 저장하는 객체 arr1Count, arr2Count를 만들고 이 두개의 객체를 비교
2. multiple pointers
- 여러개의 index를 상황에 맞게 조절해(처음, 중간, 끝) 문제를 효율적으로 해결하는 기법
Problem : 오름차순으로 정렬된 정수들의 배열을 받아 더해서 0이 되는 짝의 배열을 반환하는 함수(sumZero)를 만드시오. (없다면 undefined 반환)
ex)
- sumZero([-3,-2,-1,0,1,2,3]) --> [-3,3]
- sumZero([-2,0,1,3]) --> undefined
그냥 풀었을 때
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]];
}
}
}시간 복잡도 => O(n^2)
multiple pointers 적용
function sumZero(arr){
let left = 0;
let right = arr.length -1;
// 두 개의 Index 설정
while(left<right){
let sum = arr[left] + arr[right];
if(sum === 0){
return [arr[left], arr[right]];
} else if(sum<0){
left++;
} else{
right--;
}
}
}시간 복잡도 => O(n)
해설 : 양 끝에 index 존재(left, right). 양 끝의 숫자들을 더해 0보다 크다는 것은 right(끝 index)에 해당하는 값(양수)이 더 크다는 것을 의미하기 때문에 right 값을 하나 줄인다.(해당 배열은 오름차순 정렬이다!!) 마찬가지로 양 끝의 숫자들을 더해 0보다 작다는 것은 left(처음 index)에 해당하는 값(음수)이 더 크다는 것을 의미하기 때문에 left 값을 하나 늘린다. 더해서 0이면 그 짝을 반환.
3.sliding window
-
하나의 window를 만들어 상황이 따라 값이 증가하거나 감소
-
window는 array나 number
-
배열, 문자열에서 subset을 찾을때 유용
Problem : 정수들의 배열과 숫자 n을 받아 배열 안에서 n개의 연속 요소들의 최대합을 반환하는 함수(maxSubarraySum)을 만드시오.
ex)
- maxSubarraySum([1,2,5,2,8,1,5], 2) --> 10
- maxSubarraySum([4,2,1,6], 1) --> 6
그냥 풀었을 때
function maxSubarraySum(arr, num){
if(arr.length<num)
return null;
let maxSum = -Infinity;
let tempSum;
for(let i=0; i<arr.length-num+1; i++){
tempSum = 0;
for(let j=0; j<num; j++){
tempSum += arr[i+j];
}
if(tempSum > maxSum){
maxSum = tempSum;
}
}
return maxSum;
}시간 복잡도는 --> O(n^2)
sliding window 기법 적용 후
1
function maxSubarraySum(arr, num){
if(arr.length<num)
return null;
let maxSum = 0;
let tempSum = 0;
for(let i=0; i<num; i++){
tempSum += arr[i];
}
maxSum = tempSum;
// window --> maxSum
for(let i=0; i<arr.length-num+1; i++){
tempSum = tempSum - arr[i] + arr[i+num];
// 젤 앞의 값은 빼고 젤 뒤의 값을 더한다
if(tempSum>maxSum)
maxSum = tempSum;
}
return maxSum;
}2
function maxSubarraySum(arr, num){
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
for (let i = 0; i < num; i++) {
tempSum += arr[i];
}
maxSum = tempSum;
// window --> maxSum
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
// 위와 동일
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}두가지 버전 다 시간 복잡도 => O(n)
해설 : 처음에 0부터 n-1까지의 합을 구한다.(=window). 앞의 값을 빼고 뒤의 값을 추가하면서 그 전 값과 비교한다.