기본 연산

import numpy as np

a = np.array([3, 4])
b = np.array([1, 2])

a + b          # [4, 6]     방향을 이어 붙임
a - b          # [2, 2]     b 에서 a 로 가는 방향
3 * a          # [9, 12]    크기만 3배 (방향 유지)

np.linalg.norm(a)      # 5.0   길이(노름) = √(3² + 4²)
a / np.linalg.norm(a)  # [0.6, 0.8]  단위벡터 — 방향만 남김

실무에서 벡터로 표현하는 것들

곱셈의 규칙과 의미

A = np.array([[1, 2],
              [3, 4]])
v = np.array([5, 6])

A @ v          # [17, 39]   ← 벡터를 변환
A @ A          # 변환을 두 번 적용한 것과 같은 하나의 변환

# 결과의 [i][j] = A 의 i 행과 B 의 j 열의 내적
# "i 번째 출력은 입력 전체에 가중치를 곱해 더한 것"

A.T            # 전치 — 행과 열을 바꿈
np.eye(2)      # 항등행렬 — 곱해도 그대로 (숫자의 1 에 해당)

연산량 — 왜 GPU 가 필요한가

import time
n = 1000
A = np.random.rand(n, n); B = np.random.rand(n, n)

t = time.perf_counter()
C = A @ B                       # numpy → BLAS(멀티스레드 + SIMD)
print(time.perf_counter() - t)  # 약 0.03초

# 같은 것을 순수 파이썬 3중 반복문으로 하면 수 분.
# 차이는 알고리즘이 아니라 '어디서 도느냐'다.
#   · numpy: C 로 짜인 BLAS + CPU 벡터 명령 + 캐시 최적화
#   · GPU  : 수천 코어가 동시에

2D 변환 행렬

import numpy as np

def rotate(deg):
    t = np.radians(deg)
    return np.array([[np.cos(t), -np.sin(t)],
                     [np.sin(t),  np.cos(t)]])

scale = np.array([[2, 0],
                  [0, 3]])          # x 2배, y 3배

shear = np.array([[1, 0.5],
                  [0, 1  ]])        # 기울이기

# 합성 — 오른쪽부터 적용된다
M = rotate(30) @ scale              # 확대한 뒤 회전
p = np.array([1, 0])
M @ p

동차 좌표 — 이동까지 행렬로

# 이동(translation)은 선형변환이 아니다 — 원점이 안 움직여야 하므로.
# 그래서 차원을 하나 늘려 3×3 으로 만든다 (2D 그래픽스의 표준)

def translate(dx, dy):
    return np.array([[1, 0, dx],
                     [0, 1, dy],
                     [0, 0, 1 ]])

p = np.array([1, 2, 1])            # 마지막 1 이 '점'이라는 표시
translate(3, 4) @ p                # [4, 6, 1]

# 이래서 CSS transform · WebGL · OpenGL 이 전부 4×4 행렬을 쓴다.
# 회전·확대·이동·원근을 '곱셈 하나'로 합칠 수 있기 때문.

행렬식이 뜻하는 것

np.linalg.det([[2, 0], [0, 3]])    # 6.0   면적 6배
np.linalg.det([[1, 2], [2, 4]])    # 0.0   2행이 1행의 2배 → 직선으로 눌림
np.linalg.det([[0,-1], [1, 0]])    # 1.0   회전 — 면적 그대로

# det < 0 이면 뒤집힘(거울상)이 포함된 것

연립방정식 풀기

# 2x + y = 5
#  x + 3y = 10
A = np.array([[2, 1],
              [1, 3]])
b = np.array([5, 10])

x = np.linalg.solve(A, b)      # [1., 3.]   ★ 이걸 쓴다
x = np.linalg.inv(A) @ b       # 같은 답이지만 느리고 부정확 ✗

# 왜 solve 가 나은가
#  · inv 는 내부적으로 더 많은 연산 → 오차가 더 쌓인다
#  · solve 는 LU 분해로 바로 푼다 (약 3배 빠름)

정의는 한 줄

A = np.array([[2, 1],
              [1, 2]])
vals, vecs = np.linalg.eig(A)
# vals: [3., 1.]
# vecs: 열이 고유벡터 — [0.707, 0.707], [-0.707, 0.707]

# 확인
v = vecs[:, 0]
A @ v            # [2.12, 2.12]
3 * v            # [2.12, 2.12]   ← 같다 ✓

PageRank — 가장 유명한 응용

# "중요한 페이지가 링크한 페이지가 중요하다"
# → 이 순환 정의를 고유벡터로 푼다

def pagerank(M, d=0.85, iters=100):
    n = M.shape[0]
    r = np.ones(n) / n
    for _ in range(iters):
        r = (1 - d) / n + d * (M @ r)     # 계속 곱하면 수렴
    return r

# M[i][j] = j 가 i 를 링크할 확률
# 반복해서 곱하면 '가장 큰 고윳값의 고유벡터'로 수렴한다 (거듭제곱법)
# d = 감쇠 계수 — 링크가 없는 페이지에서 무작위 점프

임의의 벡터를 고유벡터로 분해해 보면

수렴 속도를 정하는 것은 λ₂/λ₁ 입니다 — 이 비율을 스펙트럴 갭이라 부릅니다. 두 고윳값이 비슷하면(갭이 작으면) 수렴이 아주 느려집니다. PageRank 가 “50번 반복하면 충분”한 이유도, 어떤 그래프에서 수렴이 안 되는 이유도 전부 이 값입니다.

import numpy as np

def power_iteration(A, iters=100, tol=1e-10):
    x = np.random.rand(A.shape[0])
    x /= np.linalg.norm(x)
    for k in range(iters):
        y = A @ x
        y /= np.linalg.norm(y)          # ★ 정규화 안 하면 발산·언더플로
        if np.linalg.norm(y - x) < tol:
            return y, k                  # 수렴한 반복 횟수도 함께
        x = y
    return x, iters

A = np.array([[2., 1.], [1., 3.]])
v, k = power_iteration(A)
lam = v @ A @ v                          # 레일리 몫 — 고윳값 추정
print(f"λ₁≈{lam:.4f}  v₁≈{v.round(4)}  반복={k}")
print("정답:", np.linalg.eigvalsh(A))    # [1.382, 3.618]

같은 계산이 쓰이는 곳

# PCA 를 직접 — 고윳값이 "설명하는 분산"입니다
X = np.random.randn(200, 5) @ np.random.randn(5, 5)   # 상관있는 데이터
Xc = X - X.mean(axis=0)                                # ★ 중심화 필수
C  = (Xc.T @ Xc) / (len(Xc) - 1)                       # 공분산 행렬

lam, V = np.linalg.eigh(C)          # 대칭행렬 → eigh (실수 고윳값 보장)
order = lam.argsort()[::-1]         # 큰 순서로
lam, V = lam[order], V[:, order]

