Decimal to Binary

Q: 10진수를 이진수로 변환하는 시간 복잡도는 얼마인가요?

각 단계에서 숫자가 절반으로 줄어들므로, 이진 숫자 하나당 한 번씩, 즉 약 log2(n) 번 반복문이 실행됩니다. 따라서 시간 복잡도는 O(log n) 이고, 정답 문자열에는 O(log n) 의 공간이 필요합니다. 32비트 정수의 경우 최대 31단계입니다.

Q: 나눗셈 대신 비트 연산을 사용해 이진수로 변환할 수 있나요?

네. n & 1 은 최하위 비트를 가져오고 n >> 1 은 그 비트를 제거합니다. 이는 음수가 아닌 수에 대해 n % 2 와 n / 2 를 사용하는 것과 같습니다. 반복문과 뒤집기는 그대로 유지됩니다. 나눗셈은 설명하기 더 쉽고, 시프트 방식은 저수준 코드에서 흔히 사용됩니다.

입문수학과 시뮬레이션 비트 조작

+10

음이 아닌 정수 n이 주어집니다. 앞에 0이 붙지 않는 0과 1로 이루어진 문자열로 그 이진 표현을 반환하세요. 답이 0으로 시작하는 유일한 수는 0 자체이며, "0"으로 씁니다.

함수

toBinary(n: integer) → string

ninteger: 변환할 숫자
반환값string: 문자열로 표현한 n의 이진수

제약 조건

0 ≤ n ≤ 2³¹-1
내장된 진법 변환을 호출하는 대신 문자열을 직접 만드세요.

예제

입력: n = 13
출력: "1101"
설명: 13 = 8 + 4 + 1. 8, 4, 2, 1의 자릿수에는 각각 1, 1, 0, 1이 들어가며, 이를 읽으면 1101입니다.

입력: n = 0
출력: "0"
설명: 0에는 설정된 비트가 없지만 답에는 여전히 숫자 하나가 필요하므로 빈 문자열이 아니라 "0"입니다.

입력: n = 64
출력: "1000000"
설명: 64는 2^6이며, 64의 자리에는 1 하나가 있고 그 뒤로 32부터 1까지의 자리를 나타내는 0이 여섯 개 이어집니다.

제출 시 숨은 테스트 +16개

후속 질문

같은 루프를 사용해 n을 2부터 16까지의 임의의 진법으로 변환할 수 있나요? 9보다 큰 숫자에는 a부터 f까지의 문자를 사용하세요.

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

이진수는 2의 거듭제곱을 더한 값이며, 각 자릿수는 해당 거듭제곱이 합에 포함되는지를 나타냅니다. 가장 큰 자리부터 2의 거듭제곱을 빼면서 자릿수를 구하거나, 2로 반복해서 나눈 나머지를 아래 자리부터 읽을 수 있습니다. 나눗셈 반복문은 표준적인 방법입니다. 가장 큰 거듭제곱을 먼저 찾을 필요가 없고, 모든 기수에서 같은 방식으로 작동합니다.

위에서 2의 거듭제곱을 빼기

핵심 아이디어

이것은 손으로 변환하는 방법입니다. n에 들어맞는 가장 큰 2의 거듭제곱을 찾으세요. 이것이 첫 번째 숫자인 1입니다. 그런 다음 한 번에 거듭제곱을 하나씩 낮추세요. 그 거듭제곱이 남은 값에 여전히 들어맞으면 1을 쓰고 빼세요. 그렇지 않으면 0을 쓰세요.

13의 경우 가장 큰 거듭제곱은 8입니다. 1을 쓰고 5를 남깁니다. 그런 다음 4가 들어맞으므로 (1, 1을 남김), 2는 들어맞지 않으므로 (0), 1은 들어맞습니다 (1). 숫자를 읽으면 1101입니다. 첫 번째 숫자는 항상 1이므로 앞에 0이 올 수 없습니다.

가장 큰 거듭제곱을 찾을 때는 주의해야 합니다. power가 n을 초과할 때까지 두 배로 늘리면, 다음 거듭제곱이 2^31이므로 n ≥ 2^30일 때 32비트 정수 오버플로가 발생합니다. power ≤ n / 2인 동안에만 두 배로 늘리면 n을 넘어가지 않고 올바른 거듭제곱에서 멈춥니다. 31비트 숫자에는 31단계가 걸리며, 이는 O(log n)입니다.

알고리즘

