약수를 구하는 방법

241111

 

오늘 공부한 것은 문제를 풀다 알게 된 약수를 구하는 방법이다.

 

 

 

처음에는 단순하게 내가 생각한 방식으로 코드를 구현했는데....

시간 초과가 나왔다. 시간 복잡도는 O(n) 이여서 그렇게 느리다고는 생각 안 했지만 

수가 커지고 양이 많은 테스트 문제에는 효율이 많이 안 좋았던 거 같다.

def find_divisors_basic(n):
    divisors = []
    for i in range(1, n + 1):
        if n % i == 0:
            divisors.append(i)
    return divisors

# 예시
n = 12
print(find_divisors_basic(n))  # 출력: [1, 2, 3, 4, 6, 12]

 

---

 

 

그 후에 찾아보고 알게 된 것은 제곱근을 사용하는 방법이다.

def find_divisors_sqrt(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:  
                divisors.append(n // i)
    return divisors

# 예시
n = 12
print(find_divisors_sqrt(n))  # 출력: [1, 2, 3, 4, 6, 12]

 

이 방법은 약수는 하나의 쌍으로서 존재하기 때문에 사용할 수 있는 방법이다. 예를 들면 코드에 나왔듯 [1,12], [2,6], [3,4]

이렇게 짝이 되는 수를 한 번에 제곱근까지만 찾으면  효율성이 극대화된다. 시간 복잡도는 (O(√n))이다.

최종적으로 N이 커질수록 제곱근으로 구하는 방식이 더 효율이 좋다는 결론이다.

오늘 배운건 특정 자료의 성질을 이용하면 효율을 극대화할 수 있다는 점이었다.