알고리즘 수학(나머지 연산, 최대 공약수, 최소 공배수)

나머지 연산

• (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
  • 뺄셈의 경우 음수가 나올 수 있어서 C를 더함

10430_나머지

• 문제링크

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

#include <stdio.h>
#include <vector>
#include<iostream>
using namespace std;
int A, B, C;
int main(void) {
	cin >> A >> B >> C;
	cout << (A + B) % C << '\\n';
	cout << ((A%C) + (B%C)) % C << "\\n";
	cout << (A*B) % C << "\\n";
	cout << ((A%C) *(B%C)) % C << "\\n";
	return 0;
}

최대 공약수

• GCD라고 함
  • 두 수 A와 B의 최대 공약수는 G는 A와 B의 공통된 약수 중에서 가장 큰 정수
  • 최대 공약수를 구하는 쉬운 방법
    • 2 부터 min(A,B)까지 모든 수 나눠보면 됨
    • 최대 공약수가 1인 두 수를 서로소 라고 함

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

• 위와 같은 구현하는 경우 시간 복잡도 O(N)이 걸림
• 그럼 더 빠르게 구현하는 방법은 뭘까?
  • 유클리드 호제법을 사용하면 된다.
    • Euclidean algorithm

유클리드 호제법

• a를 b로 나눈 나머지를 r이라고 했을때
• GCD(a,b) = GCD(b,r)과 같음
  • 이때, r 이 0 이면 b가 최대 공약수임
• ex) GCD(24,16) = GCD(16,8) = GCD(8,0) = 8

재귀를 사용하지 않는 방법

// 그냥 베이직 
int main() {
	int a, b;
	cin >> a >> b;

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

	cout << a;
	return 0;
}

//함수로 분리

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

재귀를 사용하는 방법

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

세 수의 최대 공약수

GCD(a,b,c) = GCD(GCD(a,b),c)

최소 공배수

• LCM이라고함
• 두 수의 최소 공배수는 두수의 공통된 배수에서 가장 작은 정수
• 최소 공배수는 최대공약수를 이용함

최소 공배수 = l = GCD(a,b) * (a/GCD(a,b)) * (b/GCD(a,b)

2609_최대공약수와 최소공배수 문제 풀어보기

• 문제 링크

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

#include<stdio.h>
#include<iostream>
using namespace std;

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

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

int main() {
	int num1, num2;
	cin >> num1 >> num2;
	/*while (b!=0) {
			int r = a % b;
			a = b;
			b = r;
	}*/
	int gcdNumber = GCD_re(num1, num2);
	cout << gcdNumber << '\\n';
	cout << gcdNumber * (num1 / gcdNumber)*(num2 / gcdNumber) << '\\n';
	return 0;
}

9613_GCD 합

• 문제 링크

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

• 문제 풀이 방식
  • 위 문제의 포인트는 GCD를 구할 줄 아는 것
  • 두개씩 쌍을 가지게 해서 GCD에 넣을 줄 알면됨
    • 무슨 말이냐면 완전 탐색을 해서 같은 위치의 숫자만 넣지 않으면 되는 것인데
    • 우리가 구해야하는 쌍은 아래와 같이 나타낼 수 있음
      • 즉, 위와 같이 같은 인덱스가 아닌것과 중복이 아닌것을 비교하면된다. 그래서아래와 같이 완전 탐색을 구현하면됨
      • for (int i = 0; i < n-1; i++) { for (int j = i + 1; j < n; j++) { sum += GCD(arr[i], arr[j]); } }
    • 
• 소스코드

#include<stdio.h>
#include<iostream>
using namespace std;

int GCD(int num1, int num2) {
	if (num2 == 0) return num1;

	return GCD(num2, num1%num2);
}

int main(void) {
	int testCaseNumber;
	cin >> testCaseNumber;
	for (int tc = 0; tc < testCaseNumber; tc++) {
		int n = 0;		
		int arr[104] = { 0, };
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		
		long long sum = 0;
		for (int i = 0; i < n-1; i++) {
			for (int j = i + 1; j < n; j++) {
				sum += GCD(arr[i], arr[j]);
			}
		}

		cout << sum << '\\n';
	}

	return 0;
}

• 이런 정수의 합을 더하는 문제는 주의 할 것이 하나더 있음
  • 출력하는 것, 더하는 변수의 크기를 잘 지정해야함
  • 필자는 int로 습관적으로 했다가 엥? 뭐지 했었음
  • 이런 문제는 우선 입력 100개 이상이 넘는 합이기 때문에 정수 범위를 넘어갈 수 있음
    • 정확히 범위를 따지면 좋지만 힘들면 long long 정도만 해줘도 왠만한 문제는 통과함