Square Root (Integer)

Q: 내장 함수를 사용하지 않고 제곱근을 구하려면 어떻게 해야 하나요?

정수 제곱근을 구하려면 이진 탐색으로 답을 찾으세요. 후보 0부터 x 까지는 제곱이 x 이하인 구간과 제곱이 더 큰 구간으로 나뉘며, 이진 탐색은 첫 번째 구간의 마지막 후보를 찾습니다. 또 다른 일반적인 방법은 뉴턴법입니다. 추정값 r 을 (r + x / r) / 2 로 제곱이 조건에 맞을 때까지 반복해서 갱신합니다.

Q: 이진 탐색 제곱근의 시간 복잡도는 얼마인가요?

O(log x) 시간 및 O(1) 공간. 각 단계에서 후보 범위가 절반으로 줄어들므로, x = 2^31 - 1 에는 31단계가 필요합니다. 0부터 세어 올라가면 O(√x) 단계가 필요하며, 같은 x 에 대해 46340단계입니다. 여기서는 괜찮지만 64비트 입력에서는 빠르게 증가합니다.

Q: 뉴턴 방법은 정수 제곱근을 어떻게 계산하나요?

r = x 로 시작합니다. r × r > x 인 동안 정수 나눗셈을 사용해 r 을 (r + x / r) / 2 로 바꿉니다. 각 단계에서 r 은 근을 넘지 않으면서 그쪽으로 작아지고, 루프는 제곱근의 정수 부분에서 멈춥니다. x = 2^31 - 1 의 경우 19단계가 필요하며, 근에 가까워지면 단계마다 올바른 자릿수가 대략 두 배로 늘어납니다.

Q: 정답이 32비트에 들어가는데 왜 해법에는 64비트 정수가 필요한가요?

정답은 최대 46340이지만, 테스트하는 후보 값은 그렇지 않습니다. 0부터 x 까지 이진 탐색을 하면 처음에는 10^9 에 가까운 후보 값을 시도하고, 그 제곱은 10^18 에 가까워 32비트 한계인 약 2.1 × 10^9 를 훨씬 초과합니다. 제곱을 64비트로 계산하면 비교가 정확하게 유지됩니다. m ≤ x / m 을 비교하면 큰 곱셈을 아예 피할 수 있습니다.

쉬움이진 탐색 수학과 시뮬레이션

+10

함수는 음이 아닌 정수 x를 받아 정수 제곱근을 반환합니다. 정수 제곱근은 r × r ≤ x를 만족하는 가장 큰 정수 r입니다. 즉, 제곱근을 내림한 값이므로 완전제곱수가 아닌 수는 그보다 작은 완전제곱수의 제곱근을 반환합니다. 내장 제곱근 함수나 거듭제곱 함수 없이 직접 계산하세요.

함수

mySqrt(x: integer) → integer

xinteger: 제곱근을 구할 음이 아닌 정수
반환값integer: x의 제곱근을 정수로 내림한 값

제약 조건

0 ≤ x ≤ 2³¹ - 1
내장 제곱근, 거듭제곱 또는 지수 함수를 호출하지 마세요.

예제

입력: x = 17
출력: 4
설명: 4 × 4 = 16은 17 이하이지만, 5 × 5 = 25는 17보다 크므로 17의 제곱근은 4로 내림합니다.

입력: x = 49
출력: 7
설명: 49는 완전제곱수입니다. 7 × 7 = 49이므로 반올림되는 값은 없으며, 답은 정확히 7입니다.

제출 시 숨은 테스트 +17개

후속 질문

대신 정수 세제곱근을 어떻게 구할까요? x가 음수일 수도 있다면, r × r × r ≤ x를 만족하는 가장 큰 r은 무엇일까요?

힌트

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

3개 중 0개 열림

풀이

