[코지] 수학적 개념 정리

개요. 

코테를 위해서 필요한 수학적 개념 정리와 이를 구하는 방법을 C++로 알아보겠습니다. 

코테 수학 기초 개념

1. 약수

어떤 수나 식을 나누어 나머지가 없이 떨어지는 수나 식을 일컫는 말.

2. 최대 공약수 

최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킵니다.

3. 소수 

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다

4. 조합

숫자 배열에서 순서 상관없이 뽑을 수 있는 가지의 수

5. 순열

숫자 배열에서 순서에 따라 뽑을 수 있는 가지의 수

수학 기초 개념 구현 

1. 약수 

std::vector<int> factor(int value) { 
	int max = value / 2; // 모든 약수는 입력 값을 제외하면 입력값의 절반 이하에서만 나온다.
	std::vector<int> factors;
	
	for(int i = 1; i < max; i++) {
		if (value % i == 0) {
			factors.push_back(i);
		}
	}
	
	factors.push_back(value);
	
	return factors;
}

2. 최대 공약수

#include <iostream>
#include <vector>

int gcd(int a, int b) {
	std:: cout << a << " : " << b << std::endl;
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}

int main(int argc, char** argv){
	
	// 두수의 최대 공약수 
	std::cout << gcd(10,13) << std::endl;

	
	// 여러수의 최대 공약수
	std::vector<int> array = {10, 5, 30};
	int result = array[0];
	for (int i = 1; i < array.size(); i++) {
		result = gcd(result, array[i]);
	}
	
	std::cout<< "result : " << result << std::endl;
	return 0;
}

3. 소수