[2022 겨울학기] 1주차 - 문자열, GCD, LCM

1. 정의

-문자열이란?

string이나 char[ ]

배열 초기화 함수: memset(배열이름, 초기화값, sizeof(배열이름));

 

-GCD란?

Greatest Common Divisor: 최대공약수

 

-LCM이란?

Least Common Multiple: 최소공배수

두 자연수의 공통된 배수 중 가장 작은 수  -> 최대공약수를 통해 구할 수 있음

 

---

 

2. 동작 원리

-GCD

방식1: 두 수 m, n를 입력받고 2부터 n까지 두 자연수를 모두 나누어보면 최대공약수를 구할 수 있음

방식2: 유클리드 호제법

            m을 n으로 나눈 나머지를 r이라고 하면, m과 n의 최대공약수는 n과 r의 최대공약수와 같은 것을 이용

 

-LCM

두 수의 곱을 두 수의 최대공약수로 나누어주면 최소공배수를 알 수 있음

 

---

 

3. 코드

//GCD 최대공약수

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

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

//최소공배수

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!