01. 1차시 교육

01.cpp - 소수판별

#include <stdio.h>
 
int is_prime(int n){
    for(int i=2; i<n; ++i){
        if(n%i==0) return 0;
    }
    return 1;
}
 
int main(){
    int n;
    scanf("%d", &n);
    printf("%d", is_prime(n));
}

내 소스는 2부터 n-1까지 약수인지 아닌지를 검사하고 하나라도 약수가 있으면 소수가 아닌것으로 판별한다. 

하지만 4행에서 for(int i=2; i<sqrt(n); ++i) 를 해주면 시간을 더 단축시킬 수 있다.

제곱근을 씌우는 이유 : n이 소수가 아닐 때, n이 갖고 있는 모든 약수에서, 1과 자기 자신을 뺀 나머지 약수들을 구해본다. 그 약수들 중에서도 소수가 아닌 약수들은 그 소수들 중 하나를 무조건 약수로 가지고 있다 => 소인수 분해와 비슷하다. 

36을 예로 들어보자. 36의 약수는 1, 2, 3, 4, 6, 9, 18, 36이다. 이 중 1과 자기 자신을 뺀 나머지 약수는 2, 3, 4, 6, 9, 18이다. 이 중 소수는 2, 3이며 나머지 약수들은 모두 2 혹은 3을 약수로 가지고 있다.

02.cpp - 콜라츠 추측(우박수)

#include <stdio.h>
 
int f(int n){
    if(n==1) return 0;
    if(n%2==0) return 1+f(n/2);
    else return 1+f(n*3+1);
 
}
 
int main(){
    int n;
    scanf("%d", &n);
    printf("%d", f(n));
}

유명한 문제이다. 어떤 수 n을 짝수면 2로 나누고 홀수면 3을 곱한 후 1로 더하는 것을 계속 반복하면 언젠간 1이 되는 것을 말한다. 아직 증명이 안되었기 때문에 콜라츠 법칙이나 공식이 아닌 추측이 된 것이다.

나는 편의상 재귀함수로 짜보았다.

03.cpp - 카운트다운

#include <stdio.h>
 
void print_int(int i){
    if(i==0){
        printf("\b");
        return;
    }
    printf("%d ", i);
    print_int(i-1);
    return;
}
 
int main(){
    int n;
    scanf("%d", &n);
    print_int(n);
}

n부터 1까지 출력하는 예제이다. 반환형이 void형인 함수를 이용해서 풀었다.

04.cpp - 팩토리얼(Factorial)

#include <stdio.h>
int fac(int n){
    if(n==1) return 1;
    return n*fac(n-1);
}
int main(){
    int n;
    scanf("%d", &n);
    printf("%d", fac(n));
}

n부터 1까지 차례대로 다 곱하는 팩토리얼이다.

05.cpp - n의 x승

#include <stdio.h>
int f(const unsigned int n, const unsigned int x){
    if(x==0) return 1;
    else return n*f(n, x-1); 
}
 
int main(){
    int n, x;
    scanf("%d %d", &n, &x);
    printf("%d", f(n, x));
}

n의 x승을 구하는 예제이다.

06.cpp - 피보나치수열(Fibonacci)

#include <stdio.h>
typedef long long int ll;
ll dp[1000];
ll res=0;
ll fi(int n){
    res++;
    if(dp[n]) return dp[n];
    if(n==1) return 0;
    else if(n==2) return 1;
    else {
        dp[n-2]=fi(n-2);
        dp[n-1]=fi(n-1);
        return dp[n-2] + dp[n-1];
    }
}
/*
int for_(int n){
    int a=0, b=1;
    for(int i=1; i<n; ++i){
        if(i%2==0){
            a=a+b;
        }
        else
            b=b+a;
    }
    if(n%2==0)
        return b;
    else return a;
}
*/
int main(){
    int n;
    scanf("%d", &n);
    printf("%lld", fi(n));
    //printf(" %d", for_(n));
    //printf(" %d", res);
}
//O(n) = n(n-1)/2

너무 유명한 공식이다.

n==1일때 (첫번째) 0을 설정하고 n==2일때 1을 설정해 놓는다고 보면 된다. 

나는 전에 배웠던 동적계획법을 복습하고자 남는 시간에 dp로 구현을 해보았다. 원래 코드는 아래와 같다.

#include <stdio.h>
typedef long long int ll;//int 형 범위 
ll dp[1000];
ll res=0;
ll fi(int n){
    res++;
    if(n==1) return 0;
    else if(n==2) return 1;
    else return fi(n-2) + fi(n-1);
}
 
int for_(int n){
    int a=0, b=1;
    for(int i=1; i<n; ++i){
        if(i%2==0){
            a=a+b;
        }
        else
            b=b+a;
    }
    if(n%2==0)
        return b;
    else return a;
}
 
int main(){
    int n;
    scanf("%d", &n);
    printf("%lld", fi(n));
    printf(" %d", for_(n));
    //printf(" %d", res); => 함수의 호출 횟수 구한 것.
}
//O(n) = n(n-1)/2 => 빅오 표기법

