Today I Learned/알고리즘

[알고리즘] 소수 판별하기

소수란? 소수란 1과 자신만으로 나누어 떨어지는 1보다 큰 양의 정수를 뜻한다. 2, 3, 5, 7, 11, 13 ... 와 같은 수는 소수가 된다. 소수를 구하는 방법에 대해 알아보자. n까지 모두 판별하기 1이 아닌 2부터 n사이의 모든 정수를 다 확인하는 방법 const isPrime = (n) => { for (let i = 2; i < n; i++) { if (n % i === 0) { return false; } } return true; } n의 제곱근 (√n) 까지만 계산하기 n의 제곱근 (√n) 값으로 나누어 떨어지면 √n의 배수라는 뜻이므로 소수가 아니게 된다. 예를 들어 25의 제곱근은 √25(5) 이다. 이때 5까지만 반복문이 돌아가더라도 25는 5의 배수이므로 i가 5일 때 나누어..

[알고리즘] 조합, 순열, 중복순열

조합, 순열, 중복순열은 모두 같은 로직으로 진행한다. 배열에서 3개를 선택하는 경우 1. 하나의 수를 선택한다. 2. 3개를 뽑는 순열 중 하나의 수를 선택했으니 남은 배열에서 2개를 선택해야한다. 3. 남는 배열에서 1개를 선택할 때 까지(재귀 탈출 조건) 2번 과정을 재귀적으로 반복한다. 이 세 과정을 반복하면 조합, 순열, 중복순열을 구할 수 있다. 조합, 순열, 중복순열들은 서로 남은 배열을 설정해주는 과정에서 차이가 있다. 알고리즘에 잘 적용 해보자! 조합 function combination(arr, n, bucket){ if(n===0){ // 탈출조건 result.push(bucket) return; } for(let i=0; i