ratio = lam / lam.sum()
print("설명 분산 비율:", ratio.round(3))
print("누적:", ratio.cumsum().round(3))
# [0.62 0.25 0.09 0.03 0.01] → 앞 2개로 87% 설명
Z = Xc @ V[:, :2]                   # 2차원으로 축소

내적 — 곱해서 더하기

a = np.array([1, 2, 3])
b = np.array([4, 5, 6])

a @ b                # 32 = 1*4 + 2*5 + 3*6
np.dot(a, b)         # 같은 것

# 직각 확인
np.array([1,0]) @ np.array([0,1])    # 0 ← 완전히 무관

코사인 유사도 — 길이를 빼고 방향만

def cosine(a, b):
    return (a @ b) / (np.linalg.norm(a) * np.linalg.norm(b))

#  1.0 : 완전히 같은 방향
#  0.0 : 무관
# -1.0 : 정반대

# ★ 미리 정규화해 두면 내적 = 코사인 유사도
A = A / np.linalg.norm(A, axis=1, keepdims=True)
sims = A @ q                      # 10만 개와 한 번에 비교

top = np.argpartition(-sims, 10)[:10]     # 상위 10개 (정렬보다 빠름)
top = top[np.argsort(-sims[top])]

세 가지 척도의 관계

import numpy as np

def cosine(a, b):
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b) + 1e-12))

# ★ 미리 정규화해 두면 내적 한 번이 곧 코사인입니다 (검색 엔진의 표준 수법)
def normalize(M):
    return M / (np.linalg.norm(M, axis=1, keepdims=True) + 1e-12)

docs = normalize(np.random.randn(100_000, 768).astype("float32"))
q    = normalize(np.random.randn(1, 768).astype("float32"))

scores = docs @ q.T                       # (100000, 1) — 행렬곱 한 번
top10  = np.argpartition(-scores.ravel(), 10)[:10]   # 전체 정렬 없이 상위 10
top10  = top10[np.argsort(-scores.ravel()[top10])]
# argsort 로 전부 정렬하면 O(n log n), argpartition 은 O(n)

고차원에서 벌어지는 일 — 차원의 저주

# 차원이 높아지면 "가장 가까운 것"과 "가장 먼 것"의 차이가 사라집니다
import numpy as np

for d in (2, 10, 100, 1000):
    X = np.random.randn(1000, d)
    q = np.random.randn(d)
    dist = np.linalg.norm(X - q, axis=1)
    print(f"d={d:5d}  최소={dist.min():7.2f}  최대={dist.max():7.2f}  "
          f"(최대-최소)/최소={(dist.max()-dist.min())/dist.min():.3f}")

# d=    2  최소=   0.05  최대=   4.71  비율=90.9
# d=   10  최소=   1.44  최대=   7.12  비율= 3.9
# d=  100  최소=  10.6   최대=  17.3   비율= 0.63
# d= 1000  최소=  39.5   최대=  49.8   비율= 0.26  ← 거의 다 비슷한 거리

기본 규칙

# 서버 3대가 각각 99% 가동, 서로 독립일 때
# 전부 죽을 확률
(0.01) ** 3        # 0.000001  → 99.9999% 가용

# ★ 하지만 같은 랙 · 같은 전원 · 같은 AZ 라면 독립이 아니다.
#   "독립 가정"이 틀리면 이 계산은 전부 무의미하다.

몬티 홀 — 조건부확률의 고전

import random
def monty(switch, n=100_000):
    win = 0
    for _ in range(n):
        car = random.randrange(3)
        pick = random.randrange(3)
        # 사회자는 자동차도 내 선택도 아닌 문을 연다
        opened = next(d for d in range(3) if d != car and d != pick)
        if switch:
            pick = next(d for d in range(3) if d != pick and d != opened)
        win += (pick == car)
    return win / n

monty(False)   # 0.333
monty(True)    # 0.667   ← 바꾸는 게 두 배 유리

로그 샘플링 — 편향 없이 줄이기

# ✗ 나쁜 샘플링 — 앞의 1000개만
logs[:1000]                       # 시간 편향

# ✓ 균등 샘플링
if random.random() < 0.01:        # 1%
    emit(log)

# ✓ 결정적 샘플링 — 같은 트레이스는 전부 남거나 전부 버림
if zlib.crc32(trace_id.encode()) % 100 == 0:   # ★ 내장 hash() 는 프로세스마다 값이 달라 쓰면 안 된다
    emit(log)                     # 분산 추적에 필수

# ✓ 꼬리 우선 샘플링 — 느린 것은 무조건 남긴다
if duration > p99 or status >= 500 or random.random() < 0.01:
    emit(log)

확률적 조기 만료 — 캐시 스탬피드 방지

import math, random, time

def should_refresh(expiry, delta, beta=1.0):
    """만료 직전에 확률적으로 미리 갱신한다.
       모든 요청이 동시에 만료를 보고 DB 로 몰리는 것을 막는다."""
    now = time.time()
    return now - delta * beta * math.log(random.random()) >= expiry

# delta = 값을 다시 계산하는 데 걸린 시간
# 캐시가 비싸게 만들어진 값일수록 더 일찍 갱신을 시작한다

if should_refresh(item.expiry, item.build_time):
    refresh_async(key)          # 한 요청만 갱신, 나머지는 옛 값 사용

공식과 이름

# 실제 침입이 0.1% 인 환경에서
# 탐지율 99%, 오탐률 1% 인 시스템이 경보를 울렸다.
# 진짜 침입일 확률은?

p_attack = 0.001
p_alert_given_attack = 0.99
p_alert_given_normal = 0.01

p_alert = (p_alert_given_attack * p_attack +
           p_alert_given_normal * (1 - p_attack))

posterior = p_alert_given_attack * p_attack / p_alert
print(posterior)      # 0.090  ← 겨우 9%!

그러면 어떻게 하나

# 증거가 여러 개면 곱해서 갱신한다 (독립 가정 = 나이브 베이즈)
def update(prior, likelihood_ratios):
    odds = prior / (1 - prior)
    for lr in likelihood_ratios:
        odds *= lr                  # 우도비를 곱하기만 하면 된다
    return odds / (1 + odds)

update(0.001, [99, 50, 20])   # 세 신호가 겹치면 0.99

베이즈 정리 유도

증거가 여러 개면 우도비를 곱하기만 하면 됩니다 — 분모 P(B) 를 계산할 필요가 없어져 나이브 베이즈 분류기가 이 형태로 구현됩니다.

나이브 베이즈 — 스팸 필터를 직접

import math
from collections import Counter