0부터 세어 가다가 다음 제곱수가 x를 넘을 때 멈추면 정답을 구할 수 있지만, 제곱근의 크기만큼 단계가 필요하므로 범위 상한 근처에서는 약 46000단계가 걸립니다. 0, 1, 4, 9, 16 등은 정렬되어 있으므로, 제곱이 x 이하인 마지막 후보를 이진 탐색하면 약 31단계 만에 끝낼 수 있습니다. 두 방법 모두의 함정은 오버플로입니다. 후보의 제곱이 항상 32비트에 들어가는 것은 아닙니다.

0부터 세기

핵심 아이디어

제곱근은 r × r ≤ x를 만족하는 가장 큰 r입니다. 제곱이 항상 범위에 들어가는 r = 0에서 시작하고, 다음 수의 제곱도 범위에 들어가는 동안 r + 1씩 계속 증가시킵니다. 다음 수가 너무 커지는 첫 번째 r에서 루프가 멈추며, 이 값이 바로 제곱근입니다. x = 17일 때 1, 4, 9, 16은 제곱이 범위에 들어가고 25는 그렇지 않으므로 루프는 4에서 멈춥니다.

루프는 답의 값만큼 반복됩니다. 여기서 답의 최댓값은 46340이므로 최대 46340번 반복하며, 이는 빠르게 끝납니다. 하지만 시간 복잡도는 O(√x)이며 입력값에 따라 증가합니다. 64비트 x의 경우 약 3 × 10^9번 반복할 수도 있습니다.

마지막 확인에 주의하세요. x = 2^31 - 1일 때 루프는 46341의 제곱이 너무 크다는 것을 확인하기 위해 계산하며, 46341 × 46341 = 2147488281은 32비트 정수에 들어가지 않습니다. 제곱은 64비트로 계산하세요.

알고리즘

root = 0으로 설정합니다.
(root + 1) × (root + 1) ≤ x인 동안 root를 1 증가시킵니다.
root를 반환합니다.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

정답에 대한 이진 탐색

핵심 아이디어

후보 0, 1, 2부터 x까지 나열하고, 각 후보에게 똑같은 질문을 합니다. 제곱이 x 이하인가요? 답은 예, 예, 예로 나오다가 제곱근 이후의 모든 후보에 대해서는 아니요가 됩니다. 제곱은 계속 커지기 때문입니다. 제곱근은 마지막 예입니다. 예가 이어지다가 아니요가 나오는 정렬된 구간이 바로 이진 탐색을 적용하기 좋은 경우입니다.

아직 결정되지 않은 후보의 범위 lo부터 hi까지를 유지합니다. 처음 범위는 0부터 x까지이고, 지금까지 나온 가장 큰 예를 저장하는 변수 best도 둡니다. 가운데 값 mid를 검사합니다. mid × mid ≤ x이면 제곱근은 mid 이상이므로, 값을 best에 저장하고 lo를 mid + 1로 옮깁니다. 그렇지 않으면 제곱근은 더 작으므로 hi를 mid - 1로 옮깁니다. 범위가 비면 best가 제곱근입니다.

x = 17을 추적해 봅시다. 범위 0부터 17에서는 8을 검사합니다(64, 너무 큼). 다음으로 0부터 7에서는 3을 검사합니다(9, 조건에 맞음, best = 3). 다음으로 4부터 7에서는 5를 검사합니다(25, 너무 큼). 마지막으로 4부터 4에서는 4를 검사합니다(16, 조건에 맞음, best = 4). 범위가 비었으므로 답은 4입니다. 각 단계에서 범위가 절반으로 줄어드므로 x = 2^31 - 1은 31단계가 걸립니다. 제곱 계산은 64비트로 하세요. 이때 첫 번째 mid는 1073741823입니다.

알고리즘

lo = 0, hi = x, best = 0으로 설정합니다.
lo ≤ hi인 동안 범위의 중간값인 mid를 계산합니다.
mid × mid ≤ x(64비트에서)이면 best = mid로 설정하고 lo = mid + 1로 설정합니다.
그렇지 않으면 hi = mid - 1로 설정합니다.
best를 반환합니다.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

함정과 경계 사례

