반응형


- 소수 판별법

. 소수(Prime Number)란?

1과 자기자신 이외에는 나누어 떨어지는 정수가 없는 양의정수


1. 2~N-1까지의 정수로 나누어 보는 방법 - O(N)

2. 2~Sqrt(N)까지의 정수로 나누어 보는 방법 O(N^1/2)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<math.h>
 
int is_prime(int n)
{
    int i;
    for(i=2;i<n;i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;
}
 
int is_prime2(int n)
{
    int i,sqrn;
    sqrn=(int)sqrt(n);
    for(i=2; i<=sqrn; i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
cs




 - 에라토스테네스의 체

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
    int main(int argc, char*argv[])
    {
        if(argc<2){
            printf("Usage : prime2[integer]\n");
            return 0;
        }
 
        int n=atoi(argv[1]);
        if(n<2){
            printf("Error : n must be greater than 1\n");
            return 0;
        }
 
        int *parray;
        parray = new int [n+1];
        if(parray==0){
            printf("Error : memory allocation failed\n");
            return 0;
        }
 
        memset(parray,0,sizeof(int)*(n+1));
 
        int i,j;
        for(i=2; i<=n; i++){
            if(parray[i]==1)
                continue;
 
            j=i;
            while((j+=i)<=n){
                parray[j]=1;
            }
        }
 
        for(i=2;i<=n;i++){
            if(parray[i]==0)
                printf("%d",i);
        }
        printf("\n");
 
        delete[]parray;
        return 0;
    }
 
cs


실행결과



반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 알고리즘(c++)' 카테고리의 다른 글

백준문제[2775번]_부녀회장이 될테야  (2) 2018.08.28
백준문제[4344]_평균은 넘겠지  (1) 2018.08.27
백준문제[1152]_단어의 개수  (1) 2018.08.27
백준문제[1205]_등수 구하기  (0) 2018.08.27
알고리즘 개요, 알고리즘 분석, 유클리드 알고리즘  (0) 2018.04.25
반응형

 

 < 알고리즘 개요>


 알고리즘이란? 주어진 문제를 해결하기 위해 잘 정의된 동작들의 유한집합이다.

 자료구조 : 알고리즘의 객체, 구조화되고 조직화된 자료의 저장/추출/관리 방법

    추상 데이터 타밉(Abstracted Data Type) -> 줄여서 ADT라고 불림.

- 하나의 문제에 여러 알고리즘이 존재

- 절대적인 최상의 알고리즘은 없다.

- 주어진 문제와 환경을 먼저 숙지하라.

- 속도와 자원(resource)의 상관관계

- 단순한 알고리즘이 좋다.(지나친 속도결벽증 금물, 알고리즘 사용빈도에 따른선택)


알고리즘의 예 : 두정수의 곱셈

45*37 = 45*(30+7)

   = 45*(30+7)

   = 45*30 + 45*7

   = 315+1350

   = 1665


- 기본연산이라고 하기에 너무 복잡하고, 사람에게는 적합하지만 컴퓨터에게는 어렵다.


   * a la russe

1. 두 정수를 첫번째 두번째에 쓴다.

2. 첫번째 수가 홀수이면 두번쨰수를 세번째칸에 기록한다.

3. 첫번째 수를 2로 나누고(나머지버림), 두번째수에 2를 곱한다.

4. 첫번째 수가 0보다 크면 2로 돌아간다.

5. 세번째 칸의 수를 모두 더한다.


c++의 경우 2로 더하고 나누고를 다음과 같이 구현한다.

ex) 6 = 0110 (이진법표기)

 a<<1   -> shift로 2를 곱한것 ( 1100 =  12 )

 a>>1   -> shift로 2를 나눈것 ( 0011 = 3 )


 <알고리즘 분석>


(경험적 분석/수학적 분석, 최악의경우/ 최선의경우, 알고리즘유형, 알고리즘 성능 표기법)

경험적 분석과 수학적 분석

- 분석은 알고리즘을 정확히 선택하기 위한 방법

- 시간소요량 vs 공간 소요량

- 경험적 분석 ( Empirical Analysis)

 실제 코드를 작성후, 실행하여 시간을 측정.

 데이터 수를 다르게 하여 함수 관계 유추.

- 수학적 분석 ( Mathematical Analysis)

 알고리즘 자체를 가지고 수학적 분석을 함.

- 최악의 경우와 최선의 경우

최악의 경우(Worst Case) : 가장 많은 시간과 자원을 필요로 하는 경우

최선의 경우(Best Case) : 가장 적은 시간과 자원이 소요되는 경우

평균적 경우(Average Case) : 개념이 모호함, 자료의 균일분포? 가장 많은 빈도의 경우?,..


       ex) 수학적 알고리즘 분석 예

1
2
3
4
5
6
7
8
9
10
11
void algorithm (int a[], int n)
{
    int i,j;
    for(i=0;i<n;i++){
    //c1
        for(j=0;j<i;j++){
        //c2
        }
    }
}
 
cs



T(N) = C1 + (C1+C2) + (C1+C2*2) + (C1+C2*3)+...+(C1+C2*(N-1))

 = C1*N + C2*(1+2+3+...+N-1)

 = C1*N + C2((N-1)N/2)

 = 0.5*C2*N*N + (C1-0.5*C2)*N


알고리즘 유형

1 (상수) - 입력자료수와 관계 없이 일정한 실행시간

log N - Divide & Conquer 방법 사용시

  - 이진검색,이진트리 검색등

N - scan 방법 사용시

   - 선형 검색등

NlogN - Divide & Conquer &Merge 방법 사용시

N^2 - 이중루프

      - 삽입정렬, 선택 정렬등

N^3 - 삼중루프



알고리즘 성능표기법 (Big -Oh)

알고리즘 성능을 객관적으로 표현하는 방법

알고리즘의 시간 복잡도를 수학적으로 표현한 것. 예를 들어 버블 정렬 알고리듬은 O(n2)의 시간 복잡도를 가진다.

그외에도 옴표시법, 세타표시법 등이 있다....



 <유클리드 알고리즘>


(최대공약수찾기, c++로 구현하기, 유클리드 알고리즘 개선)

- 최대공약수 (GCD : Greatest Common Divisor)

주어지는 두 정수의 약수 중 가장 큰 공통약수

280과 30의 GCD는 10이다.

소인수 분해를 통해 GCD를 구할수 있다.

하지만 소인수분해를 통해 구하는 방법은 직관에 의존하는 방법으로 컴퓨터에 부적절하다.


따라서 다음과같은 법칙을 따른다.

GCD(U,V) = GCD(U-V, V)     if (U>V)

GCD(U,V) = GCD(V,U)

GCD(U,0) = U


유클리드 알고리즘

임의의 정수 U,V에 대해

      1. V가 U보다 크면 V와 U의 값을 바꾼다.

2. U = U-V

3. U가 0이면 V가 최대공약수

    0 이 아니면 1로 돌아감


EX) GCD(280,30)

