ver 01 (메모화 x)
def factor_extractor(n):
if n == 1:
return [1]
if n == 2:
return [1, 2]
if n == 3:
return [1, 3]
factor_list = [1]
for num in range(2, n):
if n % num == 0:
factor_list.append(num)
factor_list.append(n)
return factor_list문제점 : 반복되는 계산
개선 방법 : 메모화(Memorization)
ver 02 (메모화 o)
def factor_extractor(n, memo = {1 : [1], 2 : [1, 2], 3 : [1, 3]}):
if n in memo:
return memo[n]
factor_list = [1, n]
for num in range(2, int(n**0.5) + 1):
if n % num == 0:
factor_list.extend([num, n // num])
memo[n] = factor_list
return sorted(list(set(factor_list)))- factor list에 인수(num)와 몫(n//num)을 함께 추가하므로 제곱근(n**0.5의 소숫점을 버린 정수값)까지만 이터레이션을 돌려서 계산을 줄일 수 있다.
- 마지막 리스트를 리턴할 때 set을 해 주는 이유 : n이 완전제곱수인 경우 중복 숫자가 존재한다. (예 - n이 121인 경우 factor_list에 11이 두 번 들어가므로 하나를 제거해주기 위함이다.)
이렇게 메모화를 해 두면 이미 한 번 했던 계산을 다시 할 필요가 없으므로 훨씬 효율적이다.
# First call with memoization
factor_extractor(10)
# Output: Calculating factors [1, 2, 5, 10]
# Second call with memoization
factor_extractor(10)
# Output: Using cached result [1, 2, 5, 10]
'Code > function snippet' 카테고리의 다른 글
| python | numpy 라이브러리를 이용하여 최대공약수, 최소공배수 구하기 (gcd, lcm) (0) | 2024.04.08 |
|---|---|
| python | 연속 공백 여러개 분리하기, split 함수 대신 정규식(re) 활용하기! (0) | 2024.04.08 |
| python | 재귀함수 (팩토리얼 예제) (0) | 2024.04.01 |
| python | 소수 판별 함수 작성하기 (prime number) (0) | 2024.04.01 |
| python | 중첩리스트 평탄화 함수 작성하기 flatten function (+ 여러번 중첩되는 경우 : 재귀함수!!) (0) | 2024.04.01 |