음이 아닌 정수 x가 주어졌을 때, 라이브러리 함수를 사용하지 않고 x의 제곱근을 구하는 문제입니다. 즉, 직접 함수를 작성해 sqrt(x)를 계산해야 하며, 결과의 소수점 이하는 버리고 정수 부분만 반환합니다.
예를 들어 x가 4라면 결과는 2입니다. x가 8인 경우에도 결과는 2인데, 실제 sqrt(8)은 약 2.82842이지만 여기서는 정수 부분만 취하기 때문입니다.
풀이 접근 방식
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 탐색 범위를 절반씩 좁혀가면서, 제곱했을 때 x보다 작거나 같은 가장 큰 정수를 찾는 방식입니다.
알고리즘의 동작 순서는 다음과 같습니다.
- l = 1, h = x + 1, answer = 0으로 초기화합니다.
- h > l인 동안 아래 과정을 반복합니다.
- mid = (h + l) / 2로 중간값을 구합니다.
- mid × mid ≤ x이면 l = mid + 1로 갱신하고, answer = mid로 저장합니다.
- 그렇지 않으면 h = mid로 갱신하여 상한을 낮춥니다.
- 반복이 종료되면 answer를 반환합니다.
파이썬 구현 예제
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
low = 1
high = x + 1
ans = 0
while high > low:
mid = (high + low) // 2
if mid * mid <= x:
low = mid + 1
ans = mid
else:
high = mid
return ans
ob1 = Solution()
print(ob1.mySqrt(4))
print(ob1.mySqrt(16))
print(ob1.mySqrt(7))
print(ob1.mySqrt(15))실행 결과
2 4 2 3
동작 원리 살펴보기
x = 7일 때를 예로 들어 보겠습니다. 초기 탐색 범위는 [1, 8]이며, 반복마다 mid 값의 제곱을 x와 비교합니다. mid² ≤ x이면 정답 후보를 갱신하고 탐색 범위를 오른쪽 절반으로, 그렇지 않으면 왼쪽 절반으로 좁힙니다. 이 과정이 끝나면 ans에는 sqrt(7) ≈ 2.645...의 정수 부분인 2가 저장됩니다.
시간 복잡도
매 반복마다 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log x)입니다. 선형 탐색(O(√x))보다 훨씬 빠르므로 x가 매우 클 때도 효율적으로 동작합니다.