[WEEK01] 정수론

Krafton Jungle/2. Keywords

[WEEK01] 정수론

munsik22 2025. 3. 15. 17:10

프로그래밍을 하면서 정수론을 사용해 알고리즘을 구현함으로써 문제를 해결할 수 있다.

모듈러의 성질

모듈러 연산은 나머지를 구하는 연산으로, 주로 다음과 같은 성질이 있다.

(a+b) % m == (a%m + b%m) % m   # 덧셈
(a*b) % m == (a%m * b%m) % m   # 곱셈
(a-b) % m == (a%m - b%m + m) % m   # 음수가 되면 +c를 해줘야함.
(a+b) % m == (a//m - b//m) % m   # 페르마의 소정리

수학적 증명을 제외하고(책을 읽어도 이해가 안돼서...😂) 최대한 쉽게 설명하자면, 모듈러 연산은 숫자가 너무 큰 수에 대하여 나머지 연산을 해야하는 경우나 연산의 수가 너무 커지는 경우 등에 사용하면 좋다.

2xn 타일링 문제를 풀어보자.

n = int(input())

if n == 1 or n == 2:
    print(n)
else:
    a, b = 1, 2
    for _ in range(n-2):
        a, b = b%10007, (a+b)%10007
    print(b)

이 문제에서는 결과 출력시 10007을 나눈 나머지를 출력하라고 명시되어 있다. 그냥 print(b)를 해도 테스트 예제는 통과하는데, 왜 굳이 10007을 나눈 나머지를 출력해야 할까?

피보나치 수열의 n번째 항은 매우 빠르게 증가한다. 예를 들어, 100번째 피보나치 수는 354224848179261915075로, 일반적인 데이터 타입의 범위를 초과하는 오버플로우(overflow)가 발생할 수 있다. 따라서, 결과를 일정한 범위로 제한하기 위해 모듈러 연산을 사용한다. 이 경우, 10007로 나눈 나머지를 구함으로써 피보나치 수를 0부터 10006 사이의 값으로 줄일 수 있다.

페르마의 소정리

이항계수를 빠르게 구할 수 있는 정리라고 한다.

p가 소수이고 a가 p로 나누어지지 않는 정수이면 a^p-1 ≡ 1 (mod p)이다.
모든 a에 대하여, a^p ≡ a (mod p)이다.

소수 판정

소수는 1과 자기 자신만으로 나누어 떨어지는 자연수이다. 소수를 판별하는 방법은 여러 가지가 있다.

단순 나눗셈: 2부터 √𝑛까지 나누어 보며 소수를 판별한다.
에라토스테네스의 체: 소수를 효율적으로 찾는 알고리즘으로, 일정 범위 내의 소수를 찾는 데 유용하다.

소수 찾기 문제는 다음과 같이 풀 수 있다.

import sys
def is_prime(n):
    if(n == 1):
        return False
    for i in range(2, n):
        if(n % i == 0):
            return False
    return True

n = int(input())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
for i in arr:
    if(is_prime(i)):
        cnt += 1
print(cnt)

에라토스테네스의 체

위에서 작성한 코드는 소수를 구하는 가장 직관적인 방법이지만, 큰 범위의 소수를 모두 구하기에 좋은 코드는 아니다. 수학자 에라토스테네스는 소수를 구하기 위해 다음과 같이 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법을 제안했다.

1은 제거한다
지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
...

다음은 소수 찾기 문제를 에라토스테네스의 체 알고리즘을 사용해 다시 푼 코드이다.

def prime_numbers(n):
    arr = [i for i in range(n+1)]
    end = int(n**(1/2))
    for i in range(2, end+1):
        if arr[i] == 0: continue
        for j in range(i*i, n+1, i): arr[j] = 0
    return [i for i in arr[2:] if arr[i]]

n = int(input())
nums = list(map(int, input().split()))
prime = prime_numbers(max(nums))

answer = sum(1 for i in nums if i in prime)
print(answer)

채점 결과 시간이 4ms 정도 단축되었다. is_prime(n)의 경우 2부터 n-1까지 반복하기 때문에 시간 복잡도가 O(n)인데 반해, 에라토스테네스의 체 알고리즘을 적용한 prime_numbers(n)의 경우 O(n log log n)의 시간 복잡도를 가져 매우 효율적인 코드라고 할 수 있다.

밀러-라빈 소수 판별법

앞에서 에라토스테네스의 체 알고리즘은 O(n log log n)의 시간 복잡도를 가져 매우 효율적인 코드라고 설명했지만, 이마저도 long long 단위의 매우 큰 수에서는 비효율적이게 된다.🤯

밀러-라빈 소수 판별법은 확률적으로 소수를 판별하는 알고리즘으로, 의 시간복잡도를 가지며, long long 범위 정도에 대해서는 결정론적으로도 소수를 판별할 수 있다. 2^64 이하의 소수들 중에서는 2에서 37까지만 확정적으로 소수임을 판별할 수 있다고 한다.

밀러-라빈 판정법은 기존의 소수 판정법들과는 달리 확률적으로 동작하지만, 상당히 빠른 시간 복잡도를 달성할 수 있다.

수학적인 증명은 생략하고, 결과적으로 밀러-라빈 판정식은 다음 식을 모두 만족하지 않는 n을 소수일 가능성이 있다고 판단한다.

a^d ≠ 1 (mod n)
a^{2^rd} ≠ -1 (mod n) for all 0 ≤ r ≤ s-1

밀러-라빈의 판정법은 다음과 같다.

임의의 수 a를 선정 : n < 264에 대해 a = 2, 3, 5, …, 31, 37만 검사해도 충분함
x = a^d mod n을 계산
x = 1 or -1이면 True를 반환
d가 n-1이 아닌 동안 다음을 반복
- x = x² mod n을 계산
- x = 1이면 False, x = n-1이면 True 반환

def miller_rabin(n, a):
    d = n - 1
    while d % 2 == 0:
        d //= 2

    x = pow(a, d, n)

	# x가 1 또는 n-1이면 소수
    if x == 1 or x == n-1: return True
    
    while d != n-1:
        x = pow(x, 2, n)
        d *= 2

        # x가 1이면 합성수이고 아니면 소수
        if x == 1: return False
        if x == n-1: return True 
    
    return False

def isPrime(n):
    if n == 2 or n == 3: return True
    if n == 1 or n%2 == 0: return False
    
    for a in [2,3]: #n < 1,373,653의 수에 대해서는 a = 2, 3만 검사해도 충분함
        # 밀러-라빈이 성립하면 소수
        # 성립하지 않아 false를 반환하면 소수가 아님
        if not miller_rabin(n, a): 
            return False
            
    return True;
    
# [출처] https://randomsampling.tistory.com/225 [Let IT Begin:티스토리]

약수 구하기

정수의 약수는 그 정수를 나누어 떨어지게 하는 자연수들이다. 약수를 구하는 방법은 다음과 같다.

𝑛의 약수는 1부터 √𝑛까지 나누어 보면서 구할 수 있다.
만약 𝑖가 𝑛의 약수라면, 𝑛/𝑖도 약수이다.

약수 구하기 문제는 다음과 같이 풀 수 있다.

import sys

n, k = map(int, sys.stdin.readline().split())
cnt = 0
answer = 0

for i in range(1, n+1):
    if n % i == 0:
        cnt += 1
        if cnt == k:
            answer = i
            break

print(answer)

소인수 분해

소인수 분해는 자연수를 소수의 곱으로 표현하는 과정이다. 소인수 분해를 수행하는 방법은 다음과 같다.

2부터 시작하여 각 소수로 나누어 보며, 나눌 수 있을 때까지 반복한다.
나누어 떨어지면 그 소수를 결과에 추가하고, 나눈 결과로 다시 반복한다.

소인수분해 문제는 다음과 같이 풀 수 있다.

n = int(input())
d = 2
while n > 1:
    while n % d == 0:
        print(d)
        n //= d
    d += 1

유클리드 호제법 (Euclidean-algorithm)

유클리드 호제법은 최대공약수를 구하는 대표적인 알고리즘이다. 여기서 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다. 다음과 같은 원리로 최대공약수를 찾는다.

gcd(𝑎, 𝑏) = gcd(𝑏, 𝑎 % 𝑏)
이 과정을 반복하면, 𝑏가 0이 될 때의 𝑎가 최대공약수이다.

간단하게 말하면, 유클리드 호제법은 MOD연산을 반복하는 것이다.

최대공약수와 최소공배수를 구하는 문제는 다음과 같이 풀 수 있다.

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

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

a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))