class NaiveBayes:
    def fit(self, docs, labels):
        self.prior, self.wc, self.total = Counter(), {}, {}
        for d, y in zip(docs, labels):
            self.prior[y] += 1
            self.wc.setdefault(y, Counter()).update(d)
        self.vocab = {w for c in self.wc.values() for w in c}
        self.total = {y: sum(c.values()) for y, c in self.wc.items()}
        self.n = len(docs)
        return self

    def predict(self, doc):
        best, best_score = None, -math.inf
        for y in self.prior:
            # ★ 확률을 곱하면 언더플로 → 로그로 바꿔 더합니다
            score = math.log(self.prior[y] / self.n)
            for w in doc:
                if w not in self.vocab:      # 처음 보는 단어는 무시
                    continue
                # ★ 라플라스 평활 — 한 번도 안 나온 단어가 확률을 0 으로 만드는 것 방지
                p = (self.wc[y][w] + 1) / (self.total[y] + len(self.vocab))
                score += math.log(p)
            if score > best_score:
                best, best_score = y, score
        return best

nb = NaiveBayes().fit(
    [["무료","쿠폰","지금"], ["회의","자료","첨부"], ["당첨","클릭","무료"]],
    ["스팸", "정상", "스팸"])
print(nb.predict(["무료","클릭"]))    # 스팸

네 가지만 알면 됩니다

from scipy import stats

# 초당 평균 50건 요청 → 어떤 1초에 80건 이상 올 확률
1 - stats.poisson.cdf(79, 50)      # 0.0000567  약 0.006%

# 1초에 100건 이상은?  → 사실상 0
# 하지만 하루 86400초 동안이면?
1 - (stats.poisson.cdf(79, 50)) ** 86400   # 거의 1 — 반드시 일어난다

응답 시간의 진짜 모양

정규분포라면          실제 응답 시간
    ▁▃▅█▅▃▁              █▅▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ …
  평균 주변 대칭        대부분 빠르고, 꼬리가 아주 길다

이유
 · 캐시 히트/미스가 갈린다        (이봉 분포)
 · GC · 재시도 · 커넥션 재수립     (드물지만 큼)
 · 큐 대기는 부하에 지수적으로 증가

→ 평균은 거의 쓸모없다. p50 · p95 · p99 · max 를 본다.

정의와 성질

import numpy as np
x = np.array([10, 12, 11, 9, 200])     # 마지막이 이상치

x.mean()      # 48.4   ← 대표값으로 못 씀
np.median(x)  # 11.0   ← 이쪽이 현실
x.std()       # 75.8   ← 흩어짐이 크다는 신호

# 이상치에 강한 지표
np.percentile(x, [25, 50, 75])         # 사분위수
stats.median_abs_deviation(x)          # MAD

큰 수의 법칙과 중심극한정리

rng = np.random.default_rng(0)

# 지수분포(전혀 정규분포가 아님)에서 표본을 뽑아
# 표본평균의 분포를 보면 → 정규분포에 가까워진다
for n in (1, 5, 30, 100):
    means = rng.exponential(1.0, size=(20000, n)).mean(axis=1)
    print(n, round(means.std(), 3))

# 1     0.994
# 5     0.45    ≈ 1/√5
# 30    0.183   ≈ 1/√30
# 100   0.100   ≈ 1/√100

# ★ 표준오차 = σ / √n
#   정확도를 2배 올리려면 표본을 4배 모아야 한다

기본 흐름

1. 가설을 먼저 — “버튼 색이 전환율을 올린다”. 데이터를 본 뒤에 세우면 안 됩니다.
2. 표본 크기를 먼저 계산 — 필요한 관측 수를 정하고 시작합니다.
3. 정해진 기간을 채운다 — 중간에 멈추면 유의성이 부풀려집니다.
4. 결과 해석 — p값은 “효과 크기”가 아니라 “우연일 가능성”입니다.

from statsmodels.stats.power import zt_ind_solve_power
from statsmodels.stats.proportion import proportion_effectsize

# 전환율 5% → 5.5% 를 감지하려면 몇 명이 필요한가
es = proportion_effectsize(0.05, 0.055)
n = zt_ind_solve_power(effect_size=es, alpha=0.05, power=0.8)
print(round(n))       # 약 15,600 명 (각 그룹 · 합계 약 31,000)

p값이 말하지 않는 것

직접 확인

0.1 + 0.2               # 0.30000000000000004
0.1 + 0.2 == 0.3        # False

from decimal import Decimal
Decimal(0.1)
# Decimal('0.1000000000000000055511151231257827021181583404541015625')
# ← float 0.1 이 실제로 담고 있는 값

# 0.1 을 2진수로: 0.0001100110011001100... (무한 반복)
# 64비트에 잘라 넣으니 아주 조금 커진다

비교하는 올바른 방법

# ✗ 절대 하면 안 됨
if a == b: ...

# ✓ 절대·상대 오차를 함께
import math
math.isclose(0.1 + 0.2, 0.3)                    # True
math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-12)

# JS
Math.abs(a - b) < Number.EPSILON * Math.max(1, Math.abs(a), Math.abs(b))

# ✗ 반복 누적도 위험
total = 0.0
for _ in range(10):
    total += 0.1
total == 1.0        # False (0.9999999999999999)

NaN · Infinity · -0.0

import math
nan = float("nan")

nan == nan          # False!  ★ 자기 자신과도 다르다
math.isnan(nan)     # True    ← 이걸로 검사

[1, nan, 2].count(nan)   # 1  (is 비교라 걸림 — 혼란스러움)
sorted([3, nan, 1])      # [3, nan, 1]  정렬이 깨진다

float("inf") - float("inf")   # nan
0.0 == -0.0                   # True
math.copysign(1, -0.0)        # -1.0  ← 부호는 구분된다
1 / -0.0                      # -inf

언제 float 이 괜찮은가

자릿수 손실 (catastrophic cancellation)

# 비슷한 크기의 두 수를 빼면 유효 자릿수가 날아간다
a = 1.0000001
b = 1.0000000
a - b                 # 1.0000000005838672e-07  ← 유효숫자 8자리가 1자리로

# 실제 사고 예: 분산을 이렇게 계산하면 안 된다
def var_bad(xs):
    n = len(xs)
    return sum(x*x for x in xs)/n - (sum(xs)/n)**2   # E[X²] - E[X]²

xs = [1e9 + 0.1 * i for i in range(5)]   # 참값 분산 0.02
var_bad(xs)     # -128.0  ← 분산이 음수?! (아래 var_good 은 0.02)

# ✓ 웰포드 알고리즘 — 한 번 훑으면서 안정적으로
def var_good(xs):
    n = 0; mean = 0.0; m2 = 0.0
    for x in xs:
        n += 1
        d = x - mean
        mean += d / n
        m2 += d * (x - mean)
    return m2 / n

합산 순서와 카한 합

xs = [1.0] + [1e-16] * 10_000_000

