JavaScript로 숫자를 1까지 줄이는 최소 연산 횟수 구하기

문제 정의

숫자 num을 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

함수가 사용할 수 있는 연산은 다음 두 가지뿐입니다.

• num이 짝수라면, num을 num / 2로 대체할 수 있습니다.
• num이 홀수라면, num을 num + 1 또는 num - 1 중 하나로 대체할 수 있습니다.

이 두 연산만 조합하여 숫자를 1로 만들 때 필요한 최소 연산 횟수를 계산하고, 그 값을 반환해야 합니다.

예시

입력이 다음과 같다고 가정해 보겠습니다.

const num = 7;

그렇다면 출력은 다음과 같아야 합니다.

const output = 4;

출력 설명

7을 1로 만드는 가장 적은 연산 과정은 아래와 같습니다.

7 -> 8 -> 4 -> 2 -> 1
또는
7 -> 6 -> 3 -> 2 -> 1

두 경로 모두 총 4번의 연산으로 1에 도달하므로, 최솟값은 4입니다.

접근 방법

이 문제는 각 단계에서 가능한 모든 경우의 수를 탐색하며 목표(1)에 가장 먼저 도달하는 경로를 찾는 전형적인 BFS(너비 우선 탐색) 문제로 풀 수 있습니다. 큐를 활용해 현재 값과 누적 연산 횟수를 함께 저장하고, 이미 방문한 값은 Set으로 관리하여 불필요한 중복 탐색을 제거하면 효율적으로 해결할 수 있습니다.

구현 코드

const num = 7;
const downToOne = (num = 1) => {
   let min = Number.POSITIVE_INFINITY;
   let stack = [{ num: num, step: 0 }];
   let set = new Set();
   let next;
   let item;
   while (stack.length) {
      item = stack.shift();
      // 1에 도달했다면 최소 연산 횟수 갱신
      if (item.num === 1) {
         if (min > item.step) {
            min = item.step;
         }
         continue;
      }
      // 이미 방문했거나 현재 최솟값보다 연산 횟수가 많으면 건너뜀
      if (set.has(item.num) || item.step >= min) {
         continue;
      }
      set.add(item.num);
      next = item.step + 1;
      if (item.num % 2 === 0) {
         // 짝수인 경우: 2로 나눔
         item.num /= 2;
         stack.push({ num: item.num, step: next });
      } else {
         // 홀수인 경우: +1과 -1 두 가지 경로 모두 탐색
         stack.push({ num: item.num - 1, step: next });
         stack.push({ num: item.num + 1, step: next });
      }
   }
   return min;
};
console.log(downToOne(num));

실행 결과

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

4

정리

이 알고리즘은 BFS를 기반으로 하기 때문에 목표 지점(1)에 도달하는 순간의 연산 횟수가 곧 최솟값이 됩니다. 여기에 방문 여부를 저장하는 Set과 이미 발견된 최솟값보다 큰 경로를 조기에 차단하는 가지치기(pruning)를 더하면, 큰 입력값에서도 빠르게 동작합니다. 홀수일 때 +1과 -1 양쪽을 모두 시도하는 것이 핵심 포인트이며, 이 덕분에 예외적인 경우(예: 3처럼 -1이 유리한 값)도 정확하게 처리할 수 있습니다.