검색 자체는 짧지만, 버그는 산술 연산과 경계 조건에 숨어 있습니다.

32비트에서 제곱하기. x = 2147483647일 때 첫 번째 중간 후보는 1073741823이며, 그 제곱은 약 1.15 × 10^18입니다. 32비트 int에서는 값이 잘못된 값으로 오버플로되며, 그 값이 충분히 작아 범위 안에 들어가는 것처럼 보일 수도 있습니다. 곱셈을 64비트로 수행하거나, 대신 m ≤ x / m을 비교하세요.
개수 계산 루프에서 다음 후보를 32비트로 제곱하기. 2^31 - 1의 제곱근은 46340이며, 루프의 마지막 검사에서는 46341을 제곱하므로 2147488281이 되어 32비트 한계를 넘습니다.
범위를 32비트 한계 너머까지 늘리기. 배타적 상한인 hi = x + 1은 가장 큰 x에 대해 2147483648이 되어 32비트 한계를 1만큼 넘습니다. 포함적 상한인 hi = x를 사용하면 첫 단계에서 lo + hi가 정확히 2147483647까지 올라가므로, 여유는 없지만 범위 안에 들어갑니다. 64비트 인덱스를 사용하거나 lo + (hi - lo) / 2를 사용하세요.
조건에 맞는 마지막 값이 아니라 마지막으로 확인한 mid를 반환하기. x = 17이면 5를 확인한 뒤 검색이 끝나는데, 5는 너무 큽니다. 정답은 기억해 둔 4입니다.
작은 입력에서 오류가 발생하기. lo = 1에서 시작하는 검색은 x = 0을 놓치며, 나눗셈 검사 m ≤ x / m은 m = 0일 때 0으로 나누게 됩니다. 0과 1은 각각 따로 검사하세요.

자주 묻는 질문4

내장 함수를 사용하지 않고 제곱근을 구하려면 어떻게 해야 하나요?

정수 제곱근을 구하려면 이진 탐색으로 답을 찾으세요. 후보 0부터 x까지는 제곱이 x 이하인 구간과 제곱이 더 큰 구간으로 나뉘며, 이진 탐색은 첫 번째 구간의 마지막 후보를 찾습니다. 또 다른 일반적인 방법은 뉴턴법입니다. 추정값 r을 (r + x / r) / 2로 제곱이 조건에 맞을 때까지 반복해서 갱신합니다.

이진 탐색 제곱근의 시간 복잡도는 얼마인가요?

O(log x) 시간 및 O(1) 공간. 각 단계에서 후보 범위가 절반으로 줄어들므로, x = 2^31 - 1에는 31단계가 필요합니다. 0부터 세어 올라가면 O(√x)단계가 필요하며, 같은 x에 대해 46340단계입니다. 여기서는 괜찮지만 64비트 입력에서는 빠르게 증가합니다.

뉴턴 방법은 정수 제곱근을 어떻게 계산하나요?

r = x로 시작합니다. r × r > x인 동안 정수 나눗셈을 사용해 r을 (r + x / r) / 2로 바꿉니다. 각 단계에서 r은 근을 넘지 않으면서 그쪽으로 작아지고, 루프는 제곱근의 정수 부분에서 멈춥니다. x = 2^31 - 1의 경우 19단계가 필요하며, 근에 가까워지면 단계마다 올바른 자릿수가 대략 두 배로 늘어납니다.

정답이 32비트에 들어가는데 왜 해법에는 64비트 정수가 필요한가요?

정답은 최대 46340이지만, 테스트하는 후보 값은 그렇지 않습니다. 0부터 x까지 이진 탐색을 하면 처음에는 10^9에 가까운 후보 값을 시도하고, 그 제곱은 10^18에 가까워 32비트 한계인 약 2.1 × 10^9를 훨씬 초과합니다. 제곱을 64비트로 계산하면 비교가 정확하게 유지됩니다. m ≤ x / m을 비교하면 큰 곱셈을 아예 피할 수 있습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

입력

x = 17

기대값