sum(xs)                 # 1.0        작은 값들이 전부 사라짐 (3.12+ 의 sum 은 보정 합산이라 정확)
math.fsum(xs)           # 1.000000001   ✓ 정확 (1 + 10⁷ × 10⁻¹⁶)
np.sum(xs)              # pairwise 합산 — 꽤 정확

# 카한 합산 알고리즘 (직접 구현할 때)
def kahan_sum(xs):
    total = 0.0; c = 0.0        # c = 잃어버린 아랫자리
    for x in xs:
        y = x - c
        t = total + y
        c = (t - total) - y     # 방금 잃은 부분을 되찾는다
        total = t
    return total

# 정렬해서 더하는 것만으로도 좋아진다 (작은 것부터)
sum(sorted(xs))

수치 문제 진단

이 탭에서 이어지는 곳

정상 분포를 두 가지 방법으로

import numpy as np

# 행이 '현재 상태', 열이 '다음 상태' — 각 행의 합은 1
P = np.array([
    [0.0, 0.7, 0.3],   # 대기 → 처리중 0.7, 실패 0.3
    [0.5, 0.3, 0.2],   # 처리중 → 대기 0.5, 유지 0.3, 실패 0.2
    [0.6, 0.0, 0.4],   # 실패 → 대기 0.6, 유지 0.4
])

# ① 반복해서 곱하기 (직관적)
pi = np.array([1.0, 0.0, 0.0])       # 대기에서 출발
for k in range(1, 60):
    new = pi @ P
    if np.abs(new - pi).max() < 1e-12:
        print(f"{k}회에 수렴"); break
    pi = new
print("정상 분포:", pi.round(4))       # [0.3529 0.3529 0.2941]  (= 6/17, 6/17, 5/17)

# ② 고유벡터로 한 번에 (πP = π → P^T 의 고윳값 1 고유벡터)
w, v = np.linalg.eig(P.T)
pi2 = np.real(v[:, np.argmin(np.abs(w - 1))])
pi2 = pi2 / pi2.sum()
print("고유벡터로:", pi2.round(4))     # 같은 값

# 수렴 속도 — 두 번째로 큰 고윳값의 크기
lam = np.sort(np.abs(w))[::-1]
print(f"λ2 = {lam[1]:.3f} → 오차가 매 단계 이 비율로 줄어듭니다")

실무에서 이 계산이 나오는 곳

# 가용성을 마르코프로 계산 — SLA 협의에 쓰는 숫자
MTBF, MTTR = 720.0, 2.0        # 평균 무장애 720시간, 평균 복구 2시간

# 상태: 0 정상, 1 다운
P = np.array([
    [1 - 1/MTBF,  1/MTBF],
    [1/MTTR,      1 - 1/MTTR],
])
w, v = np.linalg.eig(P.T)
pi = np.real(v[:, np.argmin(np.abs(w - 1))]); pi /= pi.sum()

print(f"가용성 {pi[0]*100:.4f}%")               # 99.7230%
print(f"연간 다운타임 {pi[1]*365*24:.1f}시간")   # 24.3시간
# → 99.9% 를 맞추려면 MTTR 을 줄이는 편이 MTBF 를 늘리는 것보다 쉽습니다

공식과 직접 계산

import math
from collections import Counter

def entropy(data) -> float:
    n = len(data)
    return sum((c/n) * math.log2(n/c) for c in Counter(data).values())   # −Σp·log p 와 같음 (-0.0 방지)

print(entropy("aaaaaaaa"))          # 0.0    — 전부 같음
print(entropy("abababab"))          # 1.0    — 두 글자가 반반
print(entropy("abcdefgh"))          # 3.0    — 8가지 균등 = log2(8)
print(entropy(open("a.jpg","rb").read()))   # 7.9 근처 — 이미 압축됨

# 압축 하한 확인 — 이론값보다 작게는 못 줄입니다 (글자를 독립으로 뽑은 데이터일 때)
import random
data = bytes(random.choice(b"abcd") for _ in range(16_000))   # 글자당 2비트
lower = entropy(data) * len(data) / 8
print(f"이론 하한 {lower:.0f}B, 실제 gzip {len(__import__('gzip').compress(data))}B")
# 이론 하한 4000B, 실제 gzip 약 5000B
# ★ b"aaaabbbb..." * 1000 처럼 반복이 있으면 글자 빈도로 잰 이 하한보다 훨씬 작아진다
#   (gzip 은 글자 하나가 아니라 반복 패턴을 줄이므로)

비밀번호 강도를 비트로 말하기

랭크-k 근사 — 몇 개를 남길지 정하는 법

import numpy as np

A = np.random.default_rng(0).normal(size=(200, 80))

U, s, Vt = np.linalg.svd(A, full_matrices=False)
# U (200,80) · s (80,) 내림차순 · Vt (80,80)

k = 10
Ak = (U[:, :k] * s[:k]) @ Vt[:k]          # 랭크-k 근사

err = np.linalg.norm(A - Ak) / np.linalg.norm(A)
print(f"k={k} 상대 오차 {err:.3f}")

# k 를 감으로 고르지 않는 법 — 누적 설명력
ratio = np.cumsum(s**2) / np.sum(s**2)
print("90% 설명에 필요한 k:", int(np.searchsorted(ratio, 0.90)) + 1)

# 저장 용량 — 원본 m·n 대신 (m+n+1)·k 만 있으면 됩니다
m, n = A.shape
print(f"{(m + n + 1) * k} vs {m * n}")

# 조건수도 여기서 바로 나옵니다
print("조건수", s[0] / s[-1])

어디에서 이미 쓰고 있었나

용량 산정에 그대로 쓰는 최소제곱

import numpy as np

# 트래픽으로 CPU 사용률을 설명 — y ≈ a·x + b
x = np.array([120, 240, 310, 480, 610, 750], float)   # RPS
y = np.array([12.4, 23.9, 30.1, 47.7, 60.8, 74.2])    # CPU %

A = np.column_stack([x, np.ones_like(x)])   # 열이 [x, 1]

coef, res, rank, sv = np.linalg.lstsq(A, y, rcond=None)
a, b = coef
print(f"CPU% ≈ {a:.4f}·RPS + {b:.2f}")

# 이 값이 크면 결과를 믿기 어렵습니다 (lstsq 가 σ 를 그대로 줍니다)
print("조건수", sv.max() / sv.min())

# 증설 시점을 숫자로 — 80% 를 넘는 RPS
print(f"80% 도달 RPS ≈ {(80 - b) / a:.0f}")

# 잔차로 “이 직선이 믿을 만한가”를 확인
resid = y - A @ coef
print("최대 오차", np.abs(resid).max())

정규방정식을 직접 짜면 안 되는 이유

import numpy as np

# 악명 높은 반데르몬드 행렬 — 조건수가 큽니다
A = np.vander(np.linspace(0, 1, 30), 12)
b = np.ones(30)

