[Algorithm/Python] 파이썬 약수 구하기 (시간복잡도 줄여보기)
Develop/Algorithm 2021. 3. 3. 18:16

문제 1 이상의 자연수 N이 주어졌을 때, N의 약수 구하기 풀이 단순한 풀이 방법 def getMyDivisor(n): divisorsList = [] for i in range(1, n + 1): if (n % i == 0) : divisorsList.append(i) return divisorsList for 문을 이용해 범위를 약수가 될 수 있는 최솟값인 1부터 최댓값인 자기 자신까지 돌려준다. 만약, 나머지가 0이라면 약수라는 뜻이므로 배열에 저장해준다. 이 방법을 사용할 경우 작은 수부터 i가 들어가므로 자동으로 오름차순 정렬이 된다. 시간 복잡도 : O(N) 더 효율적인 풀이 방법 def getMyDivisor(n): divisorsList = [] for i in range(1, int(n..