source C 완전제곱수 판별

완전제곱이란?

① 정수(整數)에 대해서는 다른 정수의 제곱으로 이루어져 있는 정수를 말하는 것으로, 예컨대 1(=12), 4(=22), 9(=32), 16(=42),…이다. ② 다항식(多項式)에 대해서는 어떤 다항식의 제곱으로 되어 있는 다항식을 말하는 것으로, 예를 들면 f(x)=x2＋6x＋9=(x＋3)2일 때, g(x)=x+3이면, f(x)={ g(x)} 2이 된다. 이 때 f(x)는 완전제곱이다.

- ⓒ 두산백과사전 EnCyber & EnCyber.com, 무단 전재 및 재배포 금지 -

인터넷 카페를 돌다가 누군가 완전제곱 판별 소스를 올려놓은 것을 봤다. 소스를 보면서 문제를 풀 때 바로 컴퓨터 앞에서 작성을 시작하는 것이 얼마나 위험한 일인지 다시 생각하게 되었다.
아래는 까페 관리자가 올린 소스다. 프로그래밍에 꽤 신경을 많이 쓰는 것이 보이는 사람인데 문제를 풀 때는 가끔 실수를 하기도 하니까.. 만약 이 글을 본다면 기분나쁘게 생각하지 말았으면 좋겠다.

#include <stdio.h>
#include <math.h>

int IsPerfectSquareNumber(unsigned long number);
int IsPrime(unsigned long number);

int main(void)
{
        unsigned long number;

        printf("자연수 하나를 입력하십시오 : ");
        scanf("%lu", &number);
        printf("%lu는 완전제곱수%s니다.\n", number, IsPerfectSquareNumber(number)?" 입":"가 아닙");
        return 0;
}

int IsPerfectSquareNumber(unsigned long number)
{
        unsigned long i, j;

        for(i=2; i<=number; i++)
        {
                if(IsPrime(i))
                {
                        for(j = 0; (number%i)==0; j++)
                                number/=i;
                        if((j % 2) != 0)
                                return 0;
                }
        }
        return 1;
}

int IsPrime(unsigned long number)
{
        unsigned long i, sqrt_number;

        if(number < 2)
                return 0;
        sqrt_number = (unsigned long)sqrt(number);
        for(i=2; i<=sqrt_number; i++)
                if(number%i == 0)
                        return 0;
        return 1;
}

좀 더 많은 수를 입력받을 수있게 하기 위해 unsigned long을 사용하고 있는 것을 알 수 있다.(int는 컴파일러에 따라 다른 결과를 가져올 수도 있다.)
무리하게 if문 내에 핵심내용을 기술하는 것 외에도 치명적인 실수가 있다. 프로그램이 실행되는 동안 불필요한 작업을 반복해서 하고 있는 부분이 있다. 도대체 어디가? 아래 글을 보기 전에 한번 차근자근 따져보기 바란다.


================================================================================
불필요한 작업은..

IsPrime함수의 사용이다. IsPerfectSquareNumber함수 내에서 for문을 돌면서 2부터 1씩 증가시키는 값으로 나누어질수 있는만큼 계속 나누어간다. 소인수분해는 소수(Prime number)로 나누어야 한다. 그런데 2로 나눈 나머지가 다시 2로 나누어지면 반복해서 나누는 과정이 있다.
                        for(j = 0; (number%i)==0; j++)
                                number/=i;
이 부분이다. 이 구문을 만나면 소수가 아닌 숫자로는 for문의 판별식((number%i)==0)을 만족할 수 없으므로 애초에 for문에 들어가지 못한다.
예를 들어 8로 나누어지는 수라면 이미 2로 3번 나누었다. 6으로 나누어지는 수라면 2에서 한번 3에서 한번 나누었으므로 i가 6까지 왔으면 당연히 나눌수 없게된다.

그래서 소스를 조금 수정해봤다.

#include <stdio.h>
#include <math.h>
int IsPerfectSquareNumber(unsigned long number);

int main(void)
{
        unsigned long number;
        printf("자연수 하나를 입력하십시오 : ");
        scanf("%lu", &number);
        printf("%lu는 완전제곱수%s니다.\n", number, IsPerfectSquareNumber(number)?" 입":"가 아닙");
        return 0;
}
int IsPerfectSquareNumber(unsigned long number)
{
        unsigned long i, j;
        for(i=2; i<=number; i++)
        {
            for(j = 0; (number%i)==0; j++)
                    number/=i;
            if((j % 2) != 0)
                    return 0;
        }
        return 1;
}

여기서 if문은 어떤 수가 되건 어떠한 값(소수가 아니더라도)의 제곱이 되면 완전제곱이므로 같은 수가 쌍으로 있으면 완전제곱이 될 수 있다는 생각이다. 예를 들어 144(= 12*12)는 2*2*2*2*3*3이므로 2^4*3^2으로 표현된다. 2가 두쌍 3이 한쌍 있으므로 완전제곱이 된다.

이래놓고 봐도 도저히 마음에 들지 않는다. 이럴 땐 문제를 처음부터 다시 인식하는 과정이 필요하다.
완전제곱의 정의 : 다른 정수의 제곱으로 표현되는 정수
1조건 : 정수여야 한다.
2조건 : 다른 정수의 제곱으로 표현된다.(다시 말하면 기하평균이 정수다.)

이렇게 생각해보면 기하평균이 정수인지 확인해보면 되는 것이다. 기하평균이란 어떠한 수의 제곱근을 말하는 것으로 루트를 씌운 값이라고 생각하면 쉽다. 기하평균이 정수인지는 어떻게 판단하지? 난 아래와 같은 코드를 생각했다.

#include <stdio.h>
#include <math.h>

int IsPerfectSquareNumber(unsigned long number);

int main(void)
{
        unsigned long number;
        printf("자연수 하나를 입력하십시오 : ");
        scanf("%lu", &number);
        printf("%lu는 완전제곱수%s니다.\n", number, IsPerfectSquareNumber(number)?" 입":"가 아닙");
        return 0;
}

int IsPerfectSquareNumber(unsigned long number)
{
       unsigned long ga = (unsigned long )sqrt(number); //ga == geometric_average
       return ((ga * ga) == number);
}

기하평균을 정수로 변환시킨 후 다시 제곱하여 원래의 수가 나오는지 확인하는 것이다.
만약 기하평균이 정수가 아니라면 slicing이 발생하여 소수점 아래는 버린다. 그러면 제곱을 해도 원래의 값이 되지 않는다. 형 변환의 위험을 역이용하였다. 위험한거 아냐?라고 생각한다면 큰 오해다. 마지막 소스는 수학적으로 문제가 없으며 처음보다 훨씬 안전한 소스라고 생각한다.

꽤 길고 복잡한 소스가 두줄로 줄었다. 심지어 이정도라면 함수를 따로 구현할 필요조차 없이 그냥 한줄로 넣어주면 된다. 문제를 제대로 인식하고 어떤 방법으로 접근할 것인가를 깊이 생각해보는 것은 프로그래머의 중요한 습관이다. 열심히 생각하고 노력하는 사람들도 실수를 많이 하는데 처음부터 함부러 뛰어드는 습관이 들어버린다면 당신은 프로그래머가 아니라 코더로 만족해야 한다.