수학 (진수와진법/최대공약수/최소공배수/소인수분해, 재귀함수)

수학

진수와 진법

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

---

진법 - 예제

• A ** B % C 하게되면, 시간복잡도는 O(B)가 되어 시간이 초과된다.
• 이진수를 활용하여 시간 복잡도를 줄인다.
• 거듭제곱은 거듭제곱간의 곱으로 표현 가능

// 1. mod를 하면서 연산 ( 더 빠름 )
// 수를 mod로 미리미리 나누어주는게 연산이 더 빠르다. 
def pow_custom(a, b, mod):
   ret = 1
   while b :
     if b % 2 == 1 : ret = ret * a % mod
     a = a * a % mod
     b //= 2
   return ret

// 2. 총 결과를 mod하여 리턴
def pow_custom(a, b, mod):
   ret = 1
   while b :
     if b % 2 == 1 : ret *= a
     a *= a
     b //= 2
   return ret % mod

---

최대공약수와 최소공배수

• 최대공약수
  • 공통적인 약수 중 최댓값 최대공약수가 1이면 서로소
• 최소공배수
  • 공통된 배수 중 최소값
• LCM(A,B) = A * B/GCD(A,B)
• GCD만 잘 구한다면 LCM은 O(1)에 구할 수 있다.

---

최대공약수

// 1부터 체크
// 시간복잡도 : min(a,b)
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

// min(a,b) 부터 체크 - 더 빠름
// 시간복잡도 : O(1)
def gcd(a, b):
 for i in range(min(a, b), 0, -1):
   if a % i == 0 and b % i == 0:
 return i

---

유클리드 호제법

• GCD(A,B) = GCD(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)) - 루트N
 def isPrime(N):
 i = 2
   while i*i <= N:
     if N % i == 0: return False
     i += 1
 return True

---

에라토스테네스의 체

• 1은 소수가 아니니 1만 지운다.
• 2는 소수이니, 2의 배수를 모두 지운다.
• 3은 소수이니, 3의 배수를 모두 지운다.
• 4는 소수가 아니니 4만 지운다.
• 5는 소수이니, 5의 배수를 모두 지운다.
• N까지의 소수를 구하기 위해서는 sqrt(N)까지 소수를 이용하면 가능하다.

//시간복잡도 - O(loglogN)
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)

• 문제를 분해할 수 있어야 한다.
• 재귀함수 사용

하노이탑

https://www.mathsisfun.com/games/towerofhanoi.html

Play Tower of Hanoi

---

• 마지막 판이 움직이기 위해서는 나머지 모든 판이 한 기둥에 있어야 한다.
• 그렇다면 N개의 판 중 N-1개의 판을 기둥 2에 보내는 것이 우선이다.
• N번째 판을 3번 기둥에 보내고
• N-1개의 판을 다시 3번 기둥에 보낸다.
• 1번 기둥 -> 2번 기둥의 과정과 2번 기둥 -> 3번 기둥의 과정은 같다.
• F(N) = 2 * F(N-1) + 1
• F(1) = 1

---

def hanoi(st, ed, sz): //start , end , size
     if sz == 1: return print(st, ed)
     hanoi(st, 6-st-ed, sz-1) // 6-st-ed - 중간기둥의 번호
     print(st, ed)
     hanoi(6-st-ed, ed, sz-1)
     
n = int(input())
print(2**n-1)
hanoi(1, 3, n)

• 재귀함수 설계 시 최소 조건 / 탈출 조건 (sz==1) 을 분명하게 지정해야 한다.