print(f"cond(A)   = {np.linalg.cond(A):.2e}")
print(f"cond(AᵀA) = {np.linalg.cond(A.T @ A):.2e}")   # 제곱됩니다

x_ne = np.linalg.solve(A.T @ A, A.T @ b)      # 정규방정식 직접
x_ls = np.linalg.lstsq(A, b, rcond=None)[0]   # 내부적으로 SVD

print("정규방정식 잔차", np.linalg.norm(A @ x_ne - b))
print("lstsq   잔차", np.linalg.norm(A @ x_ls - b))
# → 정규방정식 쪽이 눈에 띄게 나쁩니다. 같은 수식인데 결과가 다릅니다.

구성 요소는 넷뿐

① 무한한 테이프   ... [ ][1][0][1][ ][ ] ...
② 읽기·쓰기 헤드           ↑
③ 유한한 상태 집합   q0, q1, q2, ...
④ 전이 규칙        (현재상태, 읽은값) → (쓸값, 이동방향, 다음상태)

이게 전부다. 그런데 이 기계로
파이썬으로 짤 수 있는 모든 프로그램을 짤 수 있다.

튜링 완전 — 모든 언어가 같은 힘

# 튜링 완전에 필요한 것: 조건 분기 + 무한 반복 + 무제한 저장
# 이 셋만 있으면 무엇이든 계산할 수 있다.

# 튜링 완전한 것들 (의외의 것 포함)
#  · 모든 범용 프로그래밍 언어
#  · 엑셀 수식 (2021년 LAMBDA 추가로)
#  · C++ 템플릿 · TypeScript 타입 시스템
#  · SQL (재귀 CTE 포함)
#  · 마인크래프트 레드스톤 · 콘웨이의 생명 게임
#  · 매직 더 개더링 (카드 게임)

# 튜링 완전하지 '않은' 것 — 그래서 안전한 것들
#  · 정규식 (POSIX 표준)
#  · JSON · YAML
#  · 종료가 보장된 DSL (Bitcoin Script · Cap'n Proto)

if 뭉치 대신 전이표

if order.status == "paid" and action == "ship":
    order.status = "shipping"
elif order.status == "pending" and action == "pay":
    order.status = "paid"
elif ...    # 상태가 늘 때마다 여기저기 추가

TRANSITIONS = {
    ("pending",  "pay"):    "paid",
    ("pending",  "cancel"): "canceled",
    ("paid",     "ship"):   "shipping",
    ("paid",     "cancel"): "canceled",
    ("shipping", "deliver"):"done",
}

def apply(status, action):
    key = (status, action)
    if key not in TRANSITIONS:
        raise ValueError(f"{status} 에서 {action} 불가")
    return TRANSITIONS[key]

DFA 와 NFA

정규식 = FSM

정규식      a(b|c)*d
            ↕ 완전히 동등
FSM         q0 --a--> q1 --d--> q2(수락)
                      ↺ b, c

정규 언어로 표현할 수 있는 것
  · 고정된 패턴          이메일 형태 · 날짜 형식
  · 반복                  a* · [0-9]+
  · 선택                  (cat|dog)

표현할 수 없는 것 ★
  · 괄호 짝 맞추기        ((()))
  · 중첩 태그             <div><div></div></div>
  · aⁿbⁿ (같은 개수)
  · 회문 (팰린드롬)

이유: '몇 개나 열렸는지' 세려면 무한한 상태가 필요하다.
      FSM 의 상태는 유한하다. 끝.

“현대 정규식”은 정규식이 아니다

import regex     # pip install regex — 재귀 지원

# PCRE 의 재귀 패턴 — 이론상 정규식이 아니다
pattern = r'\((?:[^()]|(?R))*\)'
regex.match(pattern, "((a)(b))")    # 매치됨 — 중첩을 센다

# 역참조도 정규 언어를 벗어난다
regex.match(r'(\w+) \1', "hello hello")   # 같은 단어 반복 (표준 re 도 지원)

# ★ 그래서 이름이 헷갈린다
#   이론의 '정규 표현식' ≠ 프로그래밍 언어의 '정규식'
#   후자는 훨씬 강하지만, 그 대가로 성능 보장을 잃는다

BNF 로 문법 적기

# 사칙연산 문법 (연산자 우선순위가 구조에 들어 있다)
expr   ::= expr '+' term
         | expr '-' term
         | term

term   ::= term '*' factor
         | term '/' factor
         | factor

factor ::= NUMBER
         | '(' expr ')'          ← 재귀! 중첩이 가능해진다

# "정규식과의 결정적 차이"가 이 재귀다.
# 규칙이 자기 자신을 부를 수 있으므로 무한한 중첩을 표현한다.

모호성 — 파스 트리가 둘 이상

# 모호한 문법
expr ::= expr '+' expr | NUMBER

# "1 + 2 + 3" 의 파스 트리가 두 가지
#    (1+2)+3        1+(2+3)
# 덧셈은 결과가 같지만 뺄셈이면 달라진다!

# 유명한 모호성: dangling else
if (a) if (b) x(); else y();
#  else 는 어느 if 의 것인가?
#  → 대부분의 언어가 "가장 가까운 if" 로 정함 (규칙으로 해소)

# 해소 방법
#  ① 문법을 계층으로 다시 쓴다 (왼쪽 재귀 제거)
#  ② 파서 생성기에 우선순위·결합성을 따로 준다 (%left, %right)

각 계층이 못 하는 것

정규 언어가 못 함
  aⁿbⁿ         (여는 것과 닫는 것의 개수 맞추기)
  → 괄호 · 태그 중첩

문맥자유가 못 함
  aⁿbⁿcⁿ       (세 개를 동시에 맞추기)
  → "선언된 변수만 사용" · "인자 개수 일치"
  → 그래서 컴파일러는 파싱 뒤에 '의미 분석' 단계를 따로 둔다

문맥의존도 못 함
  정지 문제 (06 절)

실무에서의 의미

증명 — 자기 자신에게 물어보기

# 이런 함수가 있다고 가정하자
def halts(program, input) -> bool:
    """program(input) 이 언젠가 끝나면 True"""
    ...   # 존재한다고 가정

# 그러면 이걸 만들 수 있다
def paradox(program):
    if halts(program, program):
        while True: pass          # 끝난다고 하면 → 무한 루프
    else:
        return                    # 안 끝난다고 하면 → 끝냄

# 그리고 자기 자신을 넣는다
paradox(paradox)

#  · halts 가 True 라 하면 → paradox 는 무한 루프 → 모순
#  · halts 가 False 라 하면 → paradox 는 즉시 종료 → 모순
# 따라서 halts 는 존재할 수 없다. ∎

라이스 정리 — 더 나쁜 소식

