[정처기 실기] 실무 알고리즘 응용_기본 알고리즘(수열, 수학)

기본 알고리즘

출처: 2019 시나공 정보처리기사 실기

수열

• 팩토리얼의 합계

#include <stdio.h>

main(){
    int i=1, k=1, j=1;
    do
    {
        i++;
        k*=i;
        j+=k;
    } while(i<10)

    printf(j);
}

---

• 피보나치 수열의 합계(1+1+2+3+5+8+13~~)

//1+1+2(=1+1)+3(=1+2)+5(=2+3)+8(=3+5)+13(=5+8)


#include <stdio.h>

main(){
    int hap,cnt,c;
    int a=1,b=1;

    hap=2;
    cnt=2;

    while(1){
        c=a+b;
        hap+=c;
        cnt++;

        if(cnt<20){
            a=b;
            b=c;
        }
        else{
            printf(hap);
            break;
        }
    }
}

#include <stdio.h>

main(){
    int hap,c;
    int a=1,b=1;

    hap=2;

  for(int i=3;i<=5;i++){
        c=a+b;
        hap+=c;
        a=b;
        b=c;
        }

        printf(hap); 

}

---

수학

• 어떤 수 X가 소수인지를 판별

방법1 : X를 2부터 X보다 작은수(X-1)까지 차례대로 나누어 떨어지는지 검사. 나머지가 0이면(=나눠 떨어지면) 소수가 아니다.

방법2 제곱근 이용: X를 2부터 X의 제곱근까지의 숫자로 나누어 떨어지는지 검사.

ex) 41은 2,3,4,5,6으로 나누어도 한 번도 나누어 떨어지지 않으므로 소수이다.

sqrt(a);

• 최대 공약수 구하기 (유클리드 호제법)

1. 두 수 중 큰 수와 작은 수를 정한다.
2. 큰 수를 작은 수로 나누어 나머지를 구한다.
3. 나머지가 0이면 그때의 작은 수가 최대 공약수
4. 나머지가 0이 아니면, 그때의 작은 수를 큰 수로 하고 나머지를 작은 수로 하여 나머지가 0이 될 때까지 반복한다.

• 최소 공약수 구하기

1. 원래의 두수를 곱한 값을 최대공약수로 나눈 값

• 약수 구하기

: 어떤 수 x를 1부터 x까지 차례대로 나누어 나머지가 0이 되게 하는 수들이 x의 약수이다.

• 소인수 분해하기

1. x의 제곱근을 구한다.
2. 2부터 x의 제곱근까지의 수 중 x를 처음으로 나누어 떨어지게 하는 수가 있으면 그 수는 소수이고, x의 소인수가 된다.
3. 소인수를 구했으면, 그때의 몫을 x로 하여 2부터 다시 x의 제곱근까지의 숫자로 나누는 작업을 반복한다.
4. 만약 나누는 수가 x의 제곱근보다 커지면 그때는 몫인 x 자체가 그 수의 소인수가 된다.

ex) 
20의 소인수 분해하면 2 x 2 x 5

-> 20의 제곱근 구하기 (4) 

-> 20을 2로 나눈다 (10). 나머지가 0이므로 2는 소인수 

-> 10에 대해 다시 소인수 구하기

-> 10의 제곱근 구하기 (3) 

-> 10을 2로 나눈다 (5). 나머지가 0이므로 2는 소인수 

-> 5에 대해 다시 소인수 구하기 

-> 5의 제곱근 구하기 (2) 

-> 5를 2로 나눈다 (2). 나머지가 0이 아니므로 다음 수로 나누기 

-> 5를 3으로 나눈다 but -> 3은 5의 제곱근 2보다 크므로. 5가 소인수

• 10진수를 2진수로 변환

: x를 2로 나누어서 나머지 저장(몫이 0이 될 때까지). 그걸 거꾸로 출력

pg. 208부터~