# [06-07] 무작위 알고리즘 (Randomized Algorithms)
무작위 알고리즘은 확률과 난수를 이용하여 문제를 해결하는 알고리즘으로, 때로는 결정론적 방법보다 더 효율적이거나 간단한 해결책을 제공합니다.
🎯 무작위 알고리즘이란 무엇인가
무작위 알고리즘 (Randomized Algorithm)의 기본 개념
무작위 알고리즘은 실행 중에 난수(random number)를 사용하여 결정을 내리는 알고리즘입니다.
실생활 비유:
음식점 선택:
결정론적 방법:
"항상 가장 가까운 음식점"
→ 같은 입력이면 항상 같은 결과
무작위 방법:
"주사위를 던져서 결정"
→ 같은 입력이라도 매번 다른 결과 가능
왜 이게 좋을까?
1. 간단함: 복잡한 비교 불필요
2. 공평함: 모든 선택지에 기회
3. 예측 불가: 남들이 예상 못함또 다른 예시:
- 카드 섞기: 무작위로 섞어야 공평
- 샘플링: 일부만 검사해도 전체 파악
- 암호: 예측 불가능해야 안전
왜 무작위성을 사용하는가?
무작위 알고리즘이 필요한 이유를 이해하는 것이 중요합니다.
1. 최악의 경우 회피
퀵 정렬:
결정론적 피벗 선택 (항상 첫 원소):
입력: [1, 2, 3, 4, 5] (이미 정렬됨)
→ 최악의 경우: O(n²)
무작위 피벗 선택:
입력: [1, 2, 3, 4, 5]
→ 피벗이 무작위 → 평균 O(n log n)
→ 최악의 경우를 만들기 어려움!2. 간단한 구현
중복 원소 찾기:
결정론적:
- 정렬 후 비교: O(n log n)
- 또는 해시 테이블: O(n) + 추가 공간
무작위:
- 2개씩 무작위로 뽑아서 비교
- 구현 간단, 확률적으로 빠름3. 평균 성능 개선
많은 경우에:
무작위 버전 평균 > 결정론적 최악4. 예측 불가능성
게임 AI, 암호학:
- 상대가 패턴 파악 못함
- 보안 강화무작위 알고리즘의 두 가지 유형
무작위 알고리즘은 크게 두 가지로 분류됩니다:
1. 라스베이거스 알고리즘 (Las Vegas Algorithm)
특징:
- 결과는 항상 정확
- 실행 시간이 확률적
예: 무작위 퀵 정렬
- 정렬 결과는 항상 정확
- 하지만 실행 시간은 매번 다를 수 있음
카지노 비유:
라스베이거스에서 도박:
"이길 때까지 계속 (결과는 확실, 시간은 모름)"2. 몬테카를로 알고리즘 (Monte Carlo Algorithm)
특징:
- 실행 시간은 일정
- 결과가 확률적으로 정확
예: 원주율 근사
- 항상 같은 시간 안에 완료
- 하지만 결과가 정확하지 않을 수 있음
카지노 비유:
몬테카를로 카지노:
"정해진 시간만큼만 (시간은 확실, 결과는 근사)"비교표:
특징 라스베이거스 몬테카를로
-------------------------------------------------
결과 정확도 항상 정확 확률적 정확
실행 시간 확률적 일정
예시 무작위 퀵정렬 원주율 근사
사용 사례 정확성 중요 빠른 근사 중요무작위성의 원천
무작위 알고리즘은 어떻게 난수를 얻을까요?
의사난수 생성기 (Pseudorandom Number Generator, PRNG):
import random
# 시드 설정
random.seed(42)
# 난수 생성
print(random.randint(1, 10)) # 1~10 사이 정수
print(random.random()) # 0~1 사이 실수
print(random.choice([1,2,3])) # 리스트에서 무작위 선택주의사항:
의사난수:
- 진짜 무작위가 아님
- 알고리즘으로 생성됨
- 같은 시드 → 같은 수열
진짜 무작위:
- 물리적 현상 이용 (노이즈, 방사선 등)
- 암호학에서 필요
- 일반 알고리즘에서는 의사난수로 충분이제 구체적인 무작위 알고리즘들을 살펴봅시다.
🎲 무작위 퀵 정렬
퀵 정렬의 문제점
앞서 분할 정복에서 퀵 정렬을 배웠습니다. 하지만 퀵 정렬에는 치명적인 약점이 있습니다.
문제 복습:
퀵 정렬:
1. 피벗을 선택
2. 피벗보다 작은 것은 왼쪽, 큰 것은 오른쪽
3. 재귀적으로 정렬
평균: O(n log n) - 빠름!
최악: O(n²) - 느림!최악의 경우:
배열: [1, 2, 3, 4, 5]
피벗을 항상 첫 원소로 선택
1회차: 피벗 1
[1] | [2, 3, 4, 5]
↑ ↑
0개 n-1개 (불균형!)
2회차: 피벗 2
[2] | [3, 4, 5]
3회차: 피벗 3
[3] | [4, 5]
...
결과: O(n²)왜 이런 일이?
문제: 피벗 선택이 고정적
→ 특정 입력에서 항상 최악
해결: 피벗을 무작위로!
→ 최악의 입력을 만들기 어려움무작위 퀵 정렬
무작위 퀵 정렬은 피벗을 무작위로 선택합니다.
핵심 아이디어:
결정론적 퀵 정렬:
피벗 = arr[0] (항상 첫 원소)
무작위 퀵 정렬:
피벗 = arr[random_index] (무작위!)
효과:
- 어떤 입력이든 평균 O(n log n) 기대
- 최악의 경우를 의도적으로 만들기 어려움구현
import random
def quicksort_randomized(arr):
"""
무작위 퀵 정렬 (라스베이거스 알고리즘)
arr: 정렬할 배열
Returns:정렬된 배열
특징:
- 결과는 항상 정확 (올바르게 정렬됨)
- 실행 시간은 확률적
- 평균 O(n log n) 기대
"""
# 기저 조건
if len(arr) <= 1:
return arr
# ===== 무작위 피벗 선택 =====
# 핵심: 피벗을 무작위로!
pivot_index = random.randint(0, len(arr) - 1)
pivot = arr[pivot_index]
# ===== 분할 =====
# 피벗보다 작은 것, 같은 것, 큰 것으로 나누기
left = [] # 피벗보다 작은 것
middle = [] # 피벗과 같은 것
right = [] # 피벗보다 큰 것
for num in arr:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
else:
middle.append(num)
# ===== 정복 & 합치기 =====
# 재귀적으로 정렬 후 합치기
return (quicksort_randomized(left) +
middle +
quicksort_randomized(right))
# 사용 예시
arr = [3, 7, 8, 5, 2, 1, 9, 5, 4]
print(f"원본: {arr}")
sorted_arr = quicksort_randomized(arr)
print(f"정렬: {sorted_arr}")
# 최악의 경우 입력에도 강함
worst_case = list(range(1000)) # 이미 정렬됨
import time
start = time.time()
quicksort_randomized(worst_case)
end = time.time()
print(f"\n정렬된 1000개 배열 처리 시간: {end - start:.4f}초")제자리 정렬 버전:
def quicksort_inplace(arr, low=0, high=None):
"""
무작위 퀵 정렬 - 제자리 정렬 버전
메모리 효율적 (추가 공간 O(log n))
arr: 정렬할 배열 (직접 수정됨)
low: 정렬할 구간의 시작 인덱스
high: 정렬할 구간의 끝 인덱스
"""
if high is None:
high = len(arr) - 1
if low < high:
# 무작위 피벗 선택 및 분할
pivot_index = partition_random(arr, low, high)
# 재귀적으로 정렬
quicksort_inplace(arr, low, pivot_index - 1)
quicksort_inplace(arr, pivot_index + 1, high)
def partition_random(arr, low, high):
"""
무작위 피벗으로 배열 분할
arr: 배열
low, high: 분할할 구간
Returns: 피벗의 최종 위치
동작:
1. 무작위로 피벗 선택
2. 피벗을 끝으로 이동
3. 피벗보다 작은 것들을 왼쪽으로
4. 피벗을 중간에 배치
"""
# 1. 무작위 피벗 선택
pivot_index = random.randint(low, high)
# 2. 피벗을 끝으로 이동 (처리 편의를 위해)
arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
pivot = arr[high]
# 3. 분할
i = low - 1 # i: 작은 원소들의 경계
for j in range(low, high):
# 현재 원소가 피벗보다 작으면
if arr[j] < pivot:
i += 1
# 작은 원소 영역으로 이동
arr[i], arr[j] = arr[j], arr[i]
# 4. 피벗을 중간에 배치
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 사용 예시
arr = [3, 7, 8, 5, 2, 1, 9, 5, 4]
print(f"원본: {arr}")
quicksort_inplace(arr)
print(f"정렬: {arr}")성능 분석:
결정론적 퀵 정렬:
최선: O(n log n) - 피벗이 항상 중간
평균: O(n log n)
최악: O(n²) - 피벗이 항상 끝 (악의적 입력 가능)
무작위 퀵 정렬:
기대 시간: O(n log n) - 모든 입력에서!
최악: O(n²) - 이론적으로 가능하지만 확률 극히 낮음
확률 계산:
n=1000일 때 O(n²)이 될 확률 < 0.0001%🎯 몬테카를로 방법: 원주율 근사
몬테카를로 방법 (Monte Carlo Method)이란?
몬테카를로 방법은 무작위 샘플링을 이용하여 수치적 결과를 근사하는 기법입니다.
왜 "몬테카를로"?
모나코의 유명한 카지노 "몬테카를로"에서 이름을 땀
→ 확률과 난수를 이용한다는 의미핵심 아이디어:
복잡한 계산을 무작위 시뮬레이션으로 대체
예: 원의 넓이 구하기
정확한 방법: π × r²
몬테카를로: 무작위로 점을 찍어서 비율로 추정원주율(π) 근사하기
몬테카를로 방법으로 π를 근사하는 유명한 예제입니다.
원리:
1×1 정사각형 안에 반지름 1인 1/4 원
정사각형 넓이: 1 × 1 = 1
1/4 원 넓이: π × 1² / 4 = π/4
비율: (π/4) / 1 = π/4
따라서: π ≈ 4 × (원 안 점 수 / 전체 점 수)시각화:
1 ┌─────────┐
│ ● ● │
│ ●●●● │
│ ●●●●● ● │
│●●●●● │
│ ●●● ● │
0 └─────────┘
0 1
원 안 점: ●
원 밖 점: (없음, 원 안만 그림)
무작위로 점을 많이 찍으면:
원 안 점 수 / 전체 점 수 ≈ π/4구현
import random
import math
def monte_carlo_pi(num_samples):
"""
몬테카를로 방법으로 원주율 근사 (몬테카를로 알고리즘)
num_samples: 샘플 개수 (많을수록 정확)
Returns: 원주율 근사값
특징:
- 실행 시간 일정 (샘플 개수에 비례)
- 결과는 근사값 (정확하지 않을 수 있음)
- 샘플이 많을수록 정확
원리:
1. 1×1 정사각형 안에 무작위 점 생성
2. 점이 반지름 1인 1/4 원 안에 있는지 확인
3. 비율로 π 계산
"""
inside_circle = 0 # 원 안에 있는 점 수
for _ in range(num_samples):
# 무작위 점 생성 (0 ≤ x, y ≤ 1)
x = random.random()
y = random.random()
# 원점에서의 거리 계산
# 1/4 원이므로 원점은 (0, 0)
distance = math.sqrt(x**2 + y**2)
# 거리가 1 이하면 원 안(반지름이 1인 원)
if distance <= 1:
inside_circle += 1
# π 근사 계산
# 원 안 점 비율 ≈ π/4
# 따라서 π ≈ 4 × 비율
pi_estimate = 4 * (inside_circle / num_samples)
return pi_estimate
# 사용 예시
print(f"실제 π: {math.pi:.10f}\n")
# 샘플 수를 늘려가며 실험
for num_samples in [100, 1000, 10000, 100000, 1000000]:
pi_estimate = monte_carlo_pi(num_samples)
error = abs(pi_estimate - math.pi)
print(f"샘플 {num_samples:7d}개: {pi_estimate:.10f} (오차: {error:.10f})")
# 여러 번 실행해보기 (확률적 결과 확인)
print("\n10000개 샘플로 10번 실행:")
for i in range(10):
pi_estimate = monte_carlo_pi(10000)
print(f" {i+1}회: {pi_estimate:.6f}")실행 결과 예시:
실제 π: 3.1415926536
샘플 100개: 3.2000000000 (오차: 0.0584073464)
샘플 1000개: 3.1320000000 (오차: 0.0095926536)
샘플 10000개: 3.1412000000 (오차: 0.0003926536)
샘플 100000개: 3.1425600000 (오차: 0.0009673464)
샘플 1000000개: 3.1413880000 (오차: 0.0002046536)
10000개 샘플로 10번 실행:
1회: 3.138800
2회: 3.145200
3회: 3.136000
4회: 3.148800
5회: 3.142400
6회: 3.139600
7회: 3.144000
8회: 3.137200
9회: 3.143200
10회: 3.141600
관찰:
- 샘플이 많을수록 정확
- 매번 결과가 조금씩 다름
- 하지만 실제 π 근처에 몰려 있음🃏 무작위 섞기: Fisher-Yates 알고리즘
카드 섞기 문제
카드를 공평하게 섞는 것은 생각보다 어려운 문제입니다.
왜 중요한가?
게임, 시뮬레이션:
- 공평한 무작위성 필요
- 잘못 섞으면 특정 패턴 발생
예: 포커 게임
잘못된 섞기 → 특정 카드가 자주 등장 → 불공평!나쁜 섞기 방법:
# 나쁜 방법 1: 정렬 기반
def bad_shuffle_1(arr):
return sorted(arr, key=lambda x: random.random())
# 문제: 균등 분포가 아님
# 나쁜 방법 2: 무작위 교환 (잘못된 구현)
def bad_shuffle_2(arr):
for i in range(len(arr)):
j = random.randint(0, len(arr) - 1)
arr[i], arr[j] = arr[j], arr[i]
# 문제: 편향된 분포Fisher-Yates 섞기 알고리즘
Fisher-Yates 알고리즘은 배열을 균등하게 섞는 표준 방법입니다.
핵심 아이디어:
뒤에서부터 앞으로 진행하며:
1. 현재 위치와 이전 위치 중 하나를 무작위 선택
2. 교환
3. 반복
왜 이게 공평한가?
- 각 원소가 각 위치에 올 확률이 정확히 1/n
- 수학적으로 증명됨구현
import random
def fisher_yates_shuffle(arr):
"""
Fisher-Yates 섞기 알고리즘 (라스베이거스)
arr: 섞을 배열 (직접 수정됨)
특징:
- 결과는 항상 정확 (균등 분포)
- 시간복잡도: O(n)
- 제자리 알고리즘 (추가 공간 불필요)
원리:
뒤에서부터 앞으로:
- i번째 원소를 0~i 중 하나와 교환
- 각 순열이 동일한 확률로 생성됨
"""
n = len(arr)
# 뒤에서부터 앞으로
for i in range(n - 1, 0, -1):
# 0부터 i까지 중 하나를 무작위 선택
#
# 왜 i까지?
# → i번째 원소가 자기 자리에 남을 수도 있어야 공평
j = random.randint(0, i)
# 교환
arr[i], arr[j] = arr[j], arr[i]
# 사용 예시
cards = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']
print(f"원본: {cards}")
fisher_yates_shuffle(cards)
print(f"섞음: {cards}")
# 공평성 검증: 1000번 섞어서 분포 확인
def verify_fairness():
"""
Fisher-Yates가 정말 공평한지 확인
[1, 2, 3]을 10000번 섞어서 각 순열의 출현 빈도 확인
"""
from collections import Counter
results = []
for _ in range(10000):
arr = [1, 2, 3]
fisher_yates_shuffle(arr)
results.append(tuple(arr))
# 빈도 계산
counter = Counter(results)
print("\n공평성 검증 (10000번 섞기):")
print("순열 빈도 비율")
print("-" * 30)
for perm, count in sorted(counter.items()):
ratio = count / 10000
print(f"{perm} {count:5d} {ratio:.1%}")
print("\n이론적 확률: 각 순열 16.67%")
print("실제로 거의 균등하게 분포!")
verify_fairness()실행 결과 예시:
원본: ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']
섞음: ['7', 'Q', '3', 'A', '9', '5', 'K', '2', '4', '10', '8', '6', 'J']
공평성 검증 (10000번 섞기):
순열 빈도 비율
------------------------------
(1, 2, 3) 1659 16.6%
(1, 3, 2) 1672 16.7%
(2, 1, 3) 1663 16.6%
(2, 3, 1) 1684 16.8%
(3, 1, 2) 1656 16.6%
(3, 2, 1) 1666 16.7%
이론적 확률: 각 순열 16.67%
실제로 거의 균등하게 분포!단계별 동작:
배열: [1, 2, 3, 4, 5]
i=4: arr[4]와 arr[0~4] 중 하나 교환
j=1 선택
[1, 5, 3, 4, 2]
i=3: arr[3]와 arr[0~3] 중 하나 교환
j=3 선택 (자기 자신)
[1, 5, 3, 4, 2]
i=2: arr[2]와 arr[0~2] 중 하나 교환
j=0 선택
[3, 5, 1, 4, 2]
i=1: arr[1]와 arr[0~1] 중 하나 교환
j=1 선택
[3, 5, 1, 4, 2]
결과: [3, 5, 1, 4, 2]🎰 확률적 소수 판정
소수 (Prime Number) 판정 문제
소수인지 확인하는 것은 중요한 문제입니다.
왜 중요한가?
암호학:
- RSA 암호화: 큰 소수 2개 필요
- 수백 자리 소수를 빠르게 찾아야 함
문제:
- 결정론적 방법: 느림 (큰 수에서)
- 무작위 방법: 빠름 + 높은 정확도결정론적 방법:
def is_prime_deterministic(n):
"""
결정론적 소수 판정
시간복잡도: O(√n)
결과: 100% 정확
"""
if n < 2:
return False
# 2부터 √n까지 나눠보기
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False # 약수 발견 → 합성수
return True # 약수 없음 → 소수
# 문제: n이 크면 (예: 100자리) 매우 느림Miller-Rabin 소수 판정
Miller-Rabin 알고리즘은 확률적 소수 판정 방법입니다 (몬테카를로).
핵심 아이디어:
페르마의 소정리 응용:
n이 소수이고 a가 n과 서로소이면:
a^(n-1) ≡ 1 (mod n)
역으로:
a^(n-1) ≡ 1 (mod n)이 아니면
→ n은 확실히 합성수!
여러 번 테스트:
- k번 테스트해서 모두 통과 → 아마도 소수
- 한 번이라도 실패 → 확실히 합성수구현
import random
def miller_rabin(n, k=5):
"""
Miller-Rabin 소수 판정 (몬테카를로 알고리즘)
n: 판정할 수
k: 테스트 반복 횟수 (많을수록 정확)
Returns: - True: 아마도 소수 (확률적)
- False: 확실히 합성수
특징:
- 실행 시간: O(k log³ n) - 빠름
- 정확도: 틀릴 확률 < (1/4)^k
- k=5이면 틀릴 확률 < 0.1%
원리:
페르마의 소정리를 이용한 확률적 판정
"""
# 작은 수는 직접 처리
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# n-1을 2^r × d로 표현(d는 홀수)
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# k번 테스트
for _ in range(k):
# 무작위 증인(witness) 선택
a = random.randint(2, n - 2)
# a^d mod n 계산
x = pow(a, d, n)
# 테스트
if x == 1 or x == n - 1:
continue # 이번 테스트 통과
# r-1번 제곱
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break # 통과
else:
# 모든 제곱에서 실패
return False # 확실히 합성수!
# 모든 테스트 통과
return True # 아마도 소수
# 사용 예시
print("소수 판정 (Miller-Rabin):\n")
test_numbers = [
(17, "소수"),
(18, "합성수"),
(97, "소수"),
(100, "합성수"),
(1009, "소수"),
(1000, "합성수"),
]
for num, answer in test_numbers:
result = miller_rabin(num, k=5)
status = "소수" if result else "합성수"
correct = "✓" if status == answer else "✗"
print(f"{num:5d}: {status:5s} {correct} (정답: {answer})")
# 큰 수 테스트
print("\n큰 수 테스트:")
large_prime = 1000000007 # 실제로 소수
print(f"{large_prime}: {miller_rabin(large_prime, k=10)}")
import time
start = time.time()
result = miller_rabin(large_prime, k=10)
end = time.time()
print(f"판정 시간: {end - start:.6f}초")💡 실무 팁
무작위 알고리즘을 사용할 때
- 재현 가능성이 필요하면 시드 설정
import random
# 디버깅/테스트용: 같은 결과
random.seed(42)
result1 = my_random_algorithm()
random.seed(42)
result2 = my_random_algorithm()
# result1 == result2
# 운영 환경: 시드 설정 안함 (진짜 무작위)- 정확도 vs 속도 트레이드오프
# 빠르지만 덜 정확
monte_carlo_pi(1000)
# 느리지만 더 정확
monte_carlo_pi(1000000)
# 용도에 맞게 선택!- 무작위성 품질
# 일반 용도: random 모듈
import random
random.randint(1, 10)
# 암호학: secrets 모듈
import secrets
secrets.randbelow(10) # 더 안전한 난수알고리즘 선택
라스베이거스 (정확성 중요):
- 정렬, 검색
- 정확한 결과 필수
몬테카를로 (속도 중요):
- 근사 계산 (π, 적분)
- 시뮬레이션
- 빠른 판정 (소수)🎯 핵심 정리
무작위 알고리즘의 본질
- 난수를 이용하여 결정
- 확률적 성능 또는 정확도
- 때로는 결정론적보다 우수
두 가지 유형
라스베이거스:
- 결과 항상 정확
- 시간 확률적
- 예: 무작위 퀵 정렬
몬테카를로:
- 시간 일정
- 결과 확률적
- 예: π 근사, Miller-Rabin장점
1. 최악의 경우 회피
2. 구현 간단
3. 평균 성능 우수
4. 예측 불가능성주의사항
1. 진짜 무작위 필요 시: secrets 사용
2. 재현성 필요 시: 시드 설정
3. 확률적 정확도 이해
4. 적절한 테스트 횟수 선택시간복잡도 비교
알고리즘 결정론적 무작위
--------------------------------------------------
퀵 정렬 평균 O(n log n) O(n log n) 기대
퀵 정렬 최악 O(n²) O(n²) 확률 낮음
소수 판정 O(√n) O(k log³ n)🔗 다음 글에서는
[06-08] 그래프 알고리즘
- 그래프의 기본 개념: 정점과 간선으로 관계를 표현하는 자료구조
- 그래프 표현 방법: 인접 행렬과 인접 리스트의 장단점
- 그래프 탐색: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)
- 최단 경로: 다익스트라 알고리즘으로 최단 거리 찾기
이전 글: [06-06] 분기 한정
다음 글: [06-08] 그래프 알고리즘
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자