728x90

유클리드 호제법 : 기원전 300년경 기하학자 유클리드가 주장하여 그의 이름을 딴 공식으로 알려져 있다.
두 자연수 A,B에 대하여 A를 B로 나누었을 때 몫을 Q, 나머지를 R이라고 하면(A = BQ+R)
A,B의 최대공약수는 B,R의 최대공약수와 같다.
<증명> A,B 둘의 최대공약수 G
A = aG, B = bG (a,b는 서로소)
(A = BQ+R, B = bG 이므로)
bGQ+R = aG
=> R = (a - bQ)G
--------------------------
A = aG
B = bG
R = (a-bQ)G
그러므로 A,B의 최대공약수와 B,R의 최대공약수는 G로 서로 같다.

========================================================================
#include <stdio.h>
unsigned int gcd(unsigned int valuer1, unsigned int value2);
unsigned int lcm(unsigned int value1, unsigned int value2);

int main()
{
    unsigned int value1, value2;
    printf("자연수 2개를 입력하시오 : ");
    scanf("%d %d", &value1, &value2);
    printf("최대공약수 : %d\n", gcd(value1, value2));
    printf("최소공배수 : %d\n", lcm(value1, value2));
    return 0;
}



int lcm(int value1, int value2)
{
        int temp;
        temp = gcd(number1, number2);
        return (number1/temp)*number2;
}

======================================================================
위의 소스는 우선 돌아가는 것 같지만 약점이 있다.
입력값을 전혀 체크하지 않는다는 것! 만약 자연수를 입력하지 않는다면 문제가 발생할 가능성이 크다.
0 0을 입력한다면? 만약 수를 입력하지 않고 문자를 입력해 버린다면?
간단히 오류체크를 추가해서 main을 바꿔보자.

int main()
{
    unsigned int value1, value2;
    do{
        printf("자연수 2개를 입력하시오 : ");
        scanf("%d %d", &value1, &value2);
    }while(value1 <= 0 || value2 <= 0);
    printf("최대공약수 : %d\n", gcd(value1, value2));
    printf("최소공배수 : %d\n", lcm(value1, value2));
    return 0;
}

간단히 do-while을 사용해서 자연수가 아닌 정수(0,음수)는 걸러주도록 했다.
숫자 이외의 값이 입력되는 경우는 찾아보기 쉽게 다른 글로 다시 써야겠다.

728x90
728x90

#include <stdio.h>

unsigned long factorialUsingRecursion(unsigned long n);
unsigned long factorialUsingLoof(unsigned long n);

int main(void)
{
        printf("10! = %lu\n", actorialUsingRecursion(10));
        printf("10! = %lu\n", factorialUsingLoof(10));
        return 0;
}

// 재귀호출을 이용한 factorial계산
// 종료조건(if)을 가장 먼저 적어주는 것에 유의
// 재귀호출은 어떻게 돌아가는지가 중요한 것이 아니라
// 어떤 수식을 그대로 옮겼느냐만 생각하면 된다.
unsigned long factorialUsingRecursion(unsigned long n)
{
        if(n <= 1) return 1;
        return(n*factorial(n-1));
}

unsigned long factorialUsingLoof(unsigned long n)
{
        unsigned long result, i;

        result = 1;
        for(i=2; i<=n; i++)
        {
                result = result * i;
        }
        return result;
}

728x90
728x90
완전제곱이란?


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

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


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

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

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

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

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

+ Recent posts