조금만 더 쉬다 갈까? 기초수학 2편

제로베이스 데이터 취업 스쿨 2주차 스터디노트 2호

유클리드 호제법

너무 신기한 알고리즘... 인류 최초의 알고리즘이라고 한다.
최대공약수를 쉽게 구할 수 있는 방법이다.
$a = bq + r$
$gcd(a, b) = gcd(b, r)$

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

피보나치 수열

반복문과 재귀함수를 사용해서 표현할 수 있다.

# 반복
def fib_rep(n):
    x, y = 0, 1
    for idx in range(n):
        x, y = y, x + y
    return x

# 재귀
def fib_recur(n):
    if n == 1 or n == 2:
        return 1
    return fib_recur(n - 2) + fib_recur(n - 1)

팩토리얼

역시 반복문과 재귀함수를 사용해 표현할 수 있다.

# 반복
def factorial_rep(n):
    result = 1
    for idx in range(1, n + 1):
        result *= idx
    return result

# 재귀
def factorial_recur(n):
    if n == 1:
        return 1
    return n * factorial_recur(n - 1)

군수열

영어로 뭐라고 하는지 찾을 수 없었다. 흠...
다양한 용도로 쓰고 싶어서 일반화를 해보았다.
근데 이걸 쓸까? 안 쓸듯ㅋㅋ

def arithmetic(n, cd, a1): # 등차수열
    return cd * (n - 1) + a1

def geometric(n, cr, a1): # 등비수열
    return a1 * cr ** (n - 1) 

def seq(n): # 개별 군의 수열 진행 방식
    return geometric(n, 3, 2)

def grp(n): # 전체 군의 진행 방식
    return arithmetic(n, 2, 3)

def seq_grp(n):
    x, cur_count = 1, 0
    while cur_count + grp(x) < n:
        cur_count, x = cur_count + grp(x), x + 1
    return seq(n - cur_count)

for i in range(1, 20):
    print(seq_grp(i), end=", ")
# 2, 6, 18, 2, 6, 18, 54, 162, 2, 6, 18, 54, 162, 486, 1458, 2, 6, 18, 54, 

# (2, 6, 18), (2, 6, 18, 54, 162), (2, 6, 18, 54, 162, 486, 1458), (2, 6, 18, 54, ...)