본문 바로가기

IT/Algorithm(알고리즘)

 (6)
Multiple Pointers(여러개 포인터) - averagePair 예제] averagePair라는 함수를 만드십시오. 정수가 들어간 배열과 옆에 맞출 숫자를 넣고, 배열에 있는 두 숫자의 합의 평균이 맞출 숫자랑 값이 같는 경우 True로 반환하고 아니면 False로 반환하시오. (맞출숫자가 배열에 2개 이상이어도 됩니다.) 시간복잡도: O(N) 공간복잡도: O(1) 해답 function averagePair(arr, num){ if(arr.length === 0){ return false } arr.sort() let start = 0; let end = arr.length - 1; while(start < end) { let avg = ((arr[start] + arr[end]) / 2) if(avg === num){ return true; } else if(avg..
재귀함수호출(Recursion) 재귀함수호출은 함수를 호출할때 함수 안에 서 return값을 자기 자신으로 호출을해서 문제를 더 간단하게 만드는 방법이라고 보면 된다. 예제] function sumRange(num){ if(num === 1){ return 1; } return num + sumRange(num-1); } 위의 예제에서 sumRange(3)을 넣었다 하면 3 === 1이 아니니 return 값이 return 3+sumRange(3-1) ^ | 아래에 3값이 pop된 값은 sumRange(3)에서 return 값이 3+3이 된다. 그리고 return 6을 반환하고 | sunRange(3)이 pop된다. _____|______________ return 2+sumRange(2-num)
Frequency Counter2(숫자나 글자에서 반복되는 것 있는지 확인) 1. areThereDuplicates라는 함수를 만드십시오. 그 함수에 여러개의 변수에 매개변수를 받아서 반복되는 것이 있으면 True로 반환하고 반복되는 것이 없으면 false로 반환하시오. 해답 // Frequency Counter방법(빈도 수 확인 방법) 숫자만 됨 function areThereDuplicates(){ let collection = {}; for(let val in arguments){ collection[arguments[val]] = (collection[arguments[val]] || 0) + 1 } for(let key in collection){ if(collection[key] > 1){ return true; } } return false; } // Multiple..
Frequency Counter1(서로의 숫자 빈도수가 맞는지 확인) 1. sameFrequency라는 함수를 만드십시오. 2개의 정수에서 서로 같은 빈도수와 숫자가 같은 확인하는 함수를 만드십시오. 해답에서는 시간 복잡도가 O(N)이어야 합니다. sameFrequency(182, 281) // true sameFrequency(35989578, 5879385) // true sameFrequency(288, 134) // false 해답 function sameFrequency(num1, num2){ let strNum1 = num1.toString(); let strNum2 = num2.toString(); if(strNum1.length !== strNum2.length){ return false; } let countNum1 = {}; let countNum2 = ..
Divide and Conquer 정의 - 이 패턴은 큰 데이터를 작은 크기로 나눈 다음 작은 데이터들을 반복해서 푸는 형식이다. - 이 패턴은 배열에 많은 데이터나 리스트에 많은 데이터인 경우 시간 복잡도를 많이 줄일 수 있다. 예시] 아래 처럼 정렬된 정수과 오른쪽에 숫자를 보면서 오른쪽 숫자의 인덱스를 반환하시고 만약 숫자가 없으면 -1로 반환 하시오 search([1,2,3,4,5,6], 4) // 3 search([1,2,3,4,5,6], 6) // 5 search([1,2,3,4,5,6], 11) // -1 좋지 않는 해답 function search (arr, val) { for(let i = 0; i < arr.length; i++) { if ( arr[i] === val ) { return i; } } return -1;..
Sliding Window (슬라이딩 윈도우) Defintion - This pattern involves creating a window which can either be an array or number from one position to another - Depending on a certain condition, the window either increases or closes (and a new window is created) - Very useful for keeping track of a subset of data in an array/string etc. Ex] Write a function called 'maxSubarraySum' which accepts an array of integers and a number calle..

티스토리툴바