[알고리즘] #4_2021 KATABI 알고리즘스터디_정수론 및 조합론

정수론이란, 정수의 성질을 연구대상으로 하는 수학의 한 분야

조합론이란, 유한하거나 가산적인 구조들에 대해 어떤 주어진 성질을 만족시키는 것들의 가짓수나 어떤 주어진 성질을 극대화하는 것을 연구하는 수학의 한 분야 

 

정수론

1. 소수(Prime number)

양의 약수가 1과 자기 자신으로 두개 뿐인 자연수 

   1) 소수 구현방법 
      (1) 1, 2 제외 (소수이기 때문)
      (2) 3부터 n까지 순회하며 약수가 있는 지 확인      

 

2. 소인수분해 (Prime factorization) 
한 합성수를 소수들의 곱으로 표현하는 것을 찾는 방법 
[합성수] 소수의 반댓말, 세 개 이상의 양의 약수를 가지고 있는 수 
  

    1) 소인수분해 구현방법 
       (1) 2부터 시작해서 n의 약수 탐색 
       (2) 약수를 찾을 때마다 n/n의 약수 
  

3. 에라토스테네스의 체 (Sieve of Eratosthenes)

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수탐색방법

체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 불림

임의의 자연수 n에 대하여 그 이하의 소수를 찾는 간단하고 빠른 방법

 

    1) 에라토스테네스의 체 구현방법

    EX) 1부터 100 사이의 소수 구하는 문제

       (1) 1부터 100까지의 숫자 나열

       (2) 소수, 합성수가 아닌 유일한 자연수 1 제거

       (3) 2를 제외한 2의 배수 제거

       (4) 3을 제외한 3의 배수 제거

       (5) 2, 3 다음으로 남아있는 가장 큰 소수 5를 제외한 5의 배수 제거

       (6) 7을 제외한 7의 배수 제거

           → 4, 8의 배수는 2의 배수에서, 9의 배수는 3의 배수에서 다 지워졌기 때문에 지울 필요 X

              11 이상의 소수들의 배수부터는 `11 > (루트) 100` 이기 때문에 지울필요 X'

 

4. 유클리드 호제법 (Euclidean)

2개의 자연수 또는 정식의 최대공약수를 구하는 방법

[호제법] 두 개의 수가 서로 상대방 수를 나눠 결국 원하는 수를 얻는 알고리즘

 

    1) 유클리드 호제법 구현방법

       (1) n, m 두 개의 수 입력 (이 때, m>n)

       (2) n이 0이라면, m을 출력하고 알고리즘 종료

       (3) m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘 종료

       (4) 둘 다 아니라면, m을 n으로 나눈 나머지를 m에 대입 + m과 n을 바꾸고 다시 (3) 으로

 

조합론

1. 순열 (Falling factorial)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것

 

2. 조합 (Binomial coefficient)

∣S∣=n인 집합 S에서 r-부분 집합의 개수

서로 다른 n개 중에 r개를 선택하는 경우의 수

---

 

 

* 문제링크 https://www.acmicpc.net/problem/3036

3036번: 링

 

 

내가 구현한 링 문제 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int N, i, g = 0;
	int arr[100] = { 0 }; //N(3 ≤ N ≤ 100) 이므로 100짜리 배열 선언

	//첫번째 입력으로 정수 N 받기 
	printf("링의 개수 N개 입력 : ");
	scanf("%d", &N);

	//입력받은 N개의 정수를 arr[] 배열에 넣어주기 
	printf("%d개의 정수 입력 : ", N);
	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	
	for (i = 1; i < N; i++) {
		int g =  gcd_func(arr[0], arr[i]);
		printf("%d %d", arr[0] / g, arr[i] / g);
	}
}
int gcd_func(int a, int b) {
	int r;

	int be = a;
	int af = b;

	while (b > 0) {
		r = b;
		b = a % b;
		b = r;
	}

	for (int i = b; i > 1; i--) {
		if (a % i == 0 && b % i == 0) {
			return i;
		}
	}
	return 1;
}

 

첫번째 링 반지름 / i번째 링의 반지름을 생각해서 코드를 작성해봤다.

오류없이 코드가 실행되긴하지만, 결과가 출력되지 않는다. 

코드는 수정이 되는대로 재업로드하도록 하겠다. 

---

zoom으로 온라인 스터디 진행

 

오늘로 네번째 스터디를 끝냈다. 

 

회사와 학원으로 이래저래 바빠서 이번 스터디는 조금 열심히 준비하지 못 했다. 

스터디 날짜를 목요일에서 일요일로 변경하게 되었다. 

 

평일에는 회사일에 집중하고, 토요일에는 학원 수업이 끝나면 스터디 준비하는 시간을 가져야겠다.