GCD(250,30)

GCD(220,30)

GCD(190,30)

GCD(160,30)

GCD(130,30)

GCD(100,30)

GCD(70,30)

GCD(40,30)

GCD(10,30)

GCD(30,10)

GCD(20,10)

GCD(10,10)

GCD(0,10)

=10


- 유클리드 알고리즘 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
int get_gcd(int u, int v)
{
    int t; //U와 V를 교환하기 위한 임시변수
    while (u) //U가 0보다 클 동안
    {
        if(u<v) //U가 V보다 작으면
        {
            t=u; u=v; v=t; //U와 V교환
        }
    u=u-v;
    }
    return v;
}
cs





직접 c++로 실행해봤을때 모습


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
 
int get_gcd(int u, int v)
{
    int t;
    while(u)    {
        if(u<v)    {
            t=u; u=v; v=t;
        }
        u=u-v;
    }
    return v;
}
 
 
void main(void)
{
    int u,v;
    int gcd;
 
    u=280;
    v=30;
    printf("get_gcd result : ");
 
    gcd = get_gcd(u,v);
    printf("%d\n", gcd);
}
cs


실행결과





이 유클리드 알고리즘은 많은 뺼셈을 요구하기 때문에 비효율적이다.

따라서 나누었을때 나머지를 이용한 방법으로 유클리드 개선방법이 아래와 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
 
int get_gcd(int u, int v)
{
    int t;
    while(u)    {
        if(u<v)    {
            t=u; u=v; v=t;
        }
        u=u-v;
    }
    return v;
}
 
int get_gcd_modulus(int u, int v)
{
    int t;
    while(v)
    {
        t=u%v;
        u=v;
        v=t;
    }
    return u;
}
 
void main(void)
{
    int u,v;
    int gcd;
 
    u=280;
    v=30;
    printf("get_gcd result : ");
 
    gcd = get_gcd_modulus(u,v);
    printf("%d\n", gcd);
}
cs



실행결과는 같다.





    








https://youtu.be/OlpNg81Csn0?list=PLl5LpJCoD2mCIRn0Fkt8z07EK320ZmHgY 강의에 기반하여 작성하였습니다

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 알고리즘(c++)' 카테고리의 다른 글

백준문제[2775번]_부녀회장이 될테야  (2) 2018.08.28
백준문제[4344]_평균은 넘겠지  (1) 2018.08.27
백준문제[1152]_단어의 개수  (1) 2018.08.27
백준문제[1205]_등수 구하기  (0) 2018.08.27
소수구하기  (0) 2018.05.01

+ Recent posts

티스토리툴바