[알고리즘] 코딩테스트에 사용 되는 수학

GCD와 LCM

Greatest Common Divider와 Least Common Multiple 은 코딩테스트에서 가장 많이 나오는 유형으로 최대공약수/최소공배수를 묻는 문제의 90% 이상은 이 알고리즘을 사용한다고 한다. 아마 중학교때 배웠던 건가? 초등학교때 배웠던 건가? 대학교 들어가고 나서 딱히 최소공배수, 최대공약수를 쓸 일이 없으니 복습하는 차원에서 공부하자.

최소공배수의 경우에는 다음과 같은 식으로 풀 수 있어서 최대공약수만 알면 된다.

LCM(a, b) = a x b / GCD(a, b) <- 진짜 이것만 알면 됨

이러한 최소공배수, 최대공약수를 구현하기 위해서는 대표적으로 3가지 방법이 있다.

• 단순 반복문 이용
• 유클리드 호제법 이용
• 파이썬 라이브러리를 이용 (math)

유클리드 호제법의 경우에는 다음과 같은 공식이 성립된다.

GCD(a, b) = GCD(b, a%b)

코드

# 방법 1 : 단순 반복문 이용
def gcd(a, b):
    for i in range(min(a, b), 0, -1):
    	if a % i == 0 and b % i == 0:
    return i
            
# 방법 2-1 : 유클리드 호제법 이용
def gcd(a, b):
    if a % b == 0:
    	return b
    return gcd(b, a%b)
    
# 방법 2-2 : 반복문으로 변경
def gcd(a, b):
    while a % b != 0:
    	a, b = b, a % b
    return b

# 방법 3 : 파이썬 라이브러리 이용(math)
import math

math.gcd(a, b)

파이썬의 math 라이브러리를 사용했을 때 제일 편해 보이는 거는 팩트... 그리고 LCM을 계산할 때는 다음과 같다.

def lcm(a, b):
    return a * b / gcd(a, b)

파이썬이 아닌 다른 언어의 경우에는 다음과 같이 작성을 하면 오버플로우가 발생할 수 있으니 a / gcd(a,b) * b 이렇게 활용 하도록 하자.

소수 체크와 소인수 분해

다음은 소수 체크와 소인수 분해 알고리즘이다. 소수 체크는 반복문으로 진행하면 되고, 소인수분해의 경우에는 약간의 트릭으로 구현하면 된다.

# 소수 체크
def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
        if i * i > n:
            break
    return True

# 소인수분해 기본
def prime_factorization(n):
    p, fac = 2, []
    while p ** 2 <= n:
        if n % p == 0:
            fac.append(p)
        else:
            p += 1
    if n > 1:
        fac.append(n)

    return fac

하지만 이렇게 소수 체크를 반복문으로 진행하게 되면 시간 복잡도가 크기 때문에 느리다는 단점이 있다.(아마 이렇게 쓰면 코테에서 시간복잡도 때문에 틀리다고 나올 듯 😅)

그래서 이런 문제를 해결하기 위해 소수 리스트를 미리 만드는 방법이 있는데 이것이 에라토스테네스의 체이다. 에라토스테네스의 체의 개념은 다음과 같다.

1, 2, 3, 4, 5, 6, 7, 8, 9 10

이 주어졌을 때 1은 소수가 아니기 때문에 지워준다. 다음 2는 소수이기 때문에 2를 제외한 배수들을 지워준다.

2, 3, 5, 7, 9

그리고 나머지 숫자들에 대한 값도 방금과 같이 똑같이 해주면

2, 3, 5, 7

이라는 소수만 남게 된다.

def prime_era(n):
    # a: n의 범위 값
    # prime: 소수 리스트
    a, prime = [0 for _ in range(n+1)], []
    for i in range(2, n):
        # 소수인 경우 리스트에 추가
        if a[i] == 0:
            prime.append(i)
        else:
            continue
        for j in range(i ** 2, n, i):
            a[j] = 1

    return prime

이러한 에라토스테네스의 를 활용한 방법들은 다음과 같이 구현할 수 있다.

# 활용1: 소인수의 개수
def era_factor_count(n):
    a = [0 for _ in range(n+1)]
    for i in range(1, n):
        for j in range(i, n, i):
            a[j] += 1

    return a

# 활용2: 소인수의 합
def era_factor_sum(n):
    a = [0 for _ in range(n+1)]
    for i in range(2, n):
        for j in range(i, n, i):
            a[j] += i

    return a

# 활용3: 소인수분해 하기
def era_factorizaion(n):
    a = [0 for _ in range(n+1)]
    for i in range(2, n):
        for j in range(i, n, i):
            a[j] = i

    return a