C++에서 제곱근 연산 없이 숫자가 완전제곱수인지 확인하는 방법

프로그래밍 문제를 풀다 보면 주어진 숫자가 완전제곱수(perfect square)인지 확인해야 하는 경우가 자주 있습니다. 예를 들어 1024는 32 × 32로 표현되므로 완전제곱수지만, 1000은 어떤 정수의 제곱으로도 표현할 수 없으므로 완전제곱수가 아닙니다.

보통은 sqrt()와 같은 제곱근 함수를 사용하면 간단하게 확인할 수 있지만, 이 글에서는 제곱근 연산 없이 완전제곱수 여부를 판별하는 방법을 다룹니다. 핵심 아이디어는 간단합니다. n이 완전제곱수라면 n = i × i를 만족하는 정수 i가 반드시 존재한다는 사실을 이용하는 것입니다.

알고리즘

isPerfectSquare(n) −

입력 − 확인할 숫자 n

출력 − n이 완전제곱수이면 true, 그렇지 않으면 false

시작
    i := 1부터 시작하여 i² ≤ n을 만족하는 동안 i를 1씩 증가:
        만약 n이 i로 나누어 떨어지고, n / i = i이면
            true 반환
    반복 종료
    false 반환
끝

C++ 구현 예제

#include <iostream>
using namespace std;

bool isPerfectSquare(int number) {
    for (int i = 1; i * i <= number; i++) {
        if ((number % i == 0) && (number / i == i)) {
            return true;
        }
    }
    return false;
}

int main() {
    int n = 1024;
    if(isPerfectSquare(n)){
        cout << n << " is perfect square number";
    } else {
        cout << n << " is not a perfect square number";
    }
}

실행 결과

1024 is perfect square number

동작 원리

1. i를 1부터 시작해 i² ≤ n을 만족하는 동안 1씩 증가시킵니다.
2. n % i == 0 조건으로 i가 n의 약수인지 확인합니다.
3. n / i == i 조건으로 n이 정확히 i의 제곱인지 판별합니다.
4. 두 조건을 모두 만족하면 완전제곱수이므로 true를 반환하고, 끝까지 찾지 못하면 false를 반환합니다.

시간 복잡도

반복문은 i² ≤ n을 만족하는 동안만 실행되므로 최대 √n번 수행됩니다. 따라서 시간 복잡도는 O(√n)이며, 제곱근 연산을 직접 호출하지 않고도 효율적으로 판별할 수 있습니다.

참고로 sqrt()를 사용하는 방식은 부동소수점 오차 때문에 매우 큰 수에서 잘못된 결과를 반환할 위험이 있습니다. 반면 이 방법은 정수 연산만 사용하므로 오차 없이 정확한 결과를 얻을 수 있다는 장점이 있습니다.