[개념정리]정수론 및 조합론_nabi

기록용

3줄 TMI

시험 끝나고 첫 포스팅이다. 어제 시험이 끝났는데 오늘(11/3) 바로 스터디 준비에 들어갔다. 일단 딥러닝 강의도 슬슬 끝을 보이기 시작한다. 앞으로 일주일 뒤에 딥러닝 강의 수강이 끝나고 심화 프로젝트로 개발에 들어갈 것 같다. 이번주부터 양자컴퓨터 관련 공부 기록도 올라갈 것 같다.

 

---

정수론 : 각종 수의 성질을 대상으로 하는 수학의 한 분야

 

프로그래밍에서 정수론이 어떻게 활용될까? (코딩테스트에서 비주류 유형이라고 하지만 가끔 출제된다고 한다.)

1. 최대공약수/최소공배수 -> 유클리드 호제법

2. 에라토스테네스의 체를 사용한 소수 찾기 및 소인수 분해

3. 거듭제곱과 모듈러 연산

(더 있지만 쉽게 보기 힘든 유형이므로 생략)

 

먼저 최대공약수(GCD)와 최소공배수(LCM)

-> 유클리드 호제법(유클리드 알고리즘)이란?

    두 수의 최대공약수를 구하는 알고리즘이다.

    예를 들어 2개의 자연수 18,4에 대해 각각 a,b라고 가정. a,b에 대해 a를 b로 나눈 나머지를 r이라 가정. (이때 a는 b        보다 커야함) -> 18 % 4 = 2 = r 

    a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 과정을 반복하여 r'이 0이 되었을 때의 나누는 수가 a와 b의 최      대공약수이다. -> 4 % 2 = 0 = r' 이므로 나누는 수 2가 a와 b의 최대공약수

 

최대공약수와 최소공배수의 관계

 

출처https://artofproblemsolving.com/wiki/index.php/Least_common_multiple

 

위 유클리드 호제법을 코드로 구현해보겠다.

#include <stdio.h>

int main() {
    int a, b, r=0;

    scanf_s("%d %d", &a, &b);
    if (a < b) { //만일 b가 a보다 크다면 b와 a 변수에 들어있는 값 바꿔주기
        r = a;
        a = b;
        b = r;
    }
    while (b != 0) { //반복문 사용해서 유클리드 호제법 구현하기
        r = a % b;
        a = b;
        b = r;
    }
    printf("%d", a);

    return 0;
}

재귀로도 코드를 짜보고 싶지만 조금 더 공부를 한 후에 수정하도록 하겠다...

 

 

에라토스테네스의 체 -> 소수 찾는 방법(하지만 주로 대량의 소수를 한번에 찾고 싶을 때 사용됨)

 

출처https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11*2>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

-위키백과(https://scorchingnraining.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F#)-

 

즉, 소수를 판단할 범위만큼을 배열에 입력해준 후 소수가 아닌 숫자들은 하나씩 지우는 방식으로 작동한다.

 

위 에라토스테네스의 체를 코드로 구현해보겠다.

#include <stdio.h>

int main() {
    int N = 10000; //N 지정
    int a[10001];
    int i, j;

    for (i = 2; i <= N; i++) {
        a[i] = i; //2부터 N만큼 배열 초기화
    }

    for (i = 2; i <= N; i++) {
        for (j = 2; j <= N; j++) {
            if (a[j] != i && a[j] % i == 0) //만약 자기자신과 다른 숫자이면서 자기자신이 그 숫자로 나누어진다면 소수가 아님
                a[j] = 0; //소수가 아니라면 0 집어넣기
        }
    }

    for (i = 2; i <= N; i++) {
        if (a[i] != 0) //소수인 경우 출력
            printf("%d\n", a[i]);
    }

    return 0;
}

 

에라토스테네스의 체를 이용한 소인수 분해

------------------------------------------------

 

거든제곱과 모듈러(%) 연산

 

#include <stdio.h>

int main{
	int a,b,mod,res = 1;
    
    scanf_s("%d %d %d",&a,&b,&mod);
    while (b > 0){
        if (b % 2) 
        	res = res * a % mod
        a, b = a * a % mod, b // 2
        }
	printf("%d",res);
    
    return 0;
}

 

조합론(組合論, Combinatorics)이란, 
수학의 한 갈래로서 유한하거나 가산적인 이산구조에 대해 연구하는 분야지만 사실 하나로 딱잘라 정의하기는 어려울 정도로 다양한 주제를 포함하고 있다. -리브레 위키-

조합론의 하위 알고리즘으로는 그래프 알고리즘, 정렬 알고리즘 등 너무나도 많고 광범위하기 때문에 생략하도록 하겠다.

 

 

대표 이미지 출처 : https://pixabay.com/ko/?utm_source=link-attribution&utm_medium=referral&utm_campaign=image&utm_content=1653351">Pixabay로부터 입수된 https://pixabay.com/ko/users/200degrees-2051452/?utm_source=link-attribution&utm_medium=referral&utm_campaign=image&utm_content=1653351">200 Degrees님의 이미지 입니다.

---

느낀점 및 끝인사

정수론과 조합론 예시들을 살펴보면 이전에 이런 문제도 알고리즘 유형의 한 종류인가 하면서 풀었던 문제들이 여기에 포함되어있다. 특히 소수 찾기는 정말 많이 풀었던 유형인데 정수론에서 깜짝 등장해 반가웠다.