n이 0이면 "0"을 반환합니다.
power를 1로 설정하고 power ≤ n / 2인 동안 두 배로 늘립니다.
power > 0인 동안: n ≥ power이면 1을 추가하고 n에서 power를 뺍니다. 그렇지 않으면 0을 추가합니다.
power를 절반으로 줄이고 반복합니다.
추가한 숫자들을 반환합니다.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

2로 반복해서 나누기

핵심 아이디어

n의 마지막 이진 숫자는 n이 홀수인지 나타내며, 이는 n % 2입니다. 2로 나누고 나머지를 버리면 모든 숫자가 한 자리씩 오른쪽으로 이동하므로 다음 숫자가 마지막 숫자가 됩니다. 아무것도 남지 않을 때까지 반복하면 가장 낮은 자리부터 모든 숫자를 모을 수 있습니다.

13의 경우: 13은 나머지 1을 남기고, 6은 0을 남기고, 3은 1을 남기고, 1은 1을 남긴 다음 숫자는 0이 됩니다. 나머지는 순서대로 1, 0, 1, 1이며, 역순으로 읽으면 1101입니다. 숫자가 0에 도달하면 반복문이 멈추므로, 기록되는 가장 높은 자리 숫자는 항상 1이며 앞에 0이 붙지 않습니다. 0 자체는 반복문에 들어가지 않으므로 별도의 확인이 필요합니다.

각 단계에서 숫자가 절반으로 줄어들기 때문에 31비트 값은 31단계가 걸리며, 시간 복잡도는 O(log n)이고 숫자 문자열의 공간 복잡도는 O(log n)입니다.

알고리즘

n이 0이면 "0"을 반환합니다.
n > 0인 동안 n % 2를 숫자로 덧붙이고 n을 n / 2를 내림한 값으로 설정합니다.
숫자들이 가장 낮은 자리부터 나왔으므로 순서를 뒤집습니다.
문자열로 반환합니다.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

함정과 경계 사례

반복문은 짧으며, 대부분의 오답은 양 끝에서 발생합니다.

0에 대해 빈 문자열을 반환하는 경우. 0에서는 나눗셈 반복문이 실행되지 않으므로 먼저 확인하세요.
뒤집는 것을 잊는 경우. 나머지는 가장 낮은 자릿수부터 나오므로 6은 110이 아니라 011로 나옵니다.
JavaScript, Lua 또는 PHP처럼 나눗셈 결과가 소수인 언어에서 /를 사용하는 경우. 13 / 2는 6이 되어야 하므로, 버림하거나 정수 나눗셈을 사용하세요.
n을 초과하도록 두 배씩 늘려 가장 큰 거듭제곱을 만드는 경우. n = 2^31-1일 때 다음 거듭제곱인 2^31은 32비트 정수에 들어가지 않습니다.
C에서 메모리를 너무 적게 할당하는 경우. 31비트 숫자에는 문자 31개와 종료 문자 '\0'가 필요합니다.

자주 묻는 질문4

10진수를 이진수로 어떻게 변환하나요?

숫자를 2로 계속 나누면서 나머지를 매번 적고, 숫자가 0이 될 때까지 반복하세요. 나머지를 마지막 것부터 처음 것 순서로 읽으세요. 13의 나머지는 1, 0, 1, 1이므로, 13을 이진수로 나타내면 1101입니다.

나머지는 왜 역순으로 읽나요?

첫 번째로 2로 나누면 마지막 이진 자릿수인 숫자가 홀수인지 알 수 있습니다. 그다음 나눗셈을 할 때마다 다음 자릿수가 왼쪽에서부터 드러납니다. 따라서 나머지는 가장 낮은 자릿수부터 나오며, 숫자를 일반적인 방식으로 쓰려면 순서를 뒤집어야 합니다.

10진수를 이진수로 변환하는 시간 복잡도는 얼마인가요?

각 단계에서 숫자가 절반으로 줄어들므로, 이진 숫자 하나당 한 번씩, 즉 약 log2(n)번 반복문이 실행됩니다. 따라서 시간 복잡도는 O(log n)이고, 정답 문자열에는 O(log n)의 공간이 필요합니다. 32비트 정수의 경우 최대 31단계입니다.

나눗셈 대신 비트 연산을 사용해 이진수로 변환할 수 있나요?

네. n & 1은 최하위 비트를 가져오고 n >> 1은 그 비트를 제거합니다. 이는 음수가 아닌 수에 대해 n % 2와 n / 2를 사용하는 것과 같습니다. 반복문과 뒤집기는 그대로 유지됩니다. 나눗셈은 설명하기 더 쉽고, 시프트 방식은 저수준 코드에서 흔히 사용됩니다.

Python

def toBinary(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

n = 13

기대값

"1101"