음이 아닌 수 n이 주어졌을 때, r * r = n을 만족하는 수 r을 찾고, 그 값을 가장 가까운 정수로 내림(버림)해야 하는 문제가 있습니다. 단, 파이썬의 내장 제곱근 함수(예: math.sqrt())는 사용할 수 없습니다.
예를 들어 입력값이 1025라면, 32 × 32 = 1024 ≤ 1025이므로 출력은 32가 됩니다.
문제 해결 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 탐색 범위를 절반씩 줄여가면서 조건을 만족하는 최댓값을 찾는 방식입니다.
알고리즘 단계
- n이 1 이하이면 그대로 n을 반환합니다. (0과 1의 제곱근은 자기 자신)
- 탐색 범위를 start = 1, end = n으로 설정합니다.
- start가 end보다 작은 동안 다음을 반복합니다:
- mid를 start와 end의 중간값으로 계산합니다.
- mid * mid가 n 이하이면 start를 mid + 1로 이동합니다. (더 큰 값 탐색)
- 그렇지 않으면 end를 mid로 이동합니다. (더 작은 값 탐색)
- 반복이 끝나면 start - 1을 반환합니다. 이것이 n 이하인 최대 제곱수의 루트입니다.
구현 예제
class Solution:
def solve(self, n):
if n <= 1:
return n
start, end = 1, n
while start < end:
mid = (start + end) >> 1
if mid * mid <= n:
start = mid + 1
else:
end = mid
return start - 1
ob = Solution()
print(ob.solve(1025))입력
1025
출력
32
동작 원리 설명
위 코드에서 (start + end) >> 1은 비트 시프트 연산자를 사용한 것으로, 2로 나눈 몫과 동일한 결과를 내며 나눗셈보다 빠르게 중간값을 구할 수 있습니다.
이진 탐색 방식의 시간 복잡도는 O(log n)으로, 1부터 n까지 하나씩 확인하는 선형 탐색(O(n))에 비해 훨씬 효율적입니다. 예를 들어 n이 10억이라면 약 30번의 반복만으로 답을 찾을 수 있습니다.
또한 이 방법은 부동소수점 연산을 사용하지 않기 때문에 매우 큰 정수에 대해서도 오차 없이 정확한 결과를 보장한다는 장점이 있습니다.