수열과 급수: 반복문의 수학

# 첫째 항 a, 공차 d
# n번째 항: a_n = a + (n-1) * d

def arithmetic_sequence(a, d, n):
    """등차수열의 n번째 항까지 반환"""
    return [a + i * d for i in range(n)]


print(arithmetic_sequence(2, 3, 10))
# [2, 5, 8, 11, 14, 17, 20, 23, 26, 29]


# 합 (등차수열 합 공식)
# S_n = n(a + a_n) / 2 = n(2a + (n-1)d) / 2
def arithmetic_sum(a, d, n):
    a_n = a + (n - 1) * d
    return n * (a + a_n) // 2


print(arithmetic_sum(2, 3, 10))
# 155 (위 리스트의 합과 동일)


# 검증 — for 루프 결과와 비교
total = 0
for i in range(10):
    total += 2 + i * 3
print(total)  # 155

# 첫째 항 a, 공비 r
# n번째 항: a_n = a * r^(n-1)

def geometric_sequence(a, r, n):
    return [a * (r ** i) for i in range(n)]


print(geometric_sequence(1000, 1.05, 5))
# 원금 1000, 연 5% 복리 5년
# [1000.0, 1050.0, 1102.5, 1157.625, 1215.51]


# 복리 계산 — 투자 원금 + 이자
def compound_interest(principal, rate, years, n_per_year=1):
    """
    principal: 원금
    rate: 연 이자율 (0.05 = 5%)
    years: 기간
    n_per_year: 연 복리 횟수 (12=월복리, 365=일복리)
    """
    return principal * (1 + rate / n_per_year) ** (n_per_year * years)


# 1000만원 투자, 연 7%, 10년
print(compound_interest(10_000_000, 0.07, 10))
# 19,671,513원 (97% 증가)


# 월복리는 더 유리
print(compound_interest(10_000_000, 0.07, 10, n_per_year=12))
# 20,096,613원

from functools import reduce

# 수학: Σ_{i=1}^{n} i = n(n+1)/2
# 코드: reduce 또는 sum

n = 100

# 방법 1: 공식
formula = n * (n + 1) // 2
print(formula)  # 5050

# 방법 2: 시그마 = reduce
sigma = reduce(lambda acc, x: acc + x, range(1, n+1), 0)
print(sigma)  # 5050

# 방법 3: 빌트인 sum
print(sum(range(1, n+1)))  # 5050


# 시그마는 단순 덧셈이 아닌 일반 누적 — reduce가 정확한 대응
# Σ_{i=1}^{n} f(i) ≡ reduce((acc, x) => acc + f(x), arr, 0)


# 예: 제곱의 합 Σi²
sum_of_squares = sum(i**2 for i in range(1, n+1))
print(sum_of_squares)  # 338350


# 공식: n(n+1)(2n+1)/6
formula = n * (n + 1) * (2 * n + 1) // 6
print(formula)  # 338350

# 정의: f(n) = f(n-1) + f(n-2), f(1) = f(2) = 1
# Naive: O(2^n) — 중복 계산 폭주
def fib_naive(n):
    if n <= 2:
        return 1
    return fib_naive(n-1) + fib_naive(n-2)


# 메모이제이션: O(n)
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 2:
        return 1
    cache[n] = fib_memo(n-1) + fib_memo(n-2)
    return cache[n]


# 반복문: O(n), 공간 O(1)
def fib_iter(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return a


import time
t0 = time.perf_counter()
print(fib_iter(50))  # 12586269025
print(f"{(time.perf_counter() - t0)*1000:.3f}ms")  # < 0.01ms

# fib_naive(50)은 약 15분+ 걸림 — 절대 시도하지 말 것


# 황금비 — 피보나치 비율의 극한
import math
golden_ratio = (1 + math.sqrt(5)) / 2  # ≈ 1.618
print(fib_iter(20) / fib_iter(19))     # ≈ 1.618

# 데이터 N개를 페이지당 P개씩 표시할 때 총 페이지 수
import math

def total_pages(n, per_page):
    return math.ceil(n / per_page)


# 이는 등차수열의 일반항과 관련
# 시작 인덱스: page_index * per_page
# 끝 인덱스: min((page_index+1) * per_page, n)

def paginate(items, page, per_page=10):
    start = (page - 1) * per_page
    end = start + per_page
    return items[start:end]


items = list(range(1, 101))
print(paginate(items, 1))   # [1, 2, ..., 10]
print(paginate(items, 5))   # [41, 42, ..., 50]
print(paginate(items, 10))  # [91, 92, ..., 100]