약수1 (Python) 약수 구하기.(시간 복잡도:$O(\sqrt{n})$) 코딩테스트 문제를 풀다보면 어떤 수의 모든 약수를 구해야 할 때가 있다. 아주 간단하게 어떤 수의 약수를 구하는 알고리즘을 알아보자.추가로, 약수를 정렬된 순서로 리턴까지 해보자. 숫자 n의 약수를 구하는 알고리즘을 소개하면 다음과 같다.(시간 복잡도:$O(\sqrt{n})$) 1 ~ $\sqrt{n}$의 범위안에 드는 자연수 i를 대상으로 루프를 돈다. 만약 n이 i로 나누어 떨어진다면, i와 n을 i로 나눈 값은 n의 약수이다. 이를 코드로 나타내면 다음과 같다. x = 100 divisor_set = set() for divisor in range(1, int(x**0.5) + 1): if x % divisor == 0: divisor_set |= {divisor, x // divisor} prin.. 2022. 12. 26. 이전 1 다음