[코딩테스트 준비] 기본유형 - 수학 편

n진수 구하기

def stoi(s, n):
    ret = 0
    for i in s: ret = ret*n + int(i)
    return ret

예제 - 곱셈

1629번: 곱셈

일반적으로 생각할 수 있는 a**b%c 로 푼다면 시간초과가 뜬다.

분할 정복을 이용해서 연산의 수를 줄여준다.

def pow_custom(a, b, c):
    ret = 1
    while b:
        if b % 2 == 1:
            ret = ret * a % c
        a = a * a % c
        b //= 2
    return ret

참고) a**b%c 는 (a%c)**b%c 와 같다. 따라서 중간중간 c를 사용해 나머지를 구한 후 곱해도 결과는 같다.

최대공약수와 최소공배수

a, b의 최소공배수 = a*b/a, b의 최대공약수

최대공약수 구하기

# 시간복잡도는 무조건 O(n)이 된다. 
def gcd(a, b):
    ret = 0
    for i in range(min(a, b)):
        if a % i == 0 and b % i == 0:
            ret = i

# a, b 중 더 작은 숫자부터 시작해서 i가 하나씩 줄어들기 때문에 좀더 빠르다. 
def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i 

유클리드 호제법으로 최대공약수 구하기

(A, B) = (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부터 √n 체크 -> 시간복잡도 O(√n)
def isPrime(n):
    i = 2
    while i*i <= n:
        if n % i == 0: return False
        return True

예제 - 에라토스테네스의 체

n까지의 숫자 중에서 소수를 찾기 위해서는 √n 까지의 소수를 구하면 된다.

def era(n):
    check, prime = [False for _ in range(n+1)], []
    for i in range(2, n+1):
        if check[i]: continue  # check[i] 가 true이면(제거됨) 그냥 넘김
        prime.append(i)  # 제거되지 않음 - 소수! 
        for j in range(i*i, n+1, i): # i의 배수를 전부 제거 
            check[i] = True  # 제거 표식으로 True를 남김 
    return check, prime

분할 정복, 재귀 함수

예제 - 하노이탑

1. 마지막 층이 움직이기 위해서는 나머지 모든 층이 한 곳에 있어야 한다.
2. 그렇다면 n개 중 n-1층을 기둥 2에 보내는 것이 우선이다.
3. n번째 층을 기둥 3번에 보내고
4. n-1개의 층을 다시 기둥 3에 보낸다.
5. 기둥 1에서 2로 보내는 과정과, 2에서 3으로 보내는 과정은 같다.

💡 F(N) = 2*F(N-1)+1 , F(1) = 1 (1은 마지막 층)

def hanoi(start, end, size):
    if size == 1: return print(start, end)
		# n-1개를 기둥 1에서 기둥 2로 보낸다. 
    hanoi(start, 6-start-end, size-1) # 시작+중간+끝 = 6 이므로 중간 기둥 = 6-시작기둥-끝기둥
    print(start, end)
		# 나머지를 2에서 3으로 보낸다 
    hanoi(6-start-end, end, size-1)

n = int(input())
print(2**n-1)
hanoi(1, 3, n)

재귀함수를 설계할 때는 최소 조건/탈출 조건을 분명하게 설정해야 한다.

분할 정복에 사용하기 위해서는 줄어든 문제 조건을 표현할 parameter가 필요하다.