여기서 gcd는 최대공약수를, lcm은 최소공배수를 의미한다. 참고로, 파이썬의 math 모듈은 gcd과 lcm을 구하는 메서드를 제공하기 때문에 다음과 같이 풀 수도 있다.

import math
print(math.gcd(a, b))
print(math.lcm(a, b))

빠른 거듭제곱

빠른 거듭제곱은 큰 수의 거듭제곱을 효율적으로 계산하는 방법이다. 주로 분할 정복을 이용하여 수행한다.

예를 들어, a^b를 다음과 같이 계산할 수 있다.

짝수인 경우 : a^b/2 * a^b/2
홀수인 경우 : a * a^(b-1)/2 * a^(b-1)/2

def pows(n, m):
    if m == 0:
        return 1
    
    ret = pows(n, m // 2)
    ret *= ret
    ret %= 1000000007

    if m % 2 == 0:
        return ret * ret
    else:
        return (ret * n) % 1000000007

반복 제곱

반복 제곱(repeated squaring)은 모듈러에 의한 거듭제곱을 구하는 연산인 모듈러 지수(modular exponentiation) 연산을 효율적으로 풀기 위한 연산이다.

음이 아닌 정수 a와 b에 대해 a^b를 계산하기 위해서 반복 제곱은 다음 식을 기반으로 한다.

입력 a, b, n이 B비트의 수이면, 필요한 총 산술 연산 수는 O(B), 총 비트 연산의 수는 O(B³)이다.

def mod_expo(a, b, n):
    if b == 0:
        return 1
    elif b % 2 == 0:
        d = mod_expo(a, b//2, n)
        return (a*d) % n
    else:
        d = mod_expo(a, b-1, n)
        return (a*d) % n

한편, 파이썬의 기본 내장 메서드 pow()는 모듈러 연산을 지원하기 때문에 간단하게 다음처럼 작성해도 된다.

참고자료 : [Python] 파이썬에서 제곱 구하기-pow(), math.pow(), ** 의 차이

pow(a, b, n)

정수론에서 이해가 잘 되지 않는 부분이 많기 때문에 추후에 다시 공부할 예정이다.☠ ☠ ☠

'Krafton Jungle > 2. Keywords' 카테고리의 다른 글

[WEEK02] 이진 탐색 (0)	2025.03.20
[WEEK01] 완전 탐색 (0)	2025.03.18
[WEEK01] 복잡도와 정렬 (0)	2025.03.16
[WEEK01] 반복문과 재귀 함수 (0)	2025.03.15
[WEEK01] 배열과 문자열 (0)	2025.03.15

현재글[WEEK01] 정수론

MUNSIK BLOG

munsik22 님의 블로그 입니다.

합격후기, C, 문식이, NextJS, 크래프톤정글, 프로그래머스, 나만무, 정보처리기사, csapp, malloc, 레드블랙트리, webproxy, 오답노트, springboot, pintos, C++, 백준,

Today :
Yesterday :

[Munsik] MUNSIK BLOG [Munsik]