4. 기초 수학

1, 2, 3은 필수 4, 5, 6은 선택

4-1. 최대공약수와 최소공배수

4-1-a. 최대공약수 (GCD)

최대공약수를 구하는 가장 간단한 방법은 다음과 같습니다.

def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a%i==0 and b%i==0:
            return i

하지만 이 경우의 시간복잡도는 \(O(min(A, B))\)가 됩니다. 이 방법을 개선한 방법이 유클리드 호제법입니다. 유클리드 호제법을 수식으로 쓰면 다음과 같습니다.

\[GCD(A, B) = GCD(B, A\%B)\]

유클리드 호제법을 사용하면 시간복잡도 \(O(log \ min(A, B))\) 에 최대공약수를 구할 수 있습니다.

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

보통 이런 경우 처음에 드는 의문은 a < b 인 경우입니다. 하지만 간단하게 생각해보면 a % b == a가 되어 단순하게 swap이 되는 것을 볼 수 있습니다. python의 재귀함수 속도가 느리기에 반복문으로 다음과 같이 작성도 가능합니다.

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

4-1-b. 최소공배수 (LCM)

최소공배수는 최대공약수를 알면 다음 공식을 사용하여 쉽게 구할 수 있습니다.

\[LCM(A, B) = \frac{A \times B}{GCD(A, B)}\]

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

python에서는 int overflow가 생기는 경우가 드물지만 다른 언어의 경우에 int의 범위를 넘어갈 수 있으니 연산의 순서를 조정하는 것도 하나의 팁입니다. 또한 큰수를 나누는 연산보다 작은 수를 나누는 연산이 더 빠르니 시간적인 측면에서도 조금의 도움이 됩니다.

4-2. 소수 판별과 에라토스테네스의 체

4-2-a. 소수의 판별

소수 란 약수를 1과 자기자신만을 가지는 수입니다. 1과 합성수를 제외하면 소수이며, 소수는 약수의 개수가 2개입니다. 소수는 신기한 특징을 가지고 있는 수라 종종 흥미로운 문제가 많이 나옵니다.

첫 번째 방법은 다음과 같습니다. 1과 자신 외의 약수가 없다는 정보를 이용합니다.

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

하지만 약수는 \(\sqrt{N}\)을 기준으로 대칭되어 분포합니다. 즉 \(\sqrt{N}\)까지만 반복문을 돌려도 좋다는 의미입니다. 그렇기에 첫번째 방법의 시간복잡도가 \(O(N)\)이었다면, 두번째 방법은 \(O(\sqrt{N})\) 입니다.

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

이 외에는 밀러-라빈 등 확률 기반 소수 판별 방법이 있습니다.

4-2-b. 에라토스테네스의 체

에라토스테네스의 체는 소수 리스트를 여러 번 사용해야할 때 할 수 있는 전처리입니다.

소수를 찾으면, 그 소수 자신을 제외한 소수의 배수는 모두 합성수가 되고, 이를 제외하는 방식으로 소수 리스트를 만들 수 있습니다. 다음 애니메이션을 보면 더욱 이해가 쉬울 것 같습니다.

코드는 다음과 같이 작성할 수 있습니다.

def era(N):
    ret, ck = [], [False for _ in range(N+1)]
    ck[0] = ck[1] = True # 0과 1은 소수가 아니므로
    for i in range(2, N+1):
        if ck[i] : continue
        ret.append(i):
        for j in range(i*i, N+1, i): ck[j] = True
    return ret, ck

전역변수로 선언하는 경우도 있고, 경우에 따라 소수리스트, 소수체크리스트 둘 중 하나만 필요한 경우도 있습니다.

계산 방법은 어렵지만, 시간복잡도는 \(O(n log log n)\)입니다.

4-3. 소인수분해

수를 소인수분해하면 그 후에 여러가지 연산에 편리함이 있는 경우가 있습니다.

소인수분해는 알아두면 좋을 것 같아 넣어둡니다. 한 번쯤은 안보고 코드로 짜보는 연습해보는 것을 추천합니다.

def prime_factor(N):
    ret, p = [], 2
    while N >= p*p: # 이전 소수 판별법의 활용
        if N%p==0: # 수가 나누어 떨어진다면 계속 나누기
            while N%p==0:
                ret.append(p)
                N //= p
        p = p+1 # 아닌 경우에는 다음 수 체크

    # p**2보다 큰 경우는 남은 수 N이 소수라는 의미
    if N > 1 : ret.append(N) 
    return ret

