JavaScript - 프로그래머스 레벨 : 2(6) - ORDER BY '정답률'

먹보·2023년 3월 9일

JavaScript Javascript 코딩테스트 코딩테스트 프로그래머스

JavaScript - Coding Test (Programmers)

목록 보기

52/61

1. 점프와 순간 이동

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.

처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.

처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

예제

코드

function solution(n) {
    let count = 0;
    
    while(n != 0){
        if (n % 2 == 0){
            n = n/2
        } else {
            n--
            count++
        }
    }
    return count
}
// 다른 사람의 풀이 법
function solution(n){
    if(n === 1) return 1;
    const nArr = Array.from(n.toString(2));
    return nArr.reduce((a,b)=>(+a)+(+b));
}

🗒️코멘트

문제 자체의 난이도는 굉장히 낮았다. 최대한 2로 나누는 것을 목표로 접근을 하였고 만약 2로 나눌 수 없다면 바로 1을 빼는 방식을 적용했더니 금방 풀린다.

다른 사람들이 어떤 식으로 접근을 했는지 풀이법을 보았을 때, 2진법으로 변환한 것은 충격적이었다.

저 식 자체를 수학적으로 생각했을 때 2진법 풀이 과정은 정말 혁신적인 것이다.

특정 수를 2진법으로 변환한 뒤 그 변환된 2진법의 1의 갯수가 바로 1을 몇 번 뺐는지와 동일하기 때문이다.

1을 뺀 이유가 애초에 나머지를 없애는 것이니 말이다.

수학을 다시금 배우고 싶게 만드는 해결법이다.

2. 멀리 뛰기

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

예제

코드

function solution(n) {

    let fibo_list = [];
    fibo_list[0] = 1;
    fibo_list[1] = 1;
    fibo_list[2] = 2;
    for (let i = 3; i <= n; i++) {
        fibo_list[i] = (fibo_list[i-1]%1234567 + fibo_list[i-2]%1234567);
    }
    
    return fibo_list[n]%1234567;
}
// Recursive Solution
function solution(n) {
    const MODULO = 1234567;

    function fibonacci(num) {
        if (num < 2) {
            return 1;
        }
        let fibo = (fibonacci(num-1) + fibonacci(num-2)) % MODULO;
        return fibo;
    }

    return fibonacci(n);
}

🗒️코멘트

항상 코딩테스트 문제를 풀 때면, 예제부터 만드는 경향이 있고 이번에도 역시 예제부터 만들었다.

n = 1 => 1
n = 2 => 2
n = 3 => 3
n = 4 => 5
n = 5 => 8
n = 6 => 13
n = 7 => 21
...

이렇게 예제를 나열하다보니...엇!!! 피보나치 수열이네 라는 사실을 깨닫고 바로 기존에 만들었었던 피보나치 수열을 조금 수정 하여 적용하였다.

그리고 한 번 재귀함수로 만들어보았는데 런타임 에러가 나서 조사를 해본 결과 재귀 함수에는 다음과 같은 결함이 있다.

Function Call Overhead : 함수가 여러번 호출 되다보니 함수에 사용된 매개변수나 지역 변수들을 위한 공간이 확보되어야 하고 함수가 끝날 때 확보된 공간이 다시 비어지게 되는데 재귀 함수는 이 과정을 반복하다 보니 Overhead 현상이 나타난다.
반복 계산 : 피보나치 수열을 예를 들어보자, 위에서 만든 함수를 가져와보면 fibonacci(5)를 계산하기 위해서는 fibonacci(4)와 fibonacci(3)을 계산해야 하고 fibonacci(4)를 계산하기 위해서는 fibonacci(3)과 fibonacci(2)를 계산해야 한다. 이처럼 이미 계산했던 결과를 또 다시 계산해야 하는 사태가 벌어지고 계산해야 하는 값이 커질 수록 비효율적이게 되는 것이다.
STACK OVERFLOW : 재귀 함수는 호출 될 때마다 콜 스택에 새로운 스택을 더하게 되는데 이로 인해 메모리를 사용하게 된다. 만약 반복되는 횟수가 많아지게 되면 콜 스택이 과도하게 쌓이게 되고 스택 오버플로우 현상이 일어날 수 있다.