개발/알고리즘

[알고리즘] 재귀함수

1. 재귀함수 (1) 재귀함수란? - 재귀함수란 자기자신을 호출하는 함수이다. (2) 재귀의 기본요소 - 종료조건 - 매번 다른 입력값 (3) 재귀의 위험요소 - 종료조건이 없는경우 : 계속 반복 - return을 하지 않은 경우 - 스택 오버플로우 : 재귀호출이 멈추지 않는 경우 2. 콜스택 예시 function takeShower() { return "Showering!"; } function eatBreakfast() { let meal = cookFood(); return `Eating ${meal}`; } function cookFood() { let items = ["Oatmeal", "Eggs", "Protein Shake"]; return items[Math.floor(Math.random..

[알고리즘] 문제 모음

1. FrequencyCounter 문제 두개의 정수가 주어진다. 두 수가 같은 숫자를 포함하고 있는지 확인하는 함수 조건 : 시간복잡도 O(n) 예시 : console.log(sameFrequency(182, 281)); // true console.log(sameFrequency(34, 14)); // false console.log(sameFrequency(3589578, 5879385)); // true console.log(sameFrequency(22, 222)); // false 풀이 function sameFrequency(num1, num2) { const obj1 = {}; num1 = num1.toString(); for (let i = 0; i < num1.length; i++) {..

[알고리즘] 연속된 수를 더해서 가장 큰 값 찾기

문제 배열안에 있는 요소중 연속된 num개 만큼 뽑아 더한다. 더한값중 가장 큰값을 찾는 함수만들기 예시 : maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3); 풀이 (1) 1번 풀이 function maxSubarraySum(arr, num) { if (num > arr.length) { return null; } var max = -Infinity; for (let i = 0; i max) { max = temp; } } return max; } 시간 복잡도 : O(n^2) (2)..

[알고리즘] 배열에 중복되지 않는 요소 개수 찾기

문제 배열에 중복되지 않는 요소들의 개수를 찾는다. 조건 : 시간복잡도 O(n), 공간복잡도 O(n) 예시 countUniqueValues([1, 1, 1, 1, 1, 2]); // 2 countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]); // 7 countUniqueValues([]); // 0 countUniqueValues([-2, -1, -1, 0, 1]); // 4 풀이 function countUniqueValues(arr) { let i = 0; for (let j = 1; j < arr.length; j++) { if (arr[i] !== arr[j]) { i++; arr[i] = arr[j]; } } return i + 1; }

[알고리즘] 다중 포인터

문제 배열에 연속한 둘을 더해 0이 되는값이 있다면 그 두값을 return하는 함수를 만든다. 배열의 요소들은 오름차순으로 정렬되어있다. 예시 sumZero([-4, -3, -2, -1, 0, 1, 2, 5]); 풀이 (1) 1번풀이 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]]; } } } } 2중 for문을 돌려 시간복잡도가 O(n^2)이다. (2) 2번풀이 function sumZero(arr) { let left = 0; let right = arr.length ..

[알고리즘] anagram

애너그램은 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것이다. 문제 두개의 문자열이 주어진다. 두 문자열의 요소는 같지만 순서만 뒤바껴있는지 확인하는 함수를 만든다.조건 : 시간복잡도 O(n) 예시 : validAnagram("", ""); // true validAnagram("aaz", "zza"); // false validAnagram("anagram", "nagaram"); // true validAnagram("rat", "car"); // false) // false validAnagram("awesome", "awesom"); // false validAnagram("amanaplanacanalpanama", "acanalmanplanpamana"); //..