프로그래밍 면접 문제 27: Squareroot of a Number
프로그래밍 면접 문제 27: Squareroot of a Number
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 26: Trim Binary Search Tree
sqrt 함수를 사용하지 않고, 주어진 숫자를 반내림(rounded down)해서 제곱근을 구합니다. 예를 들어, [9, 15] 사이 숫자는 3을 반환하고 [16, 24] 사이의 숫자는 4를 반환해야 합니다.
(음수가 아닌)숫자 N의 제곱근은 항상 0에서 N / 2 사이에 숫자입니다. 이 문제를 해결하는 직관적인 해결 방법은 0과 N / 2 사이의 모든 숫자 K를 K의 제곱이 N보다 크거나 같을때까지 확인하는 것입니다. K^2이 N와 같아지면 K를 반환합니다. K^2이 N과 같지 않으면 반내림을 하기 떄문에 K-1을 반환합니다. 코드는 다음과 같습니다:
def sqrt1(num):
if num < 0: raise ValueError
if num == 1:
return 1
for k in range(1 + (num / 2)):
if k**2 == num:
return k
elif k**2 > num:
return k - 1
return k
이 접근 방법의 복잡도는 최악의 경우 N/2 개의 숫자를 확인해야 하기 때문에 O(N)입니다. 이 선형 알고리즘은 상당히 비효율적이며, 이진 탐색을 이용해서 속도를 향상시킬 수 있습니다. 제곱근이 항상 0에서 N/2사이의 숫자라는 것을 알고 있으므로, 먼저 N/4의 제곱이 N보다 작은지, 큰지, 같은지 확인해볼 수 있습니다. N/4의 제곱이 N과 같은 경우 N/4를 반환합니다. N보다 작은 경우 N/4와 N/2 사이의 숫자를 계속 확인합니다. N보다 크면 0에서 N/4 사이의 숫자를 확인합니다. 두 경우 모두 잠재적인 범위를 반으로 줄여가면서 진행하며, 이것이 이진 탐색의 원리입니다. 일반적인 이진 탐색을 수행하지는 않고 수정된 버전을 사용합니다. 숫자 K가 K^2 <= N 그리고 (K + 1)^2 > N을 만족하는 경우 확인작업을 멈춥니다. 다음 코드는 이 설명을 명확하게 반영합니다:
def sqrt2(num):
if num<0:
raise ValueError
if num == 1:
return 1
low = 0
high = 1 + (num / 2)
while low + 1 < high:
mid = low + (high - low) / 2
square = mid**2
if square == num:
return mid
elif square < num:
low = mid
else:
high = mid
return low
일반적인 이진 탐색과 한 가지 다른점은 while 루프의 조건으로, low < high가 아니라 low + 1 < high입니다. 또한 low = mid + 1이 아니고 low = mid, 그리고 high = mid – 1이 아니라 high = mid를 적용합니다. 이런 항목들이 표준 이진 탐색에서 수정한 내용 입니다. 이 방법의 복잡도는 여전히 동일하지만 대수적인 O(logN)입니다. 이는 완전히 선형적인 솔루션보다는 훨씬 나은 방법입니다.
영리한 수학 트릭을 적용하여 일정한 시간 O(1)의 복잡도를 갖는 해결 방법도 있습니다. 다음은 이 방법에 대한 내용입니다.
이 해결 방법은 특정 숫자의 로그의 지수를 취해도 결과는 변하지 않고 그대로 유지된다는 특징을 이용합니다. 따라서 먼저 숫자의 로그를 구하고, 이를 0.5와 곱하고, 지수를 취한다음, 마지막으로 반내림하기 위해 그 값의 바닥을 내립니다. 이렇게 하면 로그 함수를 사용하기 때문에 sqrt 함수의 사용을 피할 수 있습니다. 가장 가까운 정수로 반내림 한 숫자의 로그는, 그 숫자의 이진 표현에서 가장 왼쪽에 있는 1의 위치를 보고 계산할 수 있으며, 이를 구하는데 걸리는 시간은 일정합니다. 예를 들어, 숫자 6은 이진수로 110이며 가장 왼쪽의 1의 위치는 2 입니다(오른쪽에서 0부터 셉니다). 따라서 6의 로그를 반내림하면 2가 됩니다. 이 해결 방법은 반내림 효과 때문에 항상 위의 방법과 동일한 결과를 내지 않을 수도 있습니다. 그리고 면접관의 이 접근 방법에 대한 관점에 따라서 훌륭하며 영리하다고 판단되거나 잔꾀를 부리고 유효하지 않은 방법이라고 판단될 수도 있습니다. 하지만 이 방법은 궁극적으로 수학적 지름길을 알고 있음을 증명해주기 때문에, 어떤 경우에도 확실히 언급할 만한 가치가 있습니다. 그리고 이는 모든 개발자들에게 요하는 재능입니다.
