약수 효율적으로 찾기

목차

모든 경우를 탐색 : 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이므로,

1. 100은 10보다 작은 수 중 [1,2,4,5,10] 으로 나누어 떨어진다. 
2. 100 / 1 = 100
   100 / 2 = 50
   100 / 4 = 25
   100 / 5 = 20
   100 / 10 = 10

따라서 [1, 2, 4, 5, 10, 20, 25, 50, 100 ] 이 100의 약수임을 알 수 있다

10번의 반복을 통해 100의 약수를 구할 수 있으므로 시간 복잡도는 O(√N)이다.

# 약수 개수 구하기 
def getDivNum(number):
    for i in range(1, int(number**(1/2))+1):
        if number%i == 0 :
            cnt= cnt+2 if ( (i**2) != number) else cnt+1 

    return cnt

코드설명 : 

만약 100의 약수를 구한다고 했을 때, 1~10사이의 수 중 10의 제곱은 100과 같다.

따라서 10일 경우 1을 더하고, 다른 수 [1,2,4,5]에 한에서는, 100을 나누었을 때의 나머지도 100의 약수이므로 2를 더한다 

 

# 약수 구하기 
def getDiv(number):
    lst = []
    for i in range(1, int(number**(1/2))+1):
        if number%i == 0 :
            lst.append(i)
            if (i**2) != number:   
                lst.append(number // i)

    return sorted(lst)


print(getDiv(100))

코드 설명 :

만약 100의 약수를 구한다고 했을 때, 1~10사이의 수 중 10의 제곱은 100과 같다. 

따라서 lst라는 리스트에 10은 한번만 추가하고, 다른 수 [1,2,4,5]에 한에서는, 100을 나누었을 때의 나머지도 리스트에 추가한다. 

 

 

관련문제

https://school.programmers.co.kr/learn/courses/30/lessons/136798 

프로그래머스