BOJ 백준 수학 문제(나머지,최대공약수,최소공배수,소수) | 코드플러스 알고리즘 기초1/2 - 수학

1. 나머지 연산

답이 너무 커서(정답이 int나 longlong과 같은 자료형의 범위를 넘어갈 때) 나머지 값을 요구하는 문제에서는, 답을 다 구한 다음에 나머지를 구하는 것이 아니라, 연산할 때마다 나머지를 구해야 한다.

(A+B)%C = (A%C + B%C)

(A*B)%C = (A%C * B%C)

 

▶뺄셈의 경우 주의해야 할 것!

(6-5)%3 = 1 % 3 = 1

(6%3 - 5%3)%3 = (0 - 2) % 3 = -2 % 3 = -2? 1?

이것은 언어마다 답이 다르다.

C11, C++14 : -2

Java : -2

Python3 : 1

 

마이너스가 나오는 언어의 경우, A%C - B%C 에 C를 더해준 뒤 C로 나누도록 한다. 

즉, (A%C - B%C +C ) %C

 

■ BOJ 10430번 - 나머지 acmicpc.net/problem/10430

10430번: 나머지

2. 최대공약수(GCD)

재귀를 이용한 gcd 구현

def gcd(a, b):
	if b == 0:
    	return a
    else:
    	return gcd(b, a%b)

반복문을 이용한 gcd 구현

def gcd(a,b):
	while b != 0:
    	r = a%b
        a = b
        b = r
    return a

-> O(logN)

 

3. 최소공배수(LCM)

A * B = GCD * LCM 임을 기억하자!

위 식을 이용하여 LCM = A*B / GCD 로 최소공배수를 구한다.

 

+) python으로 아래 문제 풀 때, lcd = A*B // gcd 로 풀어야 맞게 나온다.

 

■ BOJ 2609번 - 최대공약수와 최소공배수

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

4. 소수

<소수 관련 알고리즘>

1. N의 소수 여부 판별

2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

 

1. N의 소수 여부 판별 

 

1-1) 소수에 대한 기본적인 개념을 이용하여 구하는 방법

N이 소수가 되려면,

- 2보다 크거나 같고

- N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

def prime(n):
	if n<2:
    	return False
    for i in range(2, n):
    	if n%i == 0:
        	return False
    return True

-> O(N)

 

1-2) N = a * b (a<=b)일 때, a=2이면 b=N/2 라는 점을 이용하여,

N이 소수가 되려면 2보다 크거나 같고 N/2 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

def prime(n):
	if n<2:
    	return False
    for i in range(2, n/2+1):
    	if n%i == 0:
        	return False
    return True

-> O(N/2) = O(N)

1-1방법과 그닥 차이가 없다.

 

1-3) N이 소수가 되려면 2보다 크거나 같고, 루트N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

N = a * b (a<=b) 에서 a<=루트N 이면 b>=루트N 일 수밖에 없다.

왜냐하면, a>루트N, b>루트N일 경우, a*b>N이므로 성립X, a<루트N, b<루트N일 경우, a*b<N이므로 성립X

따라서 a<=루트N, b>=루트N이다.

def prime(n):
	if n<2:
    	return False
    i = 2
    while i*i <= n: # 루트를 사용하지 않기 위해 i*i, 제곱형식으로 나타냄
        if n % i == 0:
            return False
        i += 1
    return True

-> O(루트N)으로 가장 빠른 방법이다.

 

■ BOJ 1978번 - 소수찾기 www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

★에라토스테네스의 체★

- 2부터 N까지 모든 수를 써놓는다.

- 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

- 그 수는 소수이다.

- 이제 그 수의 배수를 모두 지운다.

 

ex. 2부터 100의 수가 있다 치자.

(2,3,4,5,6,7,8,9,10,11, ..., 100)

- 아직 지워지지 않은 수 중에서 가장 작은 수인 2의 배수들을 모두 지운다.

(남은 수 : 3,5,7,9,11,13, ..., 99)

- 그 다음 지워지지 않은 수 중에서 가장 작은 수인 3의 배수들을 모두 지운다.

(남은 수 : 5,7,11,13,17, ..., 97)

- 그 다음 지워지지 않은 수 중에서 가장 작은 수인 5의 배수들을 모두 지운다.

이때, 남은 수를 잘 보면, 5*1 ~ 5*4 까지는 이미 지워진 것을 알 수 있다. 따라서 5*5부터 살펴보며 지우면 된다.

 

 

■ BOJ 1929번 - 소수구하기 www.acmicpc.net/problem/1929

1929번: 소수 구하기

▶ 내가 푼 코드 (python)

 

 

■ BOJ 6588번 - 골드바흐의 추측 www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

▶ 내가 푼 코드 (python)