07.cpp - 약수 출력

#include <stdio.h>
#include <math.h>
void divisor(const unsigned int n);//prototype
 
int main(){
    int n;
    scanf("%d", &n);
    divisor(n);
}
 
void divisor(const unsigned int n){
    for(int i=1; i<=n; ++i){
        if(n%i==0){
            printf("%d ", i);
        }
    }
}

약수를 모두 출력하는 예제이다. 1부터 자기 자신까지 모든 약수를 출력한다. (math.h는 이 소스와는 관련 없다.)

08.cpp - 소인수분해

#include <stdio.h>
 
void prime_factor(unsigned int n){
    int div=2;
    while(n!=1){
        
        if(n%div==0){
            printf("%d ", div);
            n/=div;
        }
        else div++;
    }
    return;
}
 
int main(){
    int n;
    scanf("%d", &n);
    prime_factor(n);
}

소인수분해 결과를 출력한다.

ex)n=100이면 2 2 5 5 출력.

09.cpp - 최대공약수의 공식과 for문으로 구현

#include <stdio.h>
void gcd(int a, int b){
    if(b==0) printf("%d", a);
    
    else gcd(b, a%b);
}
void gcd_for(int a, int b){
    int arr[100];
    int arrptr=0;
    int arr2[100];
    int arr2ptr=0;
    int done=0;
    for(int i=1; i<=a; ++i){
        if(a%i==0) arr[arrptr++]=i;
    }
    for(int i=1; i<=b; ++i){
        if(b%i==0) arr2[arr2ptr++]=i;
    }
    for(int i=arr2ptr-1; i>=0; --i){
        if(done) break;
        for(int j=0; arr[j]!=0; ++j){
            if(arr2[i]==arr[j]){
                printf("%d", arr2[i]);
                done++;
                break;
            }
        }
    }
}
int main(){
    int a, b;
    scanf("%d %d", &a, &b);
    gcd(a,b);
    gcd_for(a,b);
}

gcd, 즉 최대공약수는 유클리드 호제법이라는 공식을 통해서 쉽게 구할 수 있다.

gcd(a, b)를 gcd(a, 0)이 될 때까지 gcd(a, b mod a)의 연산을 수행하는 것이다. (b mod a 는 b를 a로 나눈 나머지를 의미하고, a>=b이다.)

유클리드 호제법 증명(단, G(a, b)는 a와 b의 최대공약수를 의미함.) : 

정수 a를 b로 나눴을 때 몫이 q이고 나머지가 r이다. 이를 식으로 쓰면 a=bq+r 이다. 이때 r은 0부터 b-1까지 가능하다.

이때 유클리드 호제법은 (a와 b의 최대공약수) == (b와 r의 최대공약수) 을 말한다.

a = bq + r

G(a, b) = k라고 정한다.

그러면 a = mk   ,    b = nk 라고 할 수 있다. 이때 m과 n은 서로소이다. (k가 최대공약수이기 때문)

a=bq+r에 mk, nk를 대입한다.

 =>  mk = nkq + r 

 =>  r = mk - nkq  

 =>  r = (m-nq) * k // 아니? a에도 k가 들어있고 b에도 k가 들어있고 r에도 k가 들어있다구우~? 근데 아직 b와 r의 최대공약수가 k인지는 모른다! 공약수가 k일뿐!

즉 n과 m-ng가 서로소임을 증명하면 된다는 말이죠!

여기서 귀류법 사용! (귀류법이란 증명하고자 하는 명제가 거짓임을 참으로 두고 그 명제의 불합리성을 증명함으로써 결국 증명하고자 하는 명제가 참임을 증명하는 방식.)

=> n과 m-nq가 서로소가 아니라고 가정한다.

=> n과 m-nq의 공약수를 G(1 아님)라고 한다.

-> n = xG, m-nq = yG

=> n = xG를 m-nq = yG에 대입하면     ==>    m - xGq = yG

    넘기면==>   m = (xq + y) * G

!!!! 분명 n과 m이 서로소라고 했는데, 여기서는 공통의 약수 G를 가진다고? 말도안되잖아 !!!!

==>>n과 m-nq는 서로소이다.

==>>G(b, r)=k

a=(제수, 나눠지는 수), b=(피제수, 나누는 수), r=(나머지)

=>결국 a와 b의 최대공약수가 b와 r(즉, a를 b로 나눈 나머지)의 최대공약수가 같다는 성질을 이용해서 수를 줄여나가는 방법이라고 볼 수 있다.

=> 수를 줄여나가는걸 어떻게 알아? => a>=b이고 b>r>=0이므로 최대공약수를 구할때까지는 무슨 일이 있어도 항상 줄여나갈 수 있다는 걸 알 수 있다.

for문으로 구현한 것은 a, b 각각의 약수를 모두 구한 다음 b의 가장 큰 약수부터 시작해서 a의 약수들과 같은지 검사하고, 같다면 그게 최대공약수이므로 출력한다.

09.cpp

08.cpp

07.cpp

06.cpp

05.cpp

04.cpp

03.cpp

02.cpp

01.cpp