JavaScript로 m에서 n까지 도달하는 데 필요한 최소 연산 횟수 구하기

문제 개요

두 개의 숫자 m과 n을 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 오직 다음 두 가지 연산만을 사용하여 화면의 숫자를 m에서 n으로 바꿀 때 필요한 최소 연산 횟수를 계산해야 합니다.

• 두 배(Double) − 화면에 표시된 숫자에 2를 곱합니다.
• 감소(Decrement) − 화면에 표시된 숫자에서 1을 뺍니다.

예를 들어, 함수의 입력이 다음과 같다면 −

const m = 5;
const n = 8;

출력은 다음과 같아야 합니다 −

const output = 2;

출력 설명

필요한 연산 과정은 다음과 같습니다 −

5 → 4 → 8

먼저 5에서 1을 빼 4를 만들고(감소 연산 1회), 이어서 4에 2를 곱해 8을 만들면(두 배 연산 1회) 정확히 2번의 연산으로 목표값에 도달할 수 있습니다.

접근 방식: 역방향 탐욕(Greedy) 전략

m에서 출발해 n을 향해 나아가는 대신, n에서 출발해 m을 향해 거꾸로 거슬러 올라가는 것이 훨씬 효율적입니다. n이 m보다 큰 동안 다음 규칙을 적용합니다.

• n이 짝수라면 2로 나눕니다. → 정방향의 '두 배' 연산을 되돌리는 행위입니다.
• n이 홀수라면 1을 더합니다. → 정방향의 '감소' 연산을 되돌리는 행위입니다.

이 과정을 반복하면 n이 결국 m 이하가 되는데, 이 시점부터는 두 값의 차이(m - n)만큼 감소 연산을 추가로 수행하면 됩니다. 매 단계에서 가능한 한 빠르게 값을 줄여나가므로 이 방법이 항상 최소 연산 횟수를 보장합니다.

예제 코드

const m = 5;
const n = 8;
const findOperations = (m, n) => {
    let res = 0;
    while(n > m){
        if(n % 2 === 0){
            n /= 2;
        }else{
            n += 1;
        };
        res += 1;
    };
    return res + m - n;
};
console.log(findOperations(m, n));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

2