점프와 순간이동 문제 — 탐욕 알고리즘

이진수로 바라보는 깔끔한 그리디 풀이

By 전경원
Posted on April 14, 2026

코딩테스트 문제 중에서 첫 인상이 무척 어려운 문제인데, 접근 방향을 바꾸면 깔끔하게 풀리는 문제들이 있다. 이번 글에서는 점프와 순간이동 문제를 이진수로 바라보는 탐욕 알고리즘 풀이를 소개한다.

🧩 문제

두 가지의 이동 방식이 있다.

  • 앞으로 1칸 이동 → 비용 1
  • 현재 위치의 2배로 이동 → 비용 0

목표는 0에서 시작해서 N까지 가는 것. 단, 총 비용을 최소화해야 한다.

💡 풀이 1: 직관적인 방식

이 문제는 0에서 N으로 가는 것이 아니라 N에서 0으로 거꾸로 내려오는 방식으로 생각하면 훨씬 쉽다.

N이 홀수라면, 마지막 상태는 반드시 +1로 만들어졌어야 한다. 왜냐하면 순간이동(×2)은 짝수만 만들 수 있기 때문이다. 따라서 N이 홀수일 때는 비용이 1 증가하고, N에서 1을 빼서 짝수로 만들어야 한다. 반면에 N이 짝수라면, 순간이동을 하는 것이 비용이 0이므로, N을 2로 나누어서 순간이동을 하는 것이 최적이다. 이렇게 N이 0이 될 때까지 반복하면 된다.

public class Solution
{
    public int solution(int n)
    {
        int cost = 0;

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

        return cost;
    }
}

예를 들어 n = 5라고 해보자.

5 → 4 → 2 → 1 → 0

- 5 (홀수) → -1 (비용 1)
- 4 (짝수) → /2
- 2 (짝수) → /2
- 1 (홀수) → -1 (비용 1)

총 비용은 2가 된다. 이 과정을 보면 홀수일 때만 비용이 발생한다는 것을 알 수 있다.

반복할 때마다 n이 반으로 줄어드는 경우가 많으므로 시간 복잡도는 $O(\log N)$이 된다. 그리고 추가로 사용하는 변수는 cost 하나뿐이므로 공간 복잡도는 $O(1)$이다.

  • 시간 복잡도: $O(\log N)$
  • 공간 복잡도: $O(1)$

🔍 풀이 2: 이진수로 바라보기

여기서 한 가지 중요한 사실을 관찰할 수 있다. 앞선 과정을 자세히 보면, 비용이 증가하는 순간은 오직 n이 홀수일 때 뿐이다. 그런데 이걸 이진수로 보면 더 명확해진다.

  • 짝수 → 마지막 비트가 0
  • 홀수 → 마지막 비트가 1

즉, 비용이 발생하는 순간은 이진수에서 1인 자리와 정확히 대응한다. 그래서 결국 이 문제는 이진수에서 1의 개수를 세는 문제로 바뀐다. 앞선 풀이로 n의 이진수 표현에서 1의 개수만 세면 된다는 것을 알았다. 그래서 더 단순화할 수 있다.

public int solution(int n)
{
    int cost = 0;
    while (n > 0)
    {
        cost += n & 1;  // 마지막 비트 확인
        n >>= 1;
    }
    return cost;
}

n & 1은 n의 마지막 비트가 1인지 확인하는 방법이다. 그리고 n >>= 1은 n을 오른쪽으로 한 비트씩 이동시키는 연산으로, 이는 n을 2로 나누는 것과 같다. 이렇게 하면 n의 모든 비트를 순회하면서 1의 개수를 세게 된다.

  • 시간 복잡도: $O(\log N)$
  • 공간 복잡도: $O(1)$

✂️ 풀이 3: 더 짧게

LINQ를 사용해서 더 직관적이면서도 짧게 표현할 수도 있다.

using System;
using System.Linq;

public int solution(int n)
{
    return Convert.ToString(n, 2).Count(c => c == '1');
}

이 코드는 아주 직관적이다.

  • 숫자를 이진수 문자열로 바꾸고,
  • 그 문자열에서 ‘1’의 개수를 센다.

하지만 단점이 있다. Convert.ToString(n, 2)는 정수 n을 이진수 문자열로 변환한다. 즉, $O(\log N)$ 길이의 문자열을 생성하게 되므로 메모리 사용이 증가한다. 그리고 Count(c => c == '1')은 이 문자열에서 ‘1’의 개수를 세는 작업으로, 내부적으로 IEnumerable<char>를 순회하며 delegate 호출을 반복하게 되므로 일반 반복문보다 오버헤드가 크다. 즉, 간단하지만 비효율적인 구현이다.

  • 공간 복잡도: $O(\log N)$
  • 시간 복잡도: $O(\log N)$

✅ 정리

  • 점프와 순간이동 문제는 N에서 0으로 거꾸로 내려오는 방식으로 생각하면 쉽게 풀 수 있다.
  • N이 홀수일 때만 비용이 발생한다는 것을 알 수 있다.
  • 결국 이 문제는 N의 이진수 표현에서 1의 개수를 세는 문제로 바뀐다.
  • 가장 효율적인 방법은 비트 연산을 사용하는 것이다. LINQ를 사용한 방법은 간단하지만, 비효율적이므로 실제 코딩테스트에서는 피하는 것이 좋다.
Tags: algorithm greedy csharp codingtest
Share: LinkedIn