4-4. 2진수와 10진수

문자열을 10진수로 바꾸는 방법은 쉽습니다. int()로 형변환을 진행하면 됩니다. 하지만 2진법 16진법 등은 어떨까요? 이를 10진수를 바탕으로 생각해보겠습니다.

우선 수 1339를 살펴봅시다. 이 수는 천 삼백 삼십 구 라고 읽습니다. 이를 수식으로 표현하면 다음과 같습니다.

\[1339 = 1000 + 300 + 30 + 9\]

각 자리수는 진수의 거듭제곱입니다. 수식으로 표현하면 다음과 같습니다.

\[1339 = 1 \cdot 10^3 + 3 \cdot 10^2 + 3 \cdot 10^1 + 9 \cdot 10^0\]

이를 바탕으로 하면 다음과 같이 연산을 진행할 수 있습니다.

def stoi(s):
    ret, s = 0, s[::-1]
    for idx, val in enumerate(s):
        ret += 10**idx * (ord(val)-ord('0')) # 또는 int(val)
    return ret

하지만 이 방법은 \(O(len(s)^2)\) 라는 시간복잡도를 가지고 있고, 꽤 느립니다. 그래서 역전하지 않고 앞에서부터 구하는 방식을 사용합니다.

\[1339 = ((((1\cdot10)+3)\cdot10)+3)\cdot10+9\]

앞자리부터 *10+다음수 연산을 진행하는 방법입니다. 코드로 보면 다음과 같습니다.

def stoi(s):
    ret = 0
    for i in s:
        ret = ret*10 + ord(i)-ord('0') # 또는 int(i)
    return ret

이 경우에는 시간복잡도가 \(O(len(s))\)가 되어 전의 코드보다 매우 빨라진 것을 알 수 있습니다.

4-5. 수의 거듭제곱과 나머지

파이썬에서 제공하는 pow 함수는 이미 최적화 되어 있습니다. 하지만 이론적으로 수의 거듭제곱을 구하는 과정은 꽤 재미있는 아이디어를 포함하기에 알아두면 좋습니다.

수의 거듭제곱의 예시를 살펴보겠습니다.

\[A^{13} = A^{8 + 4 + 1} = A^{1101_2}\]

단순하게 2진수 변환을 해보았습니다. 그렇다면 이것으로 무엇을 할 수 있을까요? 조금 더 변환해보겠습니다.

\[A^{1101_2} = A^8 \cdot A^4 \cdot A\]

거듭제곱은 이렇게 덧셈처럼 나눌 수 있습니다. 그리고 신기하게 2진수로 나누면 다음과 같이 연산을 할 수 있습니다.

\[A^8 = (A^4)^2 = ((A^2)^2)^2\]

각 항이 제곱관계라는 것입니다. 그러면 13이라는 수를 이진수로 변환한 후에 이를 활용하면 거듭제곱을 좀 더 빠르게 할 수 있지 않을까요? 한 번 코드로 작성해보겠습니다.

# a^b
def pow(a, b):
    ret = 1 # a^0 = 1
    while b > 0 :
        if b%2==1 : ret *= a
        a *= a
        b //=2
    return ret

이제 특정 모듈러를 구해야하는 task를 생각해보겠습니다. 총 2가지 방법이 있습니다.

# a^b%mod
def pow_mod_1(a, b, mod):
    ret = 1
    while b > 0 :
        if b%2==1 : ret *= a
        a *= a
        b //=2
    return ret % mod

def pow_mod_2(a, b, mod):
    ret = 1
    while b > 0 :
        if b%2==1 : ret = ret*a%mod
        a = a*a%mod
        b //=2
    return ret % mod

당연히 mod를 한 번만 하는 위의 방법이 빨라보이지만, 실험해보면 평균적으로 아래 방법이 빠른 것을 알 수 있습니다. 그 이유는 큰 수 연산이 시간이 오래걸리기 때문입니다.

위에서도 이야기 했지만 기본적으로 pow(a, b, mod)는 이미 내장함수로 되어 있기에 따로 구현할 필요는 없습니다.

4-6. 에라토스테네스의 응용

에라토스테네스는 약수와 배수 관계를 활용한 전처리 방법이므로 유사한 task를 처리하기 쉽습니다. 한번 직접 구현해볼까요?

약수의 개수 전처리
약수의 합 전처리
소인수분해 전처리

Chapter. 1