알고리즘을 optimal하게 풀기위해서는 기본적인 수학지식이 필요하다. 공부하면서 정리한 수학관련 내용을 공유해보록 하겠다.

GCD(최대 공약수)

def gcd(a, b):
    # 최대 공약수(GCD)를 계산하는 함수
    while b:
        a, b = b, a % b
    return a

import math

a = 24
b = 36
c = 48

result = math.gcd(math.gcd(a, b), c)
print(result)  # 출력: 12

---

LCM(최소 공배수)

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

def lcm(a, b):
    return (a * b) // gcd(a, b)

# 두 수의 최소공배수 계산
num1 = 12
num2 = 18
result = lcm(num1, num2)
print(result)  # 출력: 36

import math

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

# 두 수의 최소공배수 계산
num1 = 12
num2 = 18
result = lcm(num1, num2)
print(result)  # 출력: 36

---

소수

1. 소수는 자신과 1 이외의 정수로 나누어 떨어지지 않는 정수 —> 2부터 n-1까지 어떤 정수로도 나누어 떨어지지 않음.
2. 홀수 (짝수면 2로 나눠짐)
3. n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않음.

위 룰을 적용하면 1000이하 정수의 소수 찾기 경우의 수를 14622번에서 3774로 줄일 수 있음.

def isPrime(x):
    if x < 2:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False

    return True

itertools: 순열, 조합

이터레이터	인자	결과	예
count()
cycle()	p	p0, p1, … plast, p0, p1, …	cycle('ABCD') --> A B C D A B C D ...
itertools	elem [,n]	elem, elem, elem, … 끝없이 또는 최대 n 번	repeat(10, 3) --> 10 10 10
이터레이터	인자	결과	예
---	---	---	---
accumulate()	p [,func]	p0, p0+p1, p0+p1+p2, …	accumulate([1,2,3,4,5]) --> 1 3 6 10 15
chain()	p, q, …	p0, p1, … plast, q0, q1, …	chain('ABC', 'DEF') --> A B C D E F
chain.from_iterable()	iterable	p0, p1, … plast, q0, q1, …	chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
compress()	data, selectors	(d[0] if s[0]), (d[1] if s[1]), …	compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
dropwhile()	pred, seq	seq[n], seq[n+1], pred가 실패할 때 시작	dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
filterfalse()	pred, seq	pred(elem)이 거짓인 seq의 요소들	filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
groupby()	iterable[, key]	key(v)의 값으로 그룹화된 서브 이터레이터들
islice()	seq, [start,] stop [, step]	seq[start:stop:step]의 요소들	islice('ABCDEFG', 2, None) --> C D E F G
starmap()	func, seq	func(seq[0]), func(seq[1]), …	starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
takewhile()	pred, seq	seq[0], seq[1], pred가 실패할 때까지	takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
tee()	it, n	it1, it2, … itn 하나의 이터레이터를 n개의 이터레이터로 나눕니다
zip_longest()	p, q, …	(p[0], q[0]), (p[1], q[1]), …	zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-

① product

데카르트 곱이라고도 하는 cartesian product를 표현할 때 사용하는 메소드로, 두 개 이상의 리스트의 모든 조합을 구할 때 주로 사용된다.

from itertools import product

② 순열 : permutations

순열을 표현할 때 사용되는 메소드로, 한 리스트에서 중복을 허용하고 모든 경우의 수를 구할 때 사용된다. 반환되는 항목의 수는 n! / (n-r)!이다.

from itertools import permutations

③ 조합 : combinations

조합을 표현할 때 사용되는 메소드로, 한 리스트에서 중복을 허용하지 않고 모든 경우의 수를 구할 때 사용된다. 반환되는 항목의 수는 n! / (n - r)!r!이다.

from itertools import combinations
example = ['a', 'b', 'c']
cb = list(combinations(example, 2))
print(cb)
[('a', 'b'), ('a', 'c'), ('b', 'c')]

④ combinations_with_replacement()

combinations와 동일, 반복 여부에서 차이가 있다.

s = ['ㄱ','ㄴ','ㄷ','ㄹ']
k = 2

이터레이터	인자	결과
product()	p, q, … [repeat=1]	데카르트 곱(cartesian product), 중첩된 for 루프와 동등합니다
permutations()	p[, r]	r-길이 튜플들, 모든 가능한 순서, 반복되는 요소 없음
combinations()	p, r	r-길이 튜플들, 정렬된 순서, 반복되는 요소 없음
combinations_with_replacement()	p, r	r-길이 튜플들, 정렬된 순서, 반복되는 요소 있음

예	결과
product('ABCD', repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD

---

math 모듈

• math.pi: 원주율(pi) 상수를 반환합니다.
• math.e: 자연상수(e)를 반환합니다.
  수학적 함수:
• 삼각함수: math.sin(), math.cos(), math.tan(), math.asin(), math.acos(), math.atan() 등의 삼각함수를 제공합니다.
• 로그 함수: math.log(), math.log10(), math.log2() 등의 로그 함수를 제공합니다.
• 제곱 함수: math.pow(), math.sqrt() 등의 제곱 함수를 제공합니다.
• 지수 함수: math.exp(), math.expm1() 등의 지수 함수를 제공합니다.
• 절댓값: math.fabs(), math.ceil(), math.floor(), math.trunc() 등의 절댓값 함수를 제공합니다.
• 기타 함수:
  math.factorial(): 팩토리얼 값을 계산하여 반환합니다.
  math.comb(): 조합 값을 계산하여 반환합니다.
  math.gcd(): 최대공약수를 계산하여 반환합니다.
  math.isqrt(): 제곱근의 정수 부분을 계산하여 반환합니다.
  math.degrees(), math.radians(): 각도를 라디안으로 변환하거나 라디