알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수)

수학과 관련한 기초문제에는 크게 3가지 분류로 나뉘어진다. 

1. 나머지 연산
2. 최대 공약수, 최소 공배수
3. 소수 (prime number)

 

 

1. 나머지 연산 (Modular Arithmetic)

 

Python 으로 문제를 푼다면 상관없겠지만, C++ , Java와 같은 경우에는 표현할 수 있는 정수의 길이가 제한되어있다.

가장 긴 정수 표현방법인 longlong으로 했을때 8byte이므로.... 

따라서 문제에서는 이를 n으로 나눈 나머지를 구하라 와 같은 방식으로 출제하게 된다. 흔히 %를 사용하는 modular.

 

* 이러한 유형의 문제를 풀때 알아두면 좋은 공식 

• 덧셈 : (A+B)%C  = (A%C + B%C)%C

• 곱셈 : (A*B)%C  = (A%C * B%C)%C
• 뺄셈 : (A-B)%C  = ((A%C)-(B%C)+C)%C

뺄셈의 경우 음수가 나올 수 있기 때문에 식이 다르다.

나눗셈은 성립하지 않는다. 

 

 

---

2. 최대공약수 (GCD : Greates Common Divisor)

 

정답의 출력이 분수일때, 기약분수의 형태로 출력하라. 라는 경우에 최대공약수(GCD)의 사용이 필요하다.

• 최대공약수 : A,B 의 공통된 약수중, 가장 큰 약수.
• 이때 최대공약수가 1이라면 A,B는 서로소(coprime)라고 한다.

 

 

 

* 최대공약수 구하는 방법 1 - 반복문

 

최대공약수를 구하는 가장 간단한 방법 : min(a,b) ~ 2까지의 모든 정수로 나누어서 확인한다.(반복문을 통해)

이러한 경우 시간복잡도는 O(n)이 된다.

최대공약수 - Python

GCD = 1  # 어차피 공약수에 1은 무조건 들어가므로...
a = int(input()); b = int(input())
i = 2 
while(i<=min(a,b)):
    if a%i == 0 and b%i ==0 :
        GCD = i
    i+=1
print(GCD)

최대공약수

int g= 1;
for (int i=2; i<=min(a,b); i++){
    if (a%i ==0 && b%i ==0){
        g=i;
    }
}

 

* 최대공약수 구하는 방법 2 -  유클리드 호제법 (Euclidean algorithm)

 

위에서 소개한 방법 1보다 빠르다.

• 원리 : a,b의 최대공약수는 b와 a%b의 최대공약수와 같다

• 즉, GCD(a,b) = GCD(b,a%b)
• 이때 a%b를 r로 표현했을 때, r이 0이면 그때 b가 최대공약수이다.

 

예를 보면 쉽게 이해가 간다.

24와 16으로 예를들어보면 GCD(24,16) = GCD(16,8) = GCD(8,0)

마지막에 r이 0이 되었으므로, 24와 16의 최대공약수는 8이다.

 

유클리드 호제법 구현 1 - 재귀함수 사용

int gcd(int a , int b){
    if (b==0){
        return a;
    }
    else {
        return gcd(b, a%b);
    }
}

재귀함수를 사용했을때 시간복잡도는 O(log n)이 된다.

 

유클리드 호제법 구현 2 - 반복문 사용

int gcd(int a , int b){
    while(b!=0){
        int r = a%b;
        a = b;
        b = r;
    }
    return a;
}

반복문을 사용했을때도 시간복잡도는 O(log n)이 된다.

 

세개 수의 최대공약수 구하기 - Python

#24, 16, 48의 최소공약수를 구해보자.
def gcd(a, b) :
    if b==0:
        return a
    else :
        return gcd(b,a%b)

print(gcd(48,gcd(24,16)))

그냥 똑같이 구현해준뒤에, GCD(a, ( GCD(b,c) ) 와 같이 겹쳐서 구해주면 된다. 수가 4개 5개라도 마찬가지이다.

 

 

2. 최소공배수 (LCM : Least Common Multiple)

 

 

최소공배수는 줄여서 LCM이라고 하며, 최대공약수인 GCD를 응용하여 구할 수 있다.

최대공약수를 이해 했다면, 최소공배수는 아래 공식만 알면 크게 어려울내용이 없다.

 

a,b의 최소공배수 = 최대공약수 * a/최대공약수 * b/최대공약수

• LCM(a,b) = GCD*(a / GCD) * (b / GCD)

 

 

 

 

---

3.  소수 (Prime Number)

• 소수 : 약수가 1과 자기 자신밖에 없는 수
• N이라는 수가 소수가 되기 위한 조건 : 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

 

 

 

* 소수와 관련된 알고리즘 2가지 

• 첫번째 :  어떤 수 N이 소수인지 아닌지 판별하는 방법
• 두번째 : N보다 작거나 같은 모든 자연수 중에서 소수를 찾는 방법

 

 

 

*소수를 구하는 방법 1- 조건을 N/2 로

알고리즘의 시간복잡도를 줄이기위해서 소수의 범위를 줄여보면

• 소수 : 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• N/2 인 이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문이다. )
• 중요포인트 : 소수가 되기위한 조건이 N-1보다 작거나 같은 이 아니라, N/2보다 작거나 같은으로 하여야 코드구현시 시간복잡도를 좀 더 효율적으로 줄일 수 있다.

 

