CS/알고리즘

어떠한 양의 정수 N의 약수를 구할 때 간단하게 생각해보면 다음과 같이 1부터 N까지 나누어보면 쉽게 구할 수 있다는 것은 누구나 생각할 수 있다. def get_divisor(num): res = [] for i in range(1, num + 1): if num % i == 0: res.append(i) return res 하지만 이는 O(N)의 시간 복잡도를 가지므로 N이 매우 커진다면 시간 초과로 문제를 풀 수 없을 것이다. 잘 생각해보면 우리는 약수를 구할 때 1부터 N까지 모두 확인해볼 필요가 없다. 우리는 1부터 N의 제곱근까지만 확인해보면 된다. 어떻게 구할거냐면 1부터 N의 제곱근까지의 수들 중 N과 나누어 떨어지는 수들을 구한다. 그 수들을 N에 대해 다시 나누어서 나머지가 0이 되는,..

유클리드 호제법은 두 양의 정수, 또는 두 다항식의 최대공약수를 구하는 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 말로 설명하자면 다음과 같다. 두 양의 정수 $a,b (a>b)$에 대하여 $a = bq + r (0 ≤ r a: a, b = b, a if a % b == 0: return b return gcd(b, a % b)$O((log N)^2)$의 시간복잡도로 최대공약수를..

순열 : 순서를 고려하여 서로 다른 n개 중 r개 뽑기$$ nPr = \frac{n!}{(n-r)!} $$ 조합 : 순서를 고려하지 않고 서로 다른 n개 중 r 개 뽑기 $$ nCr = \frac{n!}{(n-r)!·r!} $$ 파이썬에서는 itertools 모듈을 이용하여 순열과 조합을 쉽게 구할 수도 있다. 인자로 뽑기를 할 리스트와 뽑을 개수를 넘겨주면 튜플 형태로 리스트에 담아서 반환해준다// 순열from itertools import permutationslst=[1,2,3,4]p_lst = permutations(lst, 2)for el in p_lst: print(el, end=' ') //결과//(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1..