알고리즘 문제를 풀다 보면 특정 수학적 개념들이 반복적으로 등장합니다. 이러한 개념들을 확실히 이해하고 있다면 문제 해결 과정이 훨씬 수월해집니다. 오늘은 알고리즘 문제 풀이에 자주 등장하는 핵심 수학 개념들을 살펴보겠습니다.
1. 모듈러 연산(Modular Arithmetic)
모듈러 연산은 큰 수를 다룰 때 특히 유용합니다. 많은 알고리즘 문제에서 “결과를 10^9+7로 나눈 나머지를 출력하라”와 같은 조건이 붙는 이유는 바로 이 때문입니다.
핵심 성질
(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(음수 방지)(a / b) % m = ((a % m) * (b^(m-2) % m)) % m(페르마의 소정리 이용, m이 소수일 때)
def power_mod(base, exponent, modulus):
result = 1
base = base % modulus
while exponent > 0:
if exponent % 2 == 1:
result = (result * base) % modulus
exponent = exponent >> 1
base = (base * base) % modulus
return result
이 알고리즘은 O(log n) 시간 복잡도로 (base^exponent) % modulus를 계산합니다. 이는 매우 큰 수의 거듭제곱을 효율적으로 계산할 때 필수적입니다.
2. 최대공약수(GCD)와 최소공배수(LCM)
두 수의 최대공약수는 유클리드 알고리즘을 사용하여 효율적으로 계산할 수 있습니다.
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
확장 유클리드 알고리즘
ax + by = gcd(a, b)를 만족하는 x, y를 찾는 알고리즘입니다. 모듈러 역원을 구하는 데 활용됩니다.
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_gcd(b % a, a)
return gcd, y - (b // a) * x, x
3. 소수 판별 및 에라토스테네스의 체
소수 관련 문제는 알고리즘 대회에서 빈번하게 등장합니다.
단일 소수 판별
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
에라토스테네스의 체
주어진 범위 내의 모든 소수를 찾는 가장 효율적인 알고리즘입니다.
def sieve_of_eratosthenes(n):
primes = [True for i in range(n+1)]
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n+1, p):
primes[i] = False
p += 1
prime_list = []
for p in range(2, n+1):
if primes[p]:
prime_list.append(p)
return prime_list
4. 조합론 기초
순열과 조합
nPr과 nCr을 계산하는 방법입니다.
def factorial(n):
result = 1
for i in range(2, n+1):
result *= i
return result
def permutation(n, r):
return factorial(n) // factorial(n-r)
def combination(n, r):
return factorial(n) // (factorial(r) * factorial(n-r))
대규모 조합을 계산할 때는 모듈러 연산과 함께 페르마의 소정리를 활용할 수 있습니다.
def modular_combination(n, r, mod):
if r < 0 or r > n:
return 0
# 팩토리얼 미리 계산
fact = [1]
for i in range(1, n+1):
fact.append((fact[-1] * i) % mod)
# nCr = n! / (r! * (n-r)!)
numerator = fact[n]
denominator = (fact[r] * fact[n-r]) % mod
# 페르마의 소정리를 이용한 모듈러 역원 계산
# a^(m-1) ≡ 1 (mod m) -> a^(m-2) ≡ a^(-1) (mod m)
denominator_inv = power_mod(denominator, mod-2, mod)
return (numerator * denominator_inv) % mod
5. 이산수학과 그래프 이론
그래프 표현 방법
인접 행렬과 인접 리스트는 그래프를 표현하는 가장 기본적인 방법입니다.
# 인접 행렬 (0-기반 인덱싱)
adj_matrix = [[0] * n for _ in range(n)]
for u, v in edges:
adj_matrix[u][v] = 1
adj_matrix[v][u] = 1 # 무방향 그래프일 경우
# 인접 리스트
adj_list = [[] for _ in range(n)]
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u) # 무방향 그래프일 경우
오일러 경로와 해밀턴 경로
- 오일러 경로: 그래프의 모든 간선을 정확히 한 번씩 지나는 경로
- 오일러 회로: 시작점과 끝점이 같은 오일러 경로
- 해밀턴 경로: 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로
- 해밀턴 회로: 시작점과 끝점이 같은 해밀턴 경로
오일러 경로는 다항 시간에 찾을 수 있지만, 해밀턴 경로 찾기는 NP-완전 문제입니다.
6. 동적 계획법에서의 수학적 관계
동적 계획법(DP)은 많은 알고리즘 문제에서 사용되는 기법으로, 대표적인 예시를 통해 이해해 봅시다.
피보나치 수열
def fibonacci(n):
if n <= 1:
return n
fib = [0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
이항 계수
def binomial_coefficient(n, k):
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for i in range(n+1):
for j in range(min(i, k)+1):
if j == 0 or j == i:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
return dp[n][k]
7. 확률과 기댓값
확률 문제는 종종 기댓값 계산을 요구합니다. 기댓값은 각 사건의 확률과 그 사건의 값을 곱한 것의 합으로 계산됩니다.
# 주사위를 던졌을 때 기댓값
def dice_expectation():
# 1부터 6까지 나올 확률은 각각 1/6
values = [1, 2, 3, 4, 5, 6]
probabilities = [1/6] * 6
expectation = sum(value * prob for value, prob in zip(values, probabilities))
return expectation # 결과는 3.5
결론
알고리즘 문제를 해결할 때 이러한 수학적 개념을 이해하고 적용하는 능력은 매우 중요합니다. 특히 모듈러 연산, GCD/LCM, 소수 판별, 조합론, 그래프 이론, 동적 계획법, 확률과 기댓값 등은 알고리즘 대회나 코딩 인터뷰에서 자주 등장하는 주제입니다.
이러한 개념들을 꾸준히 학습하고 실전 문제에 적용해보면서 실력을 쌓아가는 것이 중요합니다. 수학적 직관과 논리적 사고를 기르면 복잡한 알고리즘 문제도 체계적으로 접근할 수 있게 됩니다.
답글 남기기