[Math] 코딩테스트에 나오는 수학 정리(정수론 : 공약수/공배수, 에라토스테네스의 체..)

.#

ㅇ 대표적으로 코딩테스트에 나오는 수학.

- 정수론(소수, 약수, 배수 등의 관계)

- 기하(피타고라스 정리, 점 사이의 거리, 직선의 방정식, 삼각형의 넓이 등)

* 기하의 CCW(Counter Clock WIse), Convex Hull, 좌표 기하는 높은 난이도로 코딩테스트보다 대회에서 자주 빈출

---

.정수론

1. 최대공약수/최소공배수

2. 에라토스테네스의 체를 사용한 소수

3. 거듭제곱의 연산(C, Java 필수 알고리즘)

---

ㅇGCD와 LCM

ㅇ최대공약수, GCD(Greatest Common Divider)

# 1. 단순한 반복문
def gcd_naive(a, b):
    for i in range(min(a,b), 0, -1):
        if a % i== 0 and b % i == 0: return i
 
# 2. 유클리드호제법을 이용
def gcd(a, b):
    if a % b == 0: return b
    return gcd(b, a % b)
    # return gcd(b, a % b) if a % b != 0 else b
 
# 2-2. 유클리드호제법을 반복문으로
def gcd2(a, b):
    while a % b != 0: a, b = b, a % b
    return b
 
# 3. math의 gcd 사용
import math
math.gcd(1, 2)

큰 수를 넣었을 때,

속도 차이는 아래 그림과 같다

ㅇ최소공배수, LCM(Least Common Multiple)

- LCM은 GCD를 활용하여 계산

1 2 3 4

# python에서는 무관하나 다른 언어 사용 시 int overflow 발생 가능성이 있으므로 # a / gcd(a,b) * b 순서로 연산 def lcm(a, b):     return a*b / gcd(a,b)

cs

---

ㅇ 하나의 수에 대한 소수 판별 or 소인수 분해

ㅇ 소수 체크 (O(sqrt(N))

1 2 3 4 5

def isPrime(N):     for i in range(2, N):         if N%i == 0: return False         if i*i > N: break     return True

cs

line 2) 2부터 자기 자신 전까지 반복(1은 소수가 아님!)

line 3) 자신보다 작은 수로 나누었을 때, 나누어 떨어지면 소수가 아니므로 False를 return

line 4) i 가 자신의 제곱근보다 커지면 반복문 break 

line 5) 반복문에 break 되면 N은 소수임을 return

ㅇ 소인수분해 (O(sqrt(N))

1 2 3 4 5 6 7 8 9 10

def prime_factorization(N):     p, fac = 2, []     while p**2 <= N:         if N%p == 0:             N //= p             fac.append(p)         else:             p += 1     if N > 1: fac.append(N)     return fac

cs

line 2) 최소 소수와 결과를 담을 fac 공간 생성

line 3) 소수를 체크했을 때와 마찬가지로 시간복잡도를 줄여주기 위해 p**2이 N보다 작거나 같을 때까지 반복

line 4~6) N이 p로 나누어 떨어진다면 N을 p로 나눠주고, 소인수 p를 fac 공간에 추가

line 7~8) 나누어 떨어지지 않는다면 p++ 

line 9) 위 반복문이 다 돌았는데도 N이 1보다 크다면 N 자체가 소수라는 의미이므로 마찬가지로 fac 공간에 추가

---

ㅇ소수 리스트 or 소수 리스트 소인수 분해

ㅇ 에라토스테네스의 체를 활용한 소수 리스트 구하기

def era_prime(N):
    A, p = [0 for _ in range(N+1)], []
    for i in range(2, N):
        if A[i] == 0: p.append(i)
        else: continue
        for j in range(i**2, N, i):
            A[j] = 1
    return p

line 2) isPrime을 체크하는 A, 소수 리스트를 담는 p

line 3) 2부터 N까지 돌면서 소수 확인

line 4) isPrime이 체크되어있지 않다면 i 는 소수이므로, p에 추가

line 5) 소수가 아닌 경우 continue

line 6~7) i 가 소수라면, 해당 소수의 배수를 다 체크

i^2부터 N까지 반복하는 이유는 소수의 배수들 중에서 i^2보다 작은 수들은 이미 앞에 있는 소수들이 체크해주었으므로

