본문 바로가기

Algorithm8

isSubsetOf - 문제 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다. - 조건 시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과 const isSubsetOf = function (base, sample) { // 값이 있으면 COUNT +1 길이만큼 있으면 RETURN TRUE // 배열 값을 정렬 // 숫자 크기 비교 38 55 이후X // 있다면 BASE 원소 제거 // 가운데 숫자 비교해서 // 처음 과 끝 사이에 포함되는 숫자인지 판별 // 가운데 처음 끝 어디서 가까운지 판별해서 찾기 시작 // 왼쪽 탐색인지 오른쪽 탐색인지 구별 base.sort((a, b) => a - b);.. 2022. 5. 24.
fibonacci 피보나치 수열은 아래와 같은 특징을 가지고있다 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 재귀 형태로 호출시 아래와 같이 트리 구조로 호출이 되면 O(n^2) 형태로 표현이 된다 위 그림 처럼 사용시 불필요한 메모리를 차지한다 아래 그림처럼 불 필요 한걸 제거한다면 O(N) 형태로 아래와 같이 코드 작성이 가능하다 function _fibonacci(n, memo) { if ((memo[n] != 0) && (memo[n] != undefined)){ // 기록한거 사용 return memo[n]; } else // 기록이 없을시.. 2022. 5. 23.

티스토리툴바