약수 효율적으로 찾기
목차 모든 경우를 탐색 : O(N) def getDiv(num): lst = [] for i in range(1,num+1): if num % i ==0 : lst.append(i) return lst print(getDiv(100)) # [1, 2, 4, 5, 10, 20, 25, 50, 100] 위의 코드의 경우 1부터 100까지 하나하나 비교하여 약수를 찾는다. 만약 1억의 약수를 구하고자 한다면, 1억 번을 반복해야 한다. 시간 복잡도가 O(N) 이기 때문에 수가 커질 수록 런타임 초과 오류 발생 확률이 높아진다. 효율적 탐색 : O(√N) 1부터 √N까지 수 중 나누어 떨어지는 수를 찾고, N을 해당 값으로 나눈다 만약 100의 약수를 구한다면, √100 = 10이므로, 100은 1..
2022. 11. 23.