n이 소수인지 아닌지 판별 

bool prime(int n){
    if (n < 2){
        return False;
    }
    for (int i=2; i<=n/2; i++){
        if (n % i ==0){
            return False;
        }
    }
    return True;
}

시간복잡도 : O(n)

 

 

*소수를 구하는 방법 2 - 조건을 루트N 으로

 

 

• 소수 : 2보다 크거나 같고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• 루트 N인 이유 : N이 소수가 아니라면 N = a*b 로 나타낼 수 있다. (a<=b)
• 두 수 a,b의 차이가 가장 작은 경우는 루트 N일 경우이다.
• 따라서 루트 N까지만 검사를 해보면 소수인지 아닌지 판별이 가능하다.

 

 

n이 소수인지 아닌지 판별

bool prime(int n){
    if (n < 2){
        return False;
    }
    for (int i=2; i*i<=n; i++){
        if (n % i ==0){
            return False;
        }
    }
    return True;
}

이 방법이 가장 시간복잡도 효율이 좋다. 시간복잡도는 O(루트N)

 

 

*소수를 구하는 방법 3 - 에라토스테네스의 체

 

* 1부터 N까지의 범위의 모든 소수를 구할때 사용할때 에라토스테네스의 체를 사용한다.

• (1) 2부터 N까지의 모든 수를 써놓는다.
• (2) 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
• (3) 그 수는 소수이다.
• (4) 이제 그 수의 배수를 모두 지운다.

 

예를들어 2부터 100까지로 범위를 잡고 구현해보면,

여기서 제일 작은 수는 2이고, 2는 소수이다. 따라서 2의 배수를 지운다.

여기서 지워지지 않았으며, 제일 작은 수는 3이다. 3은 소수이다. 따라서 3의 배수를 지운다.

다음은 5이며, 5도 소수이므로 5의 배수를 지운다.

다음은 7이며, 7은 소수이다. 7의 배수를 지운다.

다음은 11의 배수이지만 11의 배수들은 이미 지워졌다. (11의 제곱은 121인데, 100을 넘어가기 때문에 더이상 수행 할 필요가 없는것이다.) 

여기까지 했다면 소수를 모두 구했다.

 

 

* 코드로 구현할때는 지우는 과정은 하지 않는다. 배열을 계속하여 수정하게되면 시간복잡도가 상당히 늘어나게 된다.

 따라서, 지워졌는지 아닌지를 검사하는 방식으로 코드를 짜게 된다.

 

에라토스테네스의 체 -  코드구현

int prime[100]; //1~100 저장
int pn=0; //소수의 개수 카운팅
bool check[101]; //지워졌으면 true
int n = 100; //100까지 소수
for (int i = 2; i<=n; i++){
    if (check[i] == false){ //지워지지 않았다면
        prime[pn++] = i;  // 소수 카운팅 ++
        for (int j = i*i ; j<=n; j+=i){ //문제에서 i의 수가 클경우, i*i를  i*2 정도로 바꾸는게 좋다.
            check[j] = true;
        }
    }
}

에라토스테네스의 체는 매우 효율적인 알고리즘이며, 시간복잡도는 O(nloglogn)이다.

 

에라토스테네스의 체를 이용하여, 소수 구하기  - (Python) 파이썬 사용

r = int(input()) #입력하는 만큼 범위
check = [False for _ in range(r)]

for i in range(2,int(r**0.5)) : # 2부터 ~ 범위(r)의 제곱근까지
    if check[i] == False : # 지워지지 않고, 가장 작은수라면
        for j in range(i*2 , r, i ): # i의 2배수 부터, 3배수, 4배수, .... 범위끝까지 지운다.(True로)
            check[j] = True

prime_number = [i for i,j in enumerate(check) if i>=2 and j==False]

print(prime_number)

   *range의 3번째 parameter는 점프할 숫자이다. 즉, i의 배수를 지워야 하기 때문에 3번째 인자에 i를 넣어준다.

 

---

 

*관련문제 

https://www.acmicpc.net/problem/10430

10430번: 나머지

 

https://infinitt.tistory.com/231

백준 (boj) 파이썬 - 1934 : 최소공배수

https://infinitt.tistory.com/233

백준 (boj) 파이썬 - 최대공약수와 최소공배수

 

https://infinitt.tistory.com/234

백준 (boj) 파이썬 - 9613번 : GCD 합

 

https://infinitt.tistory.com/235

백준 (boj) 파이썬 - 1978 : 소수 찾기

https://infinitt.tistory.com/236

백준 (boj) 파이썬 - 1929 : 소수 구하기

 

https://infinitt.tistory.com/237

백준 (boj) 파이썬 - 2960번 : 에라토스테네스의 체

https://infinitt.tistory.com/238

백준 (boj) 파이썬 - 6588번 : 골드바흐의 추측