ㅇ 소수 리스트가 있는 경우의 소인수 분해

# 소수 리스트의 크기는 sqrt(N)보다 커야 함
def prime_factorization_2(N, p):
    fac = []
    for i in p:
        if N == 1 or N > i*i: break
        while N % i == 0:
            fac.append(i)
            N //= i
        return fac

---

ㅇ에라토스테네스의 체를 활용한

ㅇ 소인수의 개수 구하기

# 1. 소인수의 개수 구하기 O(NlogN)
def era_factor_count(N):
    A = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(i, N+1, i):
            A[j] += 1
    return A

line 4) 1은 소수가 아니지만 소인수에 포함되므로 1부터 N까지 반복

line 5) i 의 배수는 i 를 소인수로 포함하므로 

line 6) i 의 배수 idx에 ++ 해주게되면 1~N까지 각 숫자들의 소인수 개수를 담은 A를 return

   * N이 10일 경우, [0, 1, 2, 2, 3, 2, 4, 2, 4, 3, 4]

8의 소인수 : 1, 2, 4, 8 (4개)

9의 소인수 : 1, 3, 9 (3개)

10의 소인수 : 1, 2, 5, 10 (4개)

ㅇ 소인수의 합 구하기

# 2. 소인수의 합 구하기
def era_factor_sum(N):
    A = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(i, N+1, i):
            A[j] += i
    return A

line 4) 마찬가지로 1부터 N까지 반복

line 5) i 의 배수는 i 를 소인수로 포함하므로 

line 6) i 의 배수 idx 에 i 를 누적

   * N이 10일 경우, [0, 1, 3, 4, 7, 6, 12, 8, 15, 13, 18]

8의 소인수 : 1, 2, 4, 8 (15)

9의 소인수 : 1, 3, 9 (13)

10의 소인수 : 1, 2, 5, 10 (18)

ㅇ 최적화된 소인수분해

# 3. 소인수분해
def era_factorization(N):
    A = [0 for _ in range(N+1)]
    for i in range(2, N+1):
        if A[i]: continue
        for j in range(i, N+1, i):
            A[j] = i
    return A
 
A = era_factorization(20)
N = 20
while A[N] != 0:
    print(A[N], end=' ')
    N //= A[N]

line 3) A는 해당 idx의 가장 큰 소인수를 저장

line 4) 1은 소수가 아니므로 2부터 N까지 반복

line 5) A[idx]가 저장되어있다면 continue

line 6~7) i 의 배수는 i 를 소인수로 가지므로 i 의 배수에 해당하는 idx에 i 를 저장.

      (A[j]는 i가 증가하면서 더 큰 소인수로 갱신)

line 10) 소인수분해 하는 방법

input 20에 대한 output은 [0, 0, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5, 2, 17, 3, 19, 5] 이다.

line 11) N이 20인 경우, 20을 소인수 분해하면 2x2x5 가 되는데

[0, 0, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5, 2, 17, 3, 19, 5]

여기서 찾고자하는 A[20]은 가장 큰 소인수 (5)를 저장하고 있고, 20에서 가장 큰 소인수 5를 나누면 4,

A[4]는 가장 큰 소인수 (2)를 저장, 4에서 가장 큰 소인수 2를 나누면 2,

A[2]도 마찬가지로 가장 큰 소인수 (2)를 저장, 2에서 가장 큰 소인수 2를 나누면 1,

A[1]은 0을 저장하고 있으므로 반복문 종료.

이렇게 해서 5, 2, 2 가 출력될 수 있다.

---

ㅇ거듭제곱과 모듈러

ㅇ 거듭제곱과 모듈러

def pow_advanced(a, b, mod):
    res = 1
    while b > 0:
        if b % 2: res = res * a % mod
        a, b = a * a % mod, b // 2
    return res
 
print(pow_advanced(3, 1001, 10001))
print(pow(3, 1001, 10001))
print(3**1001%10001)

lien 1~6) C, Java 같은 경우는 이렇게 함수를 만들어서 사용하는 것이 효율적

line 9) python에서는 pow 함수를 사용

line 8~9) 방대한 숫자가 연산될 경우 python에서는 pow 함수를 사용하는 것이 효율적