[알고리즘 연습] 약수 구하기 효율화 (by Python)

약수 효율적으로 구하기

• 1 이상의 자연수 n을 받았을 때 해당 수의 약수들을 구하라.
• 약수들은 리스트 형태로 숫자 크기 순서대로 출력하라.

---

단순 풀이

def get_divisor(n):
    n = int(n)
    divisors = []

    for i in range(1, n + 1):
        if (n % i == 0):            
            divisors.append(i)            

    return divisors

• 가장 단순한 방법은 for문을 돌면서 하나씩 약수인지 체크(n % i == 0)하여 해당 값을 약수 리스트에 넣어주는 것이다.
• O(N)의 시간복잡도를 가진다.

---

효율화 풀이

def get_divisor(n):
    n = int(n)
    divisors = []
    divisors_back = [] 

    for i in range(1, int(n**(1/2)) + 1): 
        if (n % i == 0):            
            divisors.append(i)
            if (i != (n // i)): 
                divisors_back.append(n//i)

    return divisors + divisors_back[::-1]

• '임의의 자연수 N의 약수들 중에서 두 약수의 곱이 N이 되는 약수 A와 약수 B는 반드시 존재한다'는 규칙이 존재하기 때문에, 자연수 N의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 자동으로 구해진다. (i, n//i)
• 따라서 이를 활용한다.
• 순서대로 정렬하기 위해 새로운 리스트를 만들고 이를 뒤집어 리턴하는 방식을 선택했다.
• O(N^(1/2))의 시간복잡도를 가진다. (반복문에서 O(N^(1/2)), 마지막으로 리스트를 뒤집는 과정은 리스트 크기가 N^(1/2)보다 작을 것이므로 마찬가지로 O(N^(1/2)))