소수 만들기
멀리 뛰기

공부하며 느낀 점

소수 만들기

• 잠깐 생각해보자 소수가 아닌 수끼리 더해서 소수가 나올 수 있는가?
  3+4 = 7 가능하다...
• 어제 만들었던 특정한 수 보다 작은 소수를 구하는 코드를 쓸 수 있을까?
  아직은 잘 모르겠다.

나의 풀이

function sol0(nums) {
    let answer = 0;
    let sum = 0;
    const length = nums.length;

    nums.sort((a, b) => b - a);

    let i = 0;

    while (i < 3) {
        sum += nums[i];
        i++;
    }

    i = 2;

    let primNumber = [];

    while (i <= sum) {
        if (isPrime(i)) {
            primNumber.push(i);
        }
        i++;
    }

    let p = 0;
    while (p < length - 2) {
        let q = p + 1;

        while (q < length - 1) {
            let r = q + 1;

            while (r < length) {
                let threeNums = nums[p] + nums[q] + nums[r];

                if (primNumber.includes(threeNums)) {
                    answer++;
                }
                r++;
            }
            q++;
        }
        p++;
    }

    return answer;
}

function isPrime(num) {
    let i = 2;
    let numSqrt = parseInt(Math.sqrt(num))
    while (i <= numSqrt) {
        if (num % i === 0) {
            return false;
        }
        i++;
    }
    return true;
}

어제 만든 소수를 구하는 함수를 이용했다.

다른 사람의 풀이

function primecheck(n){
    for(var i=2;i<=Math.sqrt(n);i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;    
}
function sol1(nums){
    var cnt = 0;
    for(var i=0;i<nums.length-2;i++){
        for(var j=i+1;j<nums.length-1;j++){
            for(var w=j+1;w<nums.length;w++){


                    if(primecheck(nums[i]+nums[j]+nums[w])){
                        cnt++;
                    }
            }
        }
    }
    return cnt;
}

소수의 목록을 만드는게 불필요한 행동이었다.

실행 시간 비교

시간복잡도

반복문 3중첩이므로 $N^3$
그리고 소수 여부를 판단하는 함수의 복잡도가 $\sqrt{Max(nums)}$

즉 $O ( N^3 * \sqrt{Max(nums)} )$ 라는 복잡한 방법이 나왔다. $Max(nums)$ 는 최소 1.7이 넘으므로 시간복잡도가 매우 큰 값이 나온 것 같다.

반복 횟수 증가

시간복잡도는 같지만 구체적인 구현을 더 간단하게 한 쪽이 훨씬 빠르다.

입력값 길이 증가

최악의 경우의 수인 10배 증가시켰는데 1000배 증가한 모습이다.

알고리즘을 짠 수학적 근거만큼이나 구체적인 구현도 중요함을 알 수 있다.

입력값 크기 증가

sol1이 오히려 속도가 더 빨라지는데 이유를 모르겠다.

• 처음에는 10배로 했었기 때문에 끝자리수가 0인 수가 소수인지 확인을 해서 빨라진것이라고 생각했다.
  하지만 생각해보면 무조건 그런게 아님을 알 수 있다.

• GPT는 Math.sqrt(n) 의 크기가 일정 수준으로 유지되어서 오히려 빨라진다는데 이건 그냥 ai의 개소리같다. (애초에 틀려먹은 전제지만)이 말대로라면 실행 시간이 특정 값에 수렴해야지 더 줄어들수는 없다.

이유를 알 수 없다.

멀리 뛰기

피보나치 수열을 쓰면 될것같다.

예전에 푼 피보나치 수열 알고리즘

나의 풀이

function sol0(n) {
    var answer = 0;
  let i = 3
  let F = [0,1, 2]

  while (i <= n) {
    F[i] = (F[i - 2] + F[i - 1]) % 1234567;
    i++;
  }
  answer = F[n];

  return answer;
}

그렇다 수학은 신인것이다!

function sol1(n) {
    var answer = 0;
    var dp=[];
    dp[1]=1;
    dp[2]=2;
    for(var i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2] %1234567;
    }
    answer=dp[n];
    return answer%1234567;
}

[0]번 인덱스를 구현할 필요가 없었다. 큰 의미는 없겠지만...

너무 길어서 따로 뺌
이것이 하드 코딩이 멸망편...
범위가 정해진 경우에 한해서는 좋을지도?

속도 비교

시간 복잡도

sol0,sol1 : $O(N)$
sol2 : $O(1)$ 일줄 알았는데 GPT에게 물어보니 배열의 정렬에도 시간이 들기 때문에 $n\log{n}$ 이라고 한다...

반복 횟수 증가

GPT가 준 답으로는 sol2가 젤 증가율이 커야하는데 그렇지 않다.

입력값 크기 증가

아무래도 GPT가 잘못 알려준것같다 $O(1)$이 아닌이상 이런 결과 값이 나올리가 없다.

다시 비교하기

위와 같이 안나누면 00
안에서 나누면 10 밖에서 나누면 01
양쪽다에서 나누면 11 로 네이밍했다.

당연히 값을 미리미리 작게 만드는 10이 빠르다.
의외인 점은 00보다 01이 느리다는 것이다.
큰값을 쌓은다음에 마지막에 처리를 하기 때문에 느린걸까?

공부하며 느낀 점

1. 넣고 싶은 기능이 아니라 필요한 기능을 넣자.
   어제 만들었던 기능이 오늘 만들 알고리즘에 쓸수 있다고 해서 넣는건 좋지 않은 판단이다. 꼭 필요한 기능인지 생각하고 넣자.
2. for문 쓰자...
   while문이 더 빨라서 while문을 썼는데 내가 쓰면서도 복잡해서 오류를 많이 냈다.
   속도차이도 중요하지만 더 중요한건 사람이 읽고 유지보수를 할 수 있느냐 없느냐이다.
3. 루프문을 만들지 말고 함수를 분리하자
   그것이 더 코드를 이해하기가 쉬웠다.
4. 수학은 중요하다.
5. 큰 정수를 다뤄야한다면 미리미리 작게 만들자.
6. 만약에 입력값이 하나의 고정된 결과값을 가지고, 입력값의 범위가 변치 않는다면...
   처음 한 번만 알고리즘을 짜서 결과같을 배열로 저장하고 그것을 불러오는 간단한 함수를 짜는 것이 서비스 속도에서는 좋을지도 모른다.