알고 있지만 쉽지 않았던... 들어봤지만 구현하기 어려운...
위 문제는 몇가지 알고리즘(?)을 조합해서 푸는 문제였다. 하지만 DFS... 여기서 발목을 잡았고, 그로 인해 DFS를 복습할 수 있는 시간이 되었다. 또한 소수를 구하는 알고리즘은 다시 복습삼아 여러가지 방법에 대해서 정리해보았다. 특히 가장 효율적이라고 불리우는 에라토스테네스의 체의 방법은 볼 때마다 기억이 잘 안난다...흑흑 😓
DFS, 이젠 좀 잘할 수 있을 때가 되지 않았니?!
이해가 잘안될땐 도식화해보자!! INPUT "17" 인 경우를 아래 코드에서 변수의 흐름에 대입하여 dfs함수가 어떤 식으로 돌아가는지 도식화시켜보겠다.
→ 문자열 17로 만들 수 있는 숫자는??
손으로 과정을 그려보면 코드가 어떤식으로 동작하는지 좀 더 정확히 이해할 수 있는 것 같다.
function solution(numbers) {
const checked = [];
const result = new Set();
const dfs = (s) => {
if (s.length > numbers.length) return; // 사실 이 조건 필요없음
result.add(Number(s));
for (let i = 0; i < numbers.length; i++) {
if (!checked[i]) {
checked[i] = 1;
dfs(s + numbers[i]);
checked[i] = 0;
}
}
};
dfs('');
return [...result].filter(isPrime).length;
}이 코드는 48번 문제를 풀고 나서 다시 수정한 코드이다. 좀 더 DFS에 대한 이해가 높아진 상태!
소수란 1과 자기자신으로만 나눠지는 수를 말한다. 대표적으로 3가지 방법으로 소수를 구할 수 있다. 아래 코드는 1 ~ n 까지 중에서 소수의 개수를 구하시오 or n이 소수인지 여부를 판별하시오 라는 문제를 구현한 것이다.
- 기본적인 방법 : 모두 순회!
-
n이 소수인지 여부 판별 → 시간복잡도 O(n)
-
n개의 수 중에서 소수인 것을 판별 → 시간복잡도 O(n^2) → 이런 경우 3번 방법을 사용해야한다
function solution(n) { let count = 0; for (let i = 1; i <= n; i++) { if (n % i === 0) count++; } console.log(count); return count === 2 ? true : false; }
- Math.sqrt() 이용
-
1번보다 좀 더 효율적인 방법
-
a * b = n으로 할 때, 자기 자신을 제외한 가장 큰 약수는 제곱근까지이다. 그렇기 때문에 자기자신을 제외하고 제곱근까지만 순회하여 나눠지는지 여부를 판별하면 된다.
function solution3(n) { let count = 0; for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i === 0) count++; } console.log(count); return count === 1 ? true : false; // 1이면 소수, 자기 자신을 카운팅에서 제외 }
- 배수를 제거하는 것이 포인트!
function solution(n) {
const checked = Array.from({ length: n + 1 }, (_, i) => i); // 체크배열
for (let i = 2; i <= n; i++) {
if (!checked[i]) continue;
for (let j = 2 * i; j <= n; j += i) {
checked[j] = 0;
}
}
console.log(checked); // 소수만 남겨짐
return checked.slice(2).filter(Boolean).length; // slice(1) : 소수가 아닌 수인 1 제외 / 소수가 아닌 곳(0으로 체크된 부분) 제외
}