완전제곱수란 무엇일까요?
어떤 수 n이 주어졌을 때, 이 수가 완전제곱수(perfect square)인지 아닌지 판별하는 것이 이 글의 목표입니다. 완전제곱수란 어떤 정수 a에 대해 k = a × a 형태로 표현할 수 있는 수를 말합니다. 특히 이번 문제에서는 math.sqrt()와 같은 내장 제곱근 함수를 사용하지 않고 직접 해결해야 한다는 조건이 있습니다.
예를 들어 입력이 n = 121이라면 121 = 11 × 11이므로 결과는 True가 됩니다. 반면 n = 122처럼 어떤 정수의 제곱으로도 표현할 수 없는 수라면 False를 반환해야 합니다.
풀이 전략: 이진 탐색 활용하기
제곱근 함수 없이 완전제곱수를 판별하는 가장 효율적인 방법 중 하나는 이진 탐색(binary search)입니다. 2부터 n의 절반까지의 범위에서 가운데 값을 기준으로 탐색 범위를 계속 절반씩 좁혀 나가면, 제곱했을 때 n과 일치하는 정수가 존재하는지 빠르게 확인할 수 있습니다.
구체적인 풀이 단계는 다음과 같습니다.
- n이 0 또는 1이라면 True를 반환합니다. (0 = 0², 1 = 1²)
- 탐색 범위의 시작점 start를 2로, 끝점 stop을 n ÷ 2의 내림값으로 설정합니다.
- start ≤ stop인 동안 아래 과정을 반복합니다:
- start부터 stop까지의 범위(temp)를 만들고, 그중 가운데 원소를 k로 선택합니다.
- k_squared = k × k를 계산합니다.
- k_squared가 n과 같다면 True를 반환합니다.
- k_squared가 n보다 크다면 탐색 범위를 왼쪽 절반(start는 유지, stop = k − 1)으로 줄입니다.
- 그렇지 않다면 오른쪽 절반(start = k + 1, stop은 유지)으로 줄입니다.
- 반복문이 끝날 때까지 찾지 못했다면 False를 반환합니다.
구현 코드
아래 예시 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
def solve(n):
if n == 0 or n == 1:
return True
start = 2
stop = n // 2
while start <= stop:
temp = range(start, stop + 1)
k = temp[len(temp) // 2]
k_squared = k * k
if k_squared == n:
return True
if k_squared > n:
start = temp[0]
stop = k - 1
else:
start = k + 1
stop = temp[-1]
return False
n = 121
print(solve(n))
입력
121
출력
True
시간 복잡도 분석
이 알고리즘은 매 반복마다 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도가 O(log n)입니다. 만약 2부터 n/2까지 모든 수를 하나씩 대입해 확인하는 선형 탐색 방식을 사용했다면 O(n)이 걸렸을 것입니다. 즉, 이진 탐색을 활용하면 숫자가 클수록 성능 차이가 극명하게 벌어지므로, 제곱근 함수 없이 완전제곱수를 판별할 때 가장 권장되는 접근법입니다.