코테 응용하기 좋은 수학 알고리즘

@수학

-포함-배제 등 중고등 수학 응용

-초보가 PS에 들어와서 당황하는 부분

-수식으로 표현할 수 없을까?

 

 

 

 

숫자로 구성된 문자열을 N진법에 맞게 변환하기 위해서는?

 

큰 수 연산할 때는 미리 중간중간 나눠주는 게 더 빠름

 

알면 풀고 모르면 못 푸는 문제들이 있음

 

 

 

 

@최대공약수

 

-공통적인 약수 중 최댓값

-최대공약수가 1이면 서로소

 

 

 

@최대공배수

 

-공통된 배수 중 최솟값

 

LCM(A,B) = A x B|GCD(A,B)

 

GCD만 잘 구하면 LCM은 O(1)에 구할 수 있음

 

# Check from 1

def gcd(a,b):
    ret = 0
    for i in range(min(a,b)):
        if a % i == 0 and b % i == 0 :
            ret = i
    return ret

 

# Check from min(a,b)

def gcd(a,b):
    for i in range(min(a,b), 0, -1):
        if a % i == 0 and b % i == 0 :
            return 1

아래 코드가 좀 더 빠름(반복문에 따른 시간차)

 

 

 

 

@유클리드 호제법

 

유클리드 호제법_위키피디아

 

GCD(A,B) = GCD(B,A%B)

-A와 B의 최대공약수는 A를 B로 나눈 B의 최대공약수와 같음

 

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

유클리드 호제법을 이용하면 이렇게 코드를 줄일 수 있음

 

 

 

 

@소인수분해

 

-2부터 N-1까지 체크

 O(N)

def isPrime(N):
    for i in range(2, N(:
        if N % i == 0 : return False
    return True

 

-2부터 sqrt(N)까지 체크

 O(sqrt(N))

def isPrime(N):
    i = 2
    while i*i <= N:
        if N % i == 0 : return False
    return True

위 코드는 거의 쓰지 않고, 아래 코드를 많이 씀

 

 

 

 

@에라토스테네스의 체

 

-N까지의 소수를 구하기 위해서 sqrt(N)까지의 소수 이용하면 됨

 

def era(N):
    ck, p = [False for _ in range(N+1)], []
    for i in range(2, N+1):
        if ck[i] == True : continue
        p.append(i)
        for j in range(i*i, N+1, i):
            ck[j] = True
   return ck, p

 

 

 

 

@분할정복(Divide & Conquer)

-문제를 분해할 수 있을까?

-재귀함수의 활용

 

 

 

 

@하노이 탑

• 생각 정리

1. 마지막 기둥이 움직이기 위해서는 나머지 모든 것이 한 곳에 있어야 함

2. 그렇다면 N개 중 N-1개를 기둥 2에 보내는 것이 우선

3. N번째 기둥을 3번에 보내고

4. N-1개의 기둥을 다시 기둥 3에 보냄

5. 기둥 1에서 2로 보내는 과정과 2에서 3으로 보내는 과정은 사실 같음

 

F(N) = 2 x F(N-1)+1 //N개 짜리

F(1) = 1 //1개 짜리

 

def hanoi(st, ed, sz):
    if sz == 1 : return print(st, ed)
    hanoi(st, 6 - st - ed, sz - 1)
    print(st, ed)
    hanoi(6 - st - ed, ed, sz - 1)
    
    
n = int(input())
print(2 ** n - 1)
hanoi(1, 3, n)

 

재귀함수 설계할 때는 최소 조건에 대한 조건문을 먼저 써줘야 함

그 후 탈출 조건을 분명하게!