JavaScript/Algorithm (13) 썸네일형 리스트형 알고리즘 출제빈도순 수정중입니다 보호되어 있는 글입니다. [Algorithm] 알고리즘의 공간 복잡도(Space Complexity)란? 1. 정의공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리의 양을 나타냅니다. 전체 공간 복잡도 = 입력 공간 + 보조 공간 으로 나뉘지만 알고리즘 자체의 공간 복잡도에 집중해야 보조 공간 (auxiliary space complexity) 메모리 효율성 평가에 유용하며 입력 크기와 무관한 추가 메모리 사용을 명확히 파악 가능하므로여기서는 입력 되는 크기는 제외하고 알고리즘 자체가 얼마나 많은 추가 메모리가 필요한지를 측정합니다. 2. 표기법보통 빅오(Big O) 표기법을 사용합니다. 예: O(n), O(1), O(n^2) 등3. 종류고정 공간: 입력 크기와 무관한 상수 공간 가변 공간: 입력 크기에 따라 변하는 공간 4. 예시 4-1. O(1) 공간 복잡도 예시function findMax(arr.. [프로그래머스] Lv1) 소수 찾기 ( 에라토스테네스의 체, 소수 찾기 ) 1 부터 n 까지의 수 중에서 소수의 개수를 반환하는 문제 입니다이전 Lv1) 기사단원의 무기 문제에서 사용한 에라토스테네스의 체를 다시 이용하면 됩니다. function solution(n) {// idx 자체를 값으로 사용하기 위해 let isPrime = new Array(n + 1).fill(true); isPrime[0] = isPrime[1] = false;// 제곱근 까지만 계산 for (let i = 2; i * i e === true).length;} 제곱근 까지만 계산하는 이유는 아래 링크에 설명 되어있습니다.https://daunje0.tistory.com/135 limit ? power : e).reduce((a,b) => a+b);}이 코드는 시간복잡도가 O.. [프로그래머스] Lv1) 기사단원의 무기 ( 에라토스테네스의 체, 소수 , 약수 찾기 ) 이 문제는 약수 찾기의 문제입니다function solution(number, limit, power) { let arr = [] let count = 0 for(let i = 1; i e > limit ? power : e).reduce((a,b) => a+b);}이 코드는 시간복잡도가 O(n^2)이기에 시간초과로 fail 이 된 경우 입니다.시간 복잡도를 줄이기 위해서는 에라토스테네스의 체를 이용해야한는 것을 검색을 통해 힌트를 얻었습니다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두.. 두 수의 최대 공약수, 최소 공배수 구하기 (유클리드 호제법, 자바스크립트) 코테 준비를 하다보면 두 수의 최대 공약수를 구해야 하는 경우가 보인다. a = 100, b = 30 두수가 있을 때, a = b * x + y 에서 기존 b 에 a 를 넣고 b 자리에는 y를 넣어 반복 하고y가 0일 때의 b값이 최대 공약수가 된다 100 = 30 * 3 + 10 => a 에 30 b 에 나머지 10치환30 = 10 * 3 + 0 => 나머지 0 이므로 10이 최대공약수 가 된다. 코드화하면const GCD = (a, b) => { if (b === 0) return a; return GCD(b, a % b); };위 처럼 재귀함수화 하여 파라미터의 a 자리에 b를 대입하고, b 자리에는 나머지를 넣어주면 된다. 그럼 최소공배수를 구하는 법은? 두 수 a와 b의 .. 이전 1 2 다음
