윤년의 수 구하기
(100 의 배수가 아닌 4의 배수이거나 400의 배수인 연도)

def countleapyear(n):
    k=0
    for i in range(1,n+1):
        if((i%100 != 0 and i%4 == 0) or (i%400 ==0)):
            k=k+1
    return k

최대공약수 구하기 (유클리드 호제법)

def gcd(a,b):
    if(a==0):
        return b
    return gcd(b%a,a)

피보나치 수 구하기

def fibonacci(n):
    if(n==0):
        return 0
    if(n==1):
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)

10진수(문자열) -> 2진수

def strdec2bin(dec):
    n=int(dec)
    if(n<2):
        print(n%2,end='')
    else:
        strdec2bin(str(n//2))
        print(n%2,end='')

2진수(문자열) -> 10진수

def strbin2dec(bin):
    n=int(bin)
    a=0
    if n>=10:
        a=strbin2dec(str(n//10))
    return a*2 + n%10

자연수의 분할

def computePart(n,k):
    if(k<1 or n<k):
        return 0
    if(k==1 or k==n):
        return 1
    answer=0
    for i in range(1,k+1):
        answer+=computePart(n-k,i)
    return answer

집합의 분할

def getSetPartitionCount(n,k):
    # 1>=k or k>=n
    if(k<=1 or n<=k):
        return 1
    # 1<k<n
    else:
        return getSetPartitionCount(n-1,k-1)+k*getSetPartitionCount(n-1,k)

Palindrome 확인

# 중간 문자열 반환
def middle(word):
    return word[1:-1]

# 글자수가 없을 때 True
def is_palindrome(word):
    if(len(word)==0):
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(middle(word))

# 글자수가 없을 때 False
def is_palindrome2(word):
    if(len(word)==0):
        return False
    if word[0] != word[-1]:
        return False
    if len(word) <=2:
        return True
    return is_palindrome2(middle(word))

루트의 근사치 (뉴턴의 방법)
(설명)

def mysqrt(a):
    if(a==1):
        return 1
    x=a-1
    epsilon=1e-6
    while True:
        y=(x+a/x)/2
        if abs(y-x) < epsilon:
            break
        x=y
    return y

파이의 근사치 (라마누잔 공식)

import math


def factorial(n):
    if n == 0:
        return 1
    else:
        return n*factorial(n-1)

def estimate_pi():
    total = 0 # total은 1/pi의 근사치 
    k = 0
    factor = 2 * math.sqrt(2) / 9801
    while True:
        num = factorial(4*k) * (1103 + 26390*k)
        den = factorial(k)**4 * 396**(4*k)
        term = factor * num / den
        total += term
        
        if abs(term) < 1e-15:
            break
        k += 1

    return 1 / total

print(estimate_pi())

소인수분해

def print_factor(n):
    if(n==1):
        return 1
    for i in range(2,n+1):
        while(n%i == 0):
            n=n//i
            if(n == 1):
                print(i)
                return
            else:
                print(i,'*',sep='',end='')

소수 판정

def isPrime(n):
    if(n<=1):
        return False
    elif(n==2):
        return True
    for i in range(2,n):
        if(n%i == 0):
            return False
    return True

삼각형 가능 여부
(세 길이 중에 하나가 다른 두 길이의 합보다 크면 삼각형 불가)

def is_triangle(a,b,c):
    if(isinstance(a,int) and isinstance(b,int) and isinstance(c,int)):
        if(a>b+c or b>a+c or c>a+b):
            print("No")
        else:
            print("Yes")

a가 b의 거듭 제곱인지 판단
(숫자 a가 b로 나눌 수 있고, a/b가 b의 거듭제곱이면 a는 b의 거듭제곱)

def is_power(a,b):
    if(a==0):
        return False
    if(a==1):
        return True
    if(a==b):
        return True
    elif(a%b==0):
        return is_power(a//b,b)
    else:
        return False

팩토리얼 함수의 Memo 버전

# Memo version (c type)
fac = [0 for i in range(100)]
def factorial(n):
    if(n==0):
        return 1
    if(fac[n]):
        return fac[n]
    else:
        fac.insert(n,n*factorial(n-1))
    return fac[n]

# Memo version (python type)
known={0:1}
def factorial(n):
    if n in known:
        return known[n]
    
    res=n*factorial(n-1)
    known[n]=res
    return res

피보나치 함수의 Memo 버전

# Memo version
known={0:0,1:1}
def fibonacci(n):
    if n in known:
        return known[n]
    
    res=fibonacci(n-1)+fibonacci(n-2)
    known[n]=res
    return res

번외) math.sqrt와 mysqrt 비교

import math

def mysqrt(a):
    if(a==1):
        return 1
    x=a-1
    epsilon=1e-6
    while True:
        y=(x+a/x)/2
        if abs(y-x) < epsilon:
            break
        x=y
    return y

def test_square_root():
    strFormat="%-20s%-20s%-20s%-20s"
    print(strFormat%('a','mysqrt(a)','math.sqrt(a)','diff'))
    print(strFormat%('-','---------','------------','----'))
    for a in range(1,10):
        print(strFormat%(str(float(a)),str(float(mysqrt(a))),str(math.sqrt(a)),str(abs(float(mysqrt(a))-math.sqrt(a)))))