Skip to content

Latest commit

 

History

History
144 lines (113 loc) · 4.83 KB

29.md

File metadata and controls

144 lines (113 loc) · 4.83 KB

기사단원의 무기

결국 약수를 효율적으로 구하는 방법에 대한 것

약수 구하는 방법

  1. 가장 일반적

    1 ~ n 까지 중에서 n과 나눠지는 수를 찾아라 라는 관점에서 구현한 코드이다. n의 약수를 구하는 것이라면 1 ~ n 까지 순회를 하게 된다. 1 ~ n 까지의 수에 대한 각각의 약수를 구한다면, O(n^2)의 시간 복잡도를 갖게 된다.

    function solution1(n) {
  const divsors = [];
  for (let i = 1; i <= n; i++) {
    if (n % i === 0) divsors.push(i);
  }
  return divsors.length;
}

  2. 약간 효율적

    자기 자신을 제외한 약수 중에서 가장 큰 약수까지 순회한다 라는 것이 포인트. n에 대한 약수 중에서 n / 2로 했을 때 나눠지는 값보다는 무조건 작거나 같다. (그 다음으로 나눠지는 큰 수가 n / 1 (자기 자신) 이기 때문이다.)

    function solution2(n) {
  const divsors = [n];
  for (let i = 1; i <= n / 2; i++) {
    if (n % i === 0) divsors.push(i);
  }
  return divsors.length;
}

  3. 매우 효율적

    n = a * b 일 때, a, b는 n의 약수이다. 이 관점에서 접근한 코드이다. 그래서 순회해야할 최대의 수는

    function solution3(n) {
  const divsors = [];
  for (let i = 1; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      divsors.push(i);
      if (n / i !== i) divsors.push(n / i);
    }
  }
  return divsors.length;
}

효율성 체크해보기!

위 3가지 코드가 얼마만큼의 효율성의 차이를 보이는지 체크해 보았다. 아래는 효율성을 체크해본 코드 스니펫이다.

const t1 = performance.now();
for (let i = 0; i < 1000000; i++) {
  solution1(10000);
}
const t2 = performance.now();
console.log('performance1', t2 - t1);

const t3 = performance.now();
for (let i = 0; i < 1000000; i++) {
  solution2(10000);
}
const t4 = performance.now();
console.log('performance2', t4 - t3);

const t5 = performance.now();
for (let i = 0; i < 1000000; i++) {
  solution3(10000);
}
const t6 = performance.now();
console.log('performance3', t6 - t5);

performance.now() 대신 console.time()을 통해서 체크해도 관계없다. 전자가 후자에 비해 좀 더 높은 정확도(천분의 일 밀리초까지 측정)를 보장하고 사용방법에 약간 불편하다는 차이점이 있다.

각각 10000에 대한 약수 구하는 코드를 100000번 반복하였다. 즉 시간복잡도는 10000 * 100000 = 10000000000(백억)이 된다. 결과는 아래와 같다.

performance1 9065.926332950592  → solution1 = solution2 * 2
performance2 4580.670459032059  → solution2 = solution3 * 30
performance3 155.74899995326996  → solution3

결과값에서 보이듯 굉장한 차이를 보여준다.(CPU환경 등에 따라 결과값이 오차는 있을 수 있다.)

Try

기사단원 문제는 얼마나 효율적으로 약수를 구할 수 있느냐의 문제이다. 그 외에는 문제만 잘 읽는 것이면 족하다고 생각한다. 문제가 약간 길다. 나 같은 경우엔, 맨 윗단락을 보지 않아서 처음에 문제를 이해하는게 어려움을 겪었다. 🥲

function solution(number, limit, power) {
  const arr = [];
  for (let i = 1; i <= number; i++) {
    const divisors = [];
    let count = 0;
    for (let j = 1; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        divisors.push(j);
        if (i / j !== j) divisors.push(i / j);
      }
    }
    arr.push(divisors.length);
  }

  let total = 0;
  arr.forEach((d) => {
    if (d > limit) total += power;
    else total += d;
  });

  return total;
}

이것은 나의 풀이!

그리고 내 풀이와 비교할겸 깔끔한 풀이 하나를 추가해본다.

function solution(number, limit, power) {
  var answer = 0;
  for (let n = 1; n <= number; n++) {
    let count = 0;
    for (let j = 1; j * j <= n; j++) {
      if (j * j == n) count++;
      else if (n % j == 0) count += 2;
    }
    if (count > limit) count = power;
    answer += count;
  }
  return answer;
}

같은 제곱근을 이용한 풀이지만, 코드 자체가 좀 더 가독성이 있다고 느껴진다. 첫번째는 약수를 구하는 두번째 for문이 인상 깊다. 그리고 나는 약수를 배열에 담아서 사용했는데, 그 이유는 j * j == n 이 경우에 대한 체크를 위해서였다. 하지만 보시다싶이 이렇게 연산을 통해서도 확인이 가능했던 것!

두번째는 약수를 구한 결과값을 토대로 다시 순회한 것이 아니라 약수를 구하는 과정 속에서 약수를 다 구한 후에 최종적인 답까지 한번에 연산이 진행된 부분.

역시 코드의 다양성 + 생각의 다양성은 무궁무진하다. 오늘도 멋진 코드를 본 것 같아서 기분이 좋다! 🚀