2016년
점프와 순간이동

공부하며 느낀 점
참조한 페이지

2016년

달력을 불러오는법을 찾아야겠다.

나의 풀이

function sol0(a, b) {
    const week = ['SUN','MON','TUE','WED','THU','FRI','SAT']

    const date = `2016-${a}-${b}`

    const weekDigit = new Date(date).getDay()

    const answer = week[weekDigit]

    return answer;
}

특별할것없이 자바스크립트 내장 기능으로 풀었다.

다른 사람의 풀이

function sol1(a,b){
    var tempDate = new Date(2016, a-1, b);

    return tempDate.toString().slice(0,3).toUpperCase();
}

Date에 넣기전에 꼭 변환할 필요가 없었던것같다.

거기에 Date라는 객체를 String으로 바꾸면 모양이 바뀌는 것도 알게 되었다. 예전에 비슷한 것 때문에 의문이었는데 이제 좀 알것같다.

과제하며 배운 것 들
약간의 배경공부

function sol2(a, b) {
    const monthDay = [31,29,31,30,31,30,31,31,30,31,30,31]
    const weekDay = ["THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"]

    let days = b
    for(let i=0 ; i<a-1 ; i++)
        days += monthDay[i];

    return weekDay[days%7];
}

2016년의 월들의 일수 그리고 2016-01-01의 요일을 바탕으로 구하는 방식이다.

function sol00(a, b) {
    const week = ['SUN','MON','TUE','WED','THU','FRI','SAT']


    const weekDigit = new Date(2016,a-1,b).getDay()

    const answer = week[weekDigit]

    return answer;
}

내 코드를 조금 고친것이다.

속도 비교

날짜라는 특성상 입력값을 10배로 늘린다거나 하는것이 불가능 하기 때문에 반복횟수만 증가 시켰다.

내코드는 당연히 중간 단계를 하나 줄인게 더 빨랐고

sol1의 경우 slice toUpperCase 같은 메서드를 많이 써서인지 느리다.

sol2의 경우 상상이상으로 매우 빠르다.
문제라면 2016년에만 적용이 가능하다는 것이다.

점프와 순간이동

k1 만큼 움직이고 k12로 움직이고
k2 만큼 운직이고 (k12+k2)*2 로 움직이고...

를 반복하는 것같다.

2배 거리만큼 더 움직이는게 아니라 2배 거리가 되는 것이고 두번 움직여햐하니 parseInt(1/4) 거리 만큼 움직이면 될 것같다.

해보니까 안된다.
직관만 가지고 다됐으면 내가 천재겠지.

GPT의 풀이

하다보니 반복문을 너무 중첩시키기만해서 안된다.

function sol0(n){
    let N = 0;

    while (n > 0) {
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n -= 1;
            N++;
        }
    }

    return N;
}

시작점이 아니라 도착점에서 시작한다.
이 문제는 점점 크게 불려야하기 때문이다.

2배씩 이동하기 때문에 parseInt(1/2) = n%2 움직이고 나머지가 있으면 1빼서 짝수로 만들어준다. 한칸 움직였으니 +1 칸이다.

다른 사람의 풀이

function sol1(n) { var ans = 0; while (n > 0) { n &= (n - 1); ans++; } return ans; }

GPT가 준 것을 한줄로 요약한 것

function sol2(n){
    if(n === 1) return 1;
    const nArr = Array.from(n.toString(2));
    return nArr.reduce((a,b)=>(+a)+(+b));
}

2진수로 변환하고 1들을 더한 것이다.
발상 자체는 위에 GPT가 만들어 준것과 비슷한것같다.

function sol3(n)
{
    return n.toString(2).replace(/0/g,"").length
}

발상 자체는 sol1과 같지만 1의 갯수를 세는 법이 다르다.

속도 비교

sol1의 시간 복잡도는 $O(K)$, (K는 n을 2진수로 바꿨을때 1의 갯수)
나머지는 $\log{N}$이다.

반복 속도 100배 증가

입력 길이 10배 증가

$\log{N}$ 이라서 거의 1배가 증가하는 것같다.

뭔가 내 생각과 다르다. 분명 증가하고 있긴한데 10진수를 2진수로 바꿔서 $\log{N}$의 시간이 걸리는 것이 아닌 다른 무언가가 있는 것같다.

확실하다... 그런데 대체 무엇인지 모르겠다.

$\log{100000000} = 8$ 인데 9.86배라니...
사실 반복시키는 것이기 때문에 반복 사이사이에 들어간 시간도 있겠지만 오차가 너무 큰것같다.

아무튼 대체적으로 크지 않게 증가하는것같다.

아마도 반복문 안에 비트연산 >>>>>>>>>>>>>>>> 반복문 안에 if문 정도의 속도차이가 있고 그 사이에 toString, Array, replace등의 메서드들을 어떻게 조합하느냐에 따라서 속도 차이가 나는것같다.

공부하며 느낀 점

1. 이미 검증된 라이브러리를 쓰면 코드 구현이 쉽고, 범용성이 올라간다.
2. 반대로 특정한 조건내에서만 사용할 목적이라면 스스로 코드를 짜는 것이 더 빠를 수 있다.
3. 2진법과 관련된 문제일때 비트 연산자는 매우 빠른 해답을 제공해준다.

참조한 페이지

요일 구하기
[JavaScript] 요일 구하기