완전 제곱수(퍼펙트 스퀘어) 판별 방법

완전 제곱수란 무엇인가?

어떤 수의 제곱근이 정수일 때, 그 수를 완전 제곱수(perfect square number)라고 부릅니다. 다시 말해, 제곱근을 씌웠을 때 소수점 없이 딱 떨어지는 정수가 나온다면 그 수는 완전 제곱수입니다. 예를 들어 16의 제곱근은 4이므로 16은 완전 제곱수이지만, 1032의 제곱근은 약 32.12로 정수가 아니기 때문에 완전 제곱수가 아닙니다.

판별 원리

완전 제곱수를 확인하는 가장 직관적인 방법은 해당 수의 제곱근을 반복적으로 계산하여 일치 여부를 비교하는 것입니다. 제곱근 값이 대상 수를 넘어서게 되면 그 수는 완전 제곱수가 아닙니다.

하지만 매번 제곱근을 새로 계산하면 불필요한 연산 낭비가 발생합니다. 완전 제곱수의 제곱근은 항상 정수라는 성질을 활용하면 훨씬 효율적입니다. 즉, 후보 제곱근 값을 1부터 시작해 하나씩 1씩 증가시키면서, 그 제곱이 대상 수와 일치하는지만 확인하면 됩니다.

입력 및 출력 예시

입력:
확인할 숫자: 1032

출력:
1032 is not a perfect square number.

알고리즘

isPerfectSquare(num)

입력: 검사할 숫자.

출력: 숫자가 완전 제곱수이면 true(제곱근 값)를 반환하고, 제곱근도 함께 출력합니다.

Begin
   if num < 0, then
      exit
   sqRoot := 1
   sq := sqRoot^2
   while sq <= num, do
      if sq = num, then
         return sqRoot
      sqRoot := sqRoot + 1
      sq := sqRoot^2
   done
   otherwise return error
End

알고리즘 동작 과정

음수가 입력되면 유효하지 않으므로 바로 종료합니다.
제곱근 후보(sqRoot)를 1로 초기화합니다.
후보 값의 제곱이 대상 수보다 작거나 같은 동안 반복합니다.
제곱이 대상 수와 정확히 일치하면 현재 후보 값이 곧 제곱근이므로 반환합니다.
일치하지 않으면 후보 값을 1 증가시키고 다시 검사합니다.
반복문이 끝날 때까지 일치하지 않으면 완전 제곱수가 아니므로 오류(-1)를 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int isPerfectSquare(int num) {
   if(num < 0)
      return -1;           // 음수는 유효한 제곱항이 아님
   int sqRoot = 1, sq;

   while((sq =(sqRoot*sqRoot)) <= num) {            // 제곱근의 제곱이 숫자를 넘지 않는 동안
      if(sq == num)
         return sqRoot;
      sqRoot++;              // 완전 제곱수의 제곱근은 항상 정수
   }
   return -1;
}

int main() {
   int num, res;
   cout << "Enter a number to check whether it is perfect square or not: ";
   cin >> num;

   if((res = isPerfectSquare(num)) != -1)
      cout << num << " is a perfect square number, square root: " << res;
   else
      cout << num << " is not a perfect square number.";
}

실행 결과

Enter a number to check whether it is perfect square or not: 1032
1032 is not a perfect square number.

정리

이 방법은 제곱근 함수를 호출하지 않고 정수 연산만으로 완전 제곱수를 판별할 수 있다는 장점이 있습니다. 시간 복잡도는 O(√n)으로, 제곱근 후보를 1씩 증가시키며 검사하기 때문에 대상 수의 제곱근 크기에 비례한 연산 횟수가 필요합니다. 음수는 제곱하여 만들 수 없으므로 처음에 예외 처리를 해주는 점도 기억해 두면 좋습니다.

완전 제곱수(퍼펙트 스퀘어) 판별 방법 - 알고리즘과 C++ 구현