결정 불가능한 질문들 (전부)
  · 이 함수가 항상 같은 값을 반환하는가
  · 이 코드에 도달 불가능한 부분이 있는가
  · 이 프로그램이 파일을 지우는가
  · 두 프로그램이 같은 일을 하는가
  · 이 변수가 null 이 될 수 있는가

★ "일반적으로는" 불가능하다는 뜻이다.
  특정한 프로그램에 대해서는 대개 답할 수 있다.

정의와 표기

빅오가 말하지 않는 것

# 이론상 O(1) 이 O(n) 보다 항상 빠르지 않다
d = {i: i for i in range(20)}       # 해시 — O(1)
lst = [(i, i) for i in range(20)]   # 리스트 순회 — O(n)

# n=20 정도면 리스트 선형 탐색이 더 빠른 경우가 많다
#  · 해시 계산 비용이 없다
#  · 연속 메모리 → 캐시에 통째로 들어간다
# 그래서 작은 맵을 배열로 구현하는 라이브러리가 많다

규칙 네 개

# ① 순차 실행 → 더한다 (큰 쪽만 남음)
f()   # O(n)
g()   # O(n²)
# → O(n + n²) = O(n²)

# ② 중첩 반복 → 곱한다
for i in range(n):        # n 번
    for j in range(n):    # × n 번
        work()            # × O(1)
# → O(n²)

# ③ 반으로 줄면 → log
while n > 1:
    n //= 2
# → O(log n)

# ④ 재귀 → 점화식 (🔢 이산수학 12 마스터 정리)
def f(n):
    if n <= 1: return
    f(n // 2); f(n // 2)
    for _ in range(n): work()
# T(n) = 2T(n/2) + n → O(n log n)

헷갈리는 형태들

# 안쪽이 i 까지만 도는 경우
for i in range(n):
    for j in range(i):      # 0+1+2+...+(n-1) = n(n-1)/2
        work()
# → O(n²)  (절반이어도 n² 이다)

# 안쪽이 고정 횟수
for i in range(n):
    for j in range(100):    # 상수
        work()
# → O(n)

# 두 개의 서로 다른 입력
for a in A:                 # len(A) = n
    for b in B:             # len(B) = m
        work()
# → O(n·m)   ★ O(n²) 이라고 쓰면 틀림

# 반복마다 크기가 반씩 주는 작업
i = n
while i > 0:
    for j in range(i): work()     # n + n/2 + n/4 + ... = 2n
    i //= 2
# → O(n)  (합이 등비급수라 2n 으로 수렴)

무엇을 세는가

# 보통 '추가로 쓰는' 메모리만 센다 (입력 제외)

def sum_all(arr):          # O(1) 공간
    t = 0
    for x in arr: t += x
    return t

def doubled(arr):          # O(n) 공간
    return [x * 2 for x in arr]

def fib_memo(n, memo={}):  # O(n) 공간
    ...

def merge_sort(a):         # O(n) 공간 (병합용 버퍼)
    ...

def quick_sort(a):         # O(log n) 공간 (재귀 스택)
    ...

# ★ 재귀 스택도 공간이다. 깊이 n 재귀는 O(n) 공간.

트레이드오프의 실제 사례

동적 배열이 두 배씩 늘리는 이유

용량이 꽉 차면 2배로 늘리고 전부 복사한다

append 1~4    : 각 O(1)
append 5      : 복사 4개  → O(n)
append 6~8    : 각 O(1)
append 9      : 복사 8개  → O(n)
...

n 번 append 하는 동안의 총 복사 횟수
  1 + 2 + 4 + 8 + ... + n/2 + n  <  2n

→ 총 비용 O(n) / n 번 = 평균 O(1)   ★ 상환 O(1)

★ 만약 '한 칸씩' 늘린다면?
  1 + 2 + 3 + ... + n = n²/2  → 평균 O(n)  ← 훨씬 나쁘다

세 가지 분석 방법

회계법으로 본 append
  · append 한 번에 3 코인을 청구한다
    ① 1 코인: 실제 삽입
    ② 1 코인: 나중에 자기를 복사할 때 쓸 저금
    ③ 1 코인: 이미 복사된 앞쪽 원소를 위한 저금
  · 확장이 일어날 때 저금이 항상 충분하다
  → 연산당 상수(3) → 상환 O(1) ∎

정의

스도쿠로 이해하기
  · 완성된 스도쿠가 맞는지 확인 → 몇 초 (NP)
  · 빈 스도쿠를 푸는 것         → 크기가 커지면 폭발

P = NP 인가?
  = "확인이 쉬우면 찾는 것도 쉬운가?"
  = 밀레니엄 문제 (상금 100만 달러)
  = 대부분의 학자는 P ≠ NP 라고 믿는다

현실 문제 중 NP-완전인 것들

정의를 정확히

실무에서 만나면 이렇게 합니다

NP-완전임을 알아챘다면 — 선택지는 넷입니다

① 입력 크기를 제한한다
   n ≤ 20 이면 2^20 = 100만, 완전 탐색이 그냥 됩니다
   "실무 데이터가 정말 큰가"를 먼저 확인하세요

② 근사 알고리즘
   최적의 몇 % 이내를 보장하며 빠르게
   예: TSP 의 크리스토피데스 — 최적의 1.5배 이내 보장

③ 휴리스틱
   보장은 없지만 대개 잘 되는 방법
   담금질 · 유전 알고리즘 · 지역 탐색

④ 솔버에 맡긴다  ← 실무에서 가장 현실적
   SAT 솔버 · MILP 솔버(OR-Tools, CBC, Gurobi)
   수십 년간 최적화된 도구가 대부분의 실제 인스턴스를 풉니다

① 근사 알고리즘

“최적의 k 배 이내”를 증명할 수 있는 방법.

· 정점 커버 → 2배 이내
· TSP(삼각부등식) → 1.5배
· 집합 커버 → ln n 배
· 빈 채우기 → 1.7배

품질 보장이 필요하면
이쪽을 쓴다

② 휴리스틱 · 메타휴리스틱

보장은 없지만 실제 데이터에서 잘 됨.

· 탐욕 + 지역 탐색
· 시뮬레이티드 어닐링
· 유전 알고리즘
· 타부 서치
· 개미 군집

구현이 쉽고
튜닝 여지가 크다

③ 솔버에 맡기기 권장

문제를 표준 형태로 기술만 하고 나머지는 맡김.

· MILP: CBC · HiGHS · Gurobi
· CP-SAT: OR-Tools
· SAT: MiniSat · CaDiCaL
· SMT: Z3

수십 년 누적된 최적화가
들어 있다

이론상의 표

현실의 측정

import time
from collections import deque

N = 1_000_000
arr = list(range(N))
lst = deque(range(N))          # 파이썬에는 진짜 연결 리스트가 없음

# 순회 — 이론상 둘 다 O(n)
t = time.perf_counter(); s = sum(arr); a = time.perf_counter() - t
t = time.perf_counter(); s = sum(lst); d = time.perf_counter() - t
print(round(d / a, 2), "배")     # deque 가 2~3배 느림

# C++ 로 재면 차이가 더 크다
#   std::vector 순회   :  1.0x
#   std::list 순회     :  5~15x  (노드가 흩어질수록 나빠짐)
#   중간 삽입 10만 번   : vector 가 여전히 더 빠른 경우가 많다

용량과 길이는 다릅니다

import sys
a = []
prev = 0
for i in range(20):
    a.append(i)
    size = sys.getsizeof(a)
    if size != prev:
        print(f"길이 {len(a):2d} → {size} 바이트  ★ 재할당")
        prev = size

# 길이  1 → 88   ★
# 길이  5 → 120  ★
# 길이  9 → 184  ★
# 길이 17 → 248  ★
# 파이썬의 성장 비율은 약 1.125배 + 상수 (구현마다 다름)

미리 확보하면 사라집니다

# 파이썬 — 크기를 아는 경우
result = [None] * n
for i in range(n):
    result[i] = f(i)

# 또는 리스트 컴프리헨션 (내부에서 크기 힌트를 씀)
result = [f(i) for i in range(n)]

// C++
std::vector<int> v;
v.reserve(n);           // ★ 재할당 0번
for (int i = 0; i < n; ++i) v.push_back(f(i));

// Go
s := make([]int, 0, n)  // 길이 0, 용량 n

// Java
var list = new ArrayList<Integer>(n);

// Rust
let mut v = Vec::with_capacity(n);

스택 (LIFO)

s = []
s.append(x)     # push  O(1)
s.pop()         # pop   O(1)
s[-1]           # peek

# 쓰이는 곳
#  · 함수 호출 스택
#  · 되돌리기(undo)
#  · 괄호 · 태그 짝 검사
#  · DFS 반복 구현
#  · 수식 계산 (후위 표기)
#  · 브라우저 뒤로 가기

큐 (FIFO)

from collections import deque
q = deque()
q.append(x)      # enqueue O(1)
q.popleft()      # dequeue O(1)

# ✗ list.pop(0) 은 O(n)

# 쓰이는 곳
#  · 작업 대기열
#  · BFS
#  · 요청 버퍼
#  · 프로듀서-컨슈머
#  · 프린터 스풀

덱 (양쪽)

d = deque()
d.append(x); d.appendleft(x)
d.pop();     d.popleft()
# 전부 O(1)

# 쓰이는 곳
#  · 슬라이딩 윈도우 최댓값
#  · 최근 N개 유지 (maxlen)
#  · 양방향 탐색
#  · 작업 훔치기 스케줄러

스택 실전 — 괄호 · 태그 짝 검사

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack = []
    for i, ch in enumerate(s):
        if ch in "([{":
            stack.append((ch, i))
        elif ch in PAIRS:
            if not stack or stack[-1][0] != PAIRS[ch]:
                return f"{i}번째 '{ch}' 가 짝이 안 맞음"
            stack.pop()
    if stack:
        ch, i = stack[-1]
        return f"{i}번째 '{ch}' 가 닫히지 않음"
    return None

balanced("a(b[c]{d})e")     # None
balanced("a(b[c)d]")        # "5번째 ')' 가 짝이 안 맞음"

덱 실전 — 슬라이딩 윈도우 최댓값

from collections import deque

def window_max(nums, k):
    """모든 크기 k 윈도우의 최댓값을 O(n) 에 구한다"""
    dq = deque()          # 값이 감소하는 인덱스만 유지
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                  # 나보다 작은 것은 영원히 쓸모없다
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()              # 윈도우 밖으로 나감
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

window_max([1,3,-1,-3,5,3,6,7], 3)    # [3,3,5,5,6,7]

# 단순하게 하면 O(n·k) — 이 기법으로 O(n)

기본 구조

key ──hash()──▶ 정수 ──% 버킷수──▶ 인덱스 ──▶ 저장 위치

buckets = [ _ , _ , [("b",2)] , _ , [("a",1),("c",3)] , _ , _ , _ ]
                                          ↑ 충돌 (같은 버킷)

핵심 세 가지
 ① 해시 함수가 고르게 퍼뜨려야 한다
 ② 충돌을 어떻게 처리할 것인가
 ③ 얼마나 차면 늘릴 것인가 (로드 팩터)

class SimpleHashMap:
    def __init__(self, cap=8):
        self.buckets = [[] for _ in range(cap)]
        self.n = 0

    def _idx(self, k): return hash(k) % len(self.buckets)

    def put(self, k, v):
        b = self.buckets[self._idx(k)]
        for i, (kk, _) in enumerate(b):
            if kk == k: b[i] = (k, v); return       # 갱신
        b.append((k, v)); self.n += 1
        if self.n / len(self.buckets) > 0.75:       # ★ 로드 팩터
            self._resize()

    def _resize(self):
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        self.n = 0
        for b in old:
            for k, v in b: self.put(k, v)           # 전부 재배치 — O(n)

충돌 처리 두 방식

좋은 해시 함수의 조건

# FNV-1a — 이해하기 쉬운 예 (실무에는 더 좋은 것이 있음)
def fnv1a(data: bytes) -> int:
    h = 0xcbf29ce484222325
    for b in data:
        h ^= b
        h = (h * 0x100000001b3) & 0xFFFFFFFFFFFFFFFF
    return h

# 곱셈이 비트를 섞고, XOR 이 새 정보를 넣는다.
# 이 두 연산의 반복이 대부분의 비암호 해시의 뼈대다.

용도별로 골라 쓰기

일관 해싱 — 노드가 바뀌어도 덜 움직인다

import bisect, hashlib

class ConsistentHash:
    def __init__(self, nodes, vnodes=150):
        self.ring = []          # (해시, 노드) 정렬 리스트
        self.vnodes = vnodes
        for n in nodes: self.add(n)

    def _h(self, s):
        return int(hashlib.blake2b(s.encode(), digest_size=8).hexdigest(), 16)

    def add(self, node):
        for i in range(self.vnodes):          # ★ 가상 노드로 고르게
            bisect.insort(self.ring, (self._h(f"{node}#{i}"), node))

    def get(self, key):
        h = self._h(key)
        i = bisect.bisect(self.ring, (h,)) % len(self.ring)
        return self.ring[i][1]

# 노드 하나를 추가해도 이동하는 키는 약 1/N 뿐
# (단순 % N 이면 거의 전부 이동 — 🔢 이산수학 10)

SimHash — 비슷하면 비슷한 해시

def simhash(tokens, bits=64):
    v = [0] * bits
    for t in tokens:
        h = int(hashlib.blake2b(t.encode(), digest_size=8).hexdigest(), 16)
        for i in range(bits):
            v[i] += 1 if (h >> i) & 1 else -1
    out = 0
    for i, x in enumerate(v):
        if x > 0: out |= 1 << i
    return out

def hamming(a, b): return bin(a ^ b).count("1")

# 거의 같은 문서면 해밍 거리가 3 이하
# → 중복 뉴스 · 표절 · 스팸 클러스터링에 쓴다

# ★ 일반 해시와 정반대 성질이다.
#   보통 해시는 1비트만 달라도 완전히 달라져야 하고(눈사태),
#   유사도 해시는 비슷한 입력이 비슷한 출력이어야 한다.

구조와 기본 연산

class Node:
    __slots__ = ("key", "val", "left", "right")
    def __init__(self, k, v):
        self.key, self.val = k, v
        self.left = self.right = None

def insert(node, k, v):
    if node is None: return Node(k, v)
    if k < node.key:   node.left  = insert(node.left, k, v)
    elif k > node.key: node.right = insert(node.right, k, v)
    else:              node.val = v
    return node

def search(node, k):
    while node:
        if k == node.key: return node.val
        node = node.left if k < node.key else node.right
    return None

def inorder(node):                  # ★ 중위 순회 = 정렬된 순서
    if node:
        yield from inorder(node.left)
        yield node.key, node.val
        yield from inorder(node.right)

해시가 못 하는 것들

회전 — 균형 유지의 기본 연산

오른쪽 회전 (왼쪽이 무거울 때)

      y                    x
     / \                  / \
    x   C     ──▶        A   y
   / \                      / \
  A   B                    B   C

★ 중위 순회 순서는 변하지 않는다 (A x B y C)
  = BST 성질이 유지된다
  = 순서를 지키면서 높이만 줄인다

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update_height(y); update_height(x)     # 순서 중요
    return x                                # 새 루트

AVL vs 레드블랙

왜 이진 트리가 아닌가

1억 건 인덱스

이진 트리         : 높이 log₂(1억) ≈ 27
                   → 디스크 접근 27번 × 0.1ms = 2.7ms

B+트리 (팬아웃 500) : 높이 log₅₀₀(1억) ≈ 3
                   → 디스크 접근 3번 × 0.1ms = 0.3ms

★ 핵심: 한 번 읽을 때 '많이' 읽는다
  · 노드 하나 = 페이지 하나 (8KB · 16KB)
  · 키가 16바이트면 한 노드에 500개
  · 높이가 3~4 면 10억 건도 커버

B-트리 vs B+트리

B+트리 구조

내부:      [ 30 | 70 ]
          /     |     \
리프: [10,20]→[30,50]→[70,90]
       ↑___양방향 링크___↑

WHERE age BETWEEN 25 AND 75
 → 25 를 찾아 리프로 내려간 뒤
   링크를 따라 순차 스캔 (트리를 다시 안 탄다)

배열로 표현하는 완전 이진 트리

       1
      / \          배열: [1, 3, 2, 7, 5, 4]
     3   2          인덱스  0  1  2  3  4  5
    / \ /
   7  5 4         자식:  2i+1, 2i+2
                  부모:  (i-1)//2

★ 포인터가 필요 없다 — 연속 메모리 → 캐시 친화적
★ 최소 힙 성질: 부모 ≤ 자식 (전체 정렬은 아님)

import heapq

h = []
heapq.heappush(h, 5)          # O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h)              # 1  — O(log n)
h[0]                          # 최솟값 확인 — O(1)

heapq.heapify(arr)            # 리스트를 힙으로 — O(n) ★ n log n 아님
heapq.nlargest(10, data)      # Top-10
heapq.nsmallest(10, data)

heapify 가 O(n) 인 이유

아래에서 위로 내려보내기(sift-down)를 하면

레벨      노드 수    각 노드의 최대 이동
────────────────────────────────────
맨 아래   n/2        0    (리프는 안 움직임)
그 위     n/4        1
그 위     n/8        2
...
루트      1          log n

총합 = Σ (n/2^(k+1)) × k  =  n × Σ k/2^(k+1)  ≈  n

★ 위에서 아래로(sift-up) 하면 O(n log n) 이 된다.
  방향이 복잡도를 바꾼다.

구조와 구현

단어: cat, car, card, dog

      (root)
      /    \
     c      d
     |      |
     a      o
    / \     |
   t   r    g*
   *   |
       d*      (* = 단어 끝)

★ 공통 접두사를 한 번만 저장한다

class Trie:
    def __init__(self):
        self.root = {}
        self.END = "$"

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node[self.END] = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and self.END in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node: return None
            node = node[ch]
        return node

    def complete(self, prefix, limit=10):
        node = self._walk(prefix)
        if node is None: return []
        out = []
        def dfs(n, acc):
            if len(out) >= limit: return
            if self.END in n: out.append(prefix + acc)
            for ch, child in n.items():
                if ch != self.END: dfs(child, acc + ch)
        dfs(node, "")
        return out

해시맵과 비교

전체 구현이 15줄

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n                 # 그룹 개수

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # ★ 경로 압축
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False                          # 이미 같은 그룹
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra  # ★ 랭크로 합치기
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count -= 1
        return True

    def same(self, a, b): return self.find(a) == self.find(b)

두 가지 최적화가 만드는 차이

경로 압축이 하는 일

find(7) 호출 전       find(7) 호출 후
    1                     1
    |                   / | \
    3                  3  5  7   ← 전부 루트에 직접 연결
    |
    5
    |
    7

블룸 필터 — “없다”만 확실히

비트 배열 + 해시 함수 k 개

넣기:  x → h1(x), h2(x), h3(x) 위치의 비트를 1로
묻기:  세 위치가 전부 1이면 "있을 수도"
       하나라도 0이면 "확실히 없다"

[0,1,0,1,1,0,0,1,0,1,0,0]
     ↑   ↑ ↑

★ 위양성(있다고 잘못 말함)은 있고
  위음성(없다고 잘못 말함)은 절대 없다

import math, hashlib

class BloomFilter:
    def __init__(self, n, fp_rate=0.01):
        self.m = math.ceil(-n * math.log(fp_rate) / (math.log(2) ** 2))
        self.k = max(1, round(self.m / n * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _idx(self, item, i):
        h = hashlib.blake2b(f"{i}:{item}".encode(), digest_size=8).digest()
        return int.from_bytes(h, "big") % self.m

    def add(self, item):
        for i in range(self.k):
            p = self._idx(item, i)
            self.bits[p // 8] |= 1 << (p % 8)

    def __contains__(self, item):
        return all(self.bits[(p := self._idx(item, i)) // 8] & (1 << (p % 8))
                   for i in range(self.k))

bf = BloomFilter(1_000_000, 0.01)
# 100만 개 · 오탐 1% → 약 1.2MB (set 이면 약 80MB)

쓰이는 곳