소수 여부를 판별할 수 있는 함수를 작성해 보자.

참고로 숫자 1은 소수가 아니다!

 

def prime_num_classify(n):
    if n == 1:
        return False
    elif n in [2, 3, 5, 7]:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    else:
        for i in range(3, n // 2):
            if n % i == 0:
                return False
    return True
 

위 코드는 정상 작동하지만 숫자가 커질수록 비효율성이 커진다. chatGPT는 위 코드를 100점 만점에 50점으로 평가하였으며 이를 개선할 수 있는 90점짜리 최적화 코드를 제공하였다.

 

else 이후 부분을 주목해서 보자.

def prime_num_classify(n):
    if n == 1:
        return False
    elif n in [2, 3, 5, 7]:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    else:
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
    return True
 

Breakdown

    else:
        i = 5

먼저 소수판별을 할 n의 인수(나누어줄 수)로 숫자 5부터 점검하기 시작한다. 왜 5부터 시작할까? 인수로 2, 3은 elif구문에서 이미 판별하였고, 4는 짝수라서 역시 elif구문에서 걸러졌기 때문이다.

        while i * i <= n:

인수의 제곱이 나누어지는 수(n)보다 작은 경우에만 이터레이션을 돌린다. 다르게 말하면, n의 제곱근 정수값 int(n ** 0.5) 보다 i가 작거나 같은 경우에만 이터레이션을 돌린다. 왜 그럴까?

 

We only need to test divisibility by potential factors up to the square root of n. This is because if n has a factor larger than its square root, it must also have a corresponding factor smaller than its square root.

 

우리는 i가 주어진 수(n)의 인수가 되는지, 즉 n이 i로 나누어 떨어지는지를 살펴 보며 소수를 판별한다. 이 때 i값은 n의 제곱근 정수값 int(n ** 0.5)까지만 살펴보면 되는데, 그 이유는 인수와 몫의 관계 때문이다. 아래 예시를 확인해 보면, 나눗셈을 할때 제곱근 정수를 기준으로 인수와 몫이 갈라지게 되는 것을 확인할 수 있다.

 

(예)

  1. 숫자 225의 약수는 [1, 3, 5, 9, 15, 25, 45, 75, 225]이다. 225의 제곱근 정수는 15이다. 15를 기준으로(225는 완전제곱수) 9 * 25 = 225와 같이 인수(9)와 몫(25)이 갈라지는 것을 확인할 수 있다.
  2. 숫자 108의 [1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108] 이다. 108의 제곱근 정수는 10이다. 10을 기준으로 9 * 12 = 108과 같이 인수(9)와 몫(12)이가 갈라지는 것을 확인할 수 있다.

 

따라서 제곱근 정수 이하의 숫자에 인수가 있는지만 확인하면 계산을 단축하여 효율성을 높일 수 있는 것이다. (9 * 12 = 108, 12 * 9 = 108과 같은 중복 계산을 제외하게 되는 것.)

 

만약 n = 119일 경우를 생각해 보자. i = 5부터 시작하면, i * i = 25이므로 True가 되어 if문을 살펴보게 된다.

            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
 

119은 5로 나누어지지 않는다.

119는 7로 나누어 떨어진다. (몫 : 17)

따라서 119는 소수가 아니므로 False를 리턴하고 함수가 종료된다.

 

그렇다면 if문에서는 왜 i + 2만 함께 점검하는 걸까?

  1. 우리가 점검해 줄 i값은 5에서 시작하여 2씩 늘려주면 된다. 왜냐면 홀수값만 판별하면 되니까. 주어진 숫자 n이 짝수로 나누어 떨어지는지는 그 전에 이미 확인을 했다. (elif 구문)
  2. i + 1, i + 3, i + 5 모두 짝수이기 때문에 확인할 필요가 없다.
  3. 그럼 i + 4는 왜 안해도 될까? i + 4의 경우 확인해 보면 3의 배수가 되는 것을 알 수 있다. 따라서 i + 6을 해준 다음 이터레이션을 돌리는 것이다. 이 과정을 통해 계산 시간을 줄이고 효율성을 높이게 되었다.

 

'Code > function snippet' 카테고리의 다른 글

python | numpy 라이브러리를 이용하여 최대공약수, 최소공배수 구하기 (gcd, lcm)  (0) 2024.04.08
python | 연속 공백 여러개 분리하기, split 함수 대신 정규식(re) 활용하기!  (0) 2024.04.08
python | 재귀함수 (팩토리얼 예제)  (0) 2024.04.01
python | 약수(factor) 리스트업 함수 작성하기 + 메모화 (memorization)  (0) 2024.04.01
python | 중첩리스트 평탄화 함수 작성하기 flatten function (+ 여러번 중첩되는 경우 : 재귀함수!!)  (0) 2024.04.01

 

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)))
 
  1. factor list에 인수(num)와 몫(n//num)을 함께 추가하므로 제곱근(n**0.5의 소숫점을 버린 정수값)까지만 이터레이션을 돌려서 계산을 줄일 수 있다.
  2. 마지막 리스트를 리턴할 때 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

 

 

가끔 코딩 테스트에서 이거.. 리스트를 평탄화해주면 쉽게 풀 수 있겠는데? 라는 생각이 들 때가 있습니다. 프로그래머스 0단계에서는 이 평탄화 함수를 작성하는 것 자체가 문제로 출제되기도 했었던거 같기도 하구요. 어쨌든 알고 있으면(또는 외워 두면) 정말 너무나!!!! 큰 도움이 되는!!!!! 평탄화 함수 작성하는 방법!!! 정리해 봅시다.

 

* 설명 없이 함수만 빠르게 확인하고 싶으시다면 글 맨 아래로 가세요! *

 

 

 

 

먼저, 중첩 리스트란 무엇일까요?

normal_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
weird_list = [1, 2, [3], 4, 5, [6], 7, [8, 9, 10]]
crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]

위 세 가지 리스트를 살펴 봅시다.

 

먼저 멀쩡한 리스트 normal_list는 참 보기 좋습니다.

그런데 weird_list는 리스트 안에 리스트를 원소로 가지고 있네요. [3], [6], [8, 9, 10]과 같이 말이죠. 이런 놈들을 중첩 리스트라고 부르겠습니다. 그래도 여기까진 어찌저찌 해체해볼 수 있을 것 같습니다.

 

그런데 crazy_list.. 이 미친놈을 보니까 리스트 안에 리스트가 또 리스트를 가지고 있어요. 중첩에 중첩에 중첩에 중첩에 중...!!!

 

 

평탄화란? (Flatten)

weird_list, crazy_list, crazy_list_and_tuple처럼 중첩된 리스트를

normal_list처럼 1차원의 리스트로 평평(Flat)하게 평탄화(Flatten)해주는 작업을 의미합니다.

 

만약 우리가 리스트 안에 있는 모든 값들 중에서 가장 큰 값을 구해야 된다면 어떻게 할까요?

normal_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
max(normal_list)
# 10

crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]
max(crazy_list)
# ????????

1차원 리스트인 normal_list의 경우 내장함수 max()를 사용하면 아주 쉽게 최댓값을 구해낼 수 있지만, 우리의 미친놈 crazy_list는 그렇게 호락호락하지가 않습니다. 

 

 

평탄화 함수 작업하기

리스트 안에 리스트가 들어가 있는 중첩 리스트를 하나의 리스트로 평탄화(Flatten)하는 회귀함수를 작성해 봅니다. 먼저 weird_list를 가지고 생각을 열어 보겠습니다.

weird_list = [1, 2, [3], 4, 5, [6], 7, [8, 9, 10]]

def easy_flatten(nested_list):
    result = []

    for element in nested_list:
        if isinstance(element, list):
            result.extend(element)
        else:
            result.append(element)

    return result
    
easy_flatten(weird_list)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

weird_list의 원소를 하나씩 점검합니다. 만약 원소가 리스트라면 result에 그 리스트를 extend해서 합쳐 주고, 원소가 리스트가 아니라면 해당 원소를 append를 이용해서 result에 추가해 줍니다. weird_list가 예쁘게 평탄화된 것을 확인할 수 있습니다.

 

 

그렇다면 easy_flatten 함수를 가지고 crazy_list도 평탄화 작업이 될까요?

crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]
easy_flatten(crazy_list)
# [1, 2, [3], 4, 5, [6], 7, [8, [9, [10]]]]

 

우리가 원하는 결과가 나오지 않았습니다. 중첩에 중첩이 여러번 반복되는 경우를 생각해주지 못했기 때문입니다. 그렇다면 여러 개의 중첩을 풀어주는 함수를 어떻게 작성할 수 있을까요? 중첩이 몇 번 반복되는지 알 수 없다는 점에 착안하여, 재귀함수(recursion)를 작성해 보겠습니다.

 

 

재귀함수를 적용한 Flatten 함수

def hard_flatten(nested_list):
    result = []

    for element in nested_list:
        if isinstance(element, list):
            # 유일하게 달라진 부분 - element 대신 hard_flatten(element)❤️
            result.extend(hard_flatten(element))
        else:
            result.append(element)

    return result

 

만약 nested_list의 element가 list 객체라면 result에 hard_flatten(element)를 추가해주도록 재귀함수가 작성되었습니다. 이렇게 여러 번 중첩이 반복되는 경우 자기 자신을 호출함으로써 문제를 간단히 해결할 수 있게 되었습니다.

crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]
hard_flatten(crazy_list)
#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

우리가 원하는 결과값을 얻었네요!

이 리스트 평탄화 함수는 여러 번 작성해보시면서 외워 두시면 필요할 때 요긴히 사용하실 수 있을거에요.

 

 

(적용 예시)

 
# 리스트 k에서 하트를 모두 제거한 1차원 리스트를 출력하세요
k = [['a', 'b', ['🩶', 'd']], 'e', 'f', '🩶', [['🩶'], 'i']]

[element for element in hard_flatten(k) if element != '🩶']
# ['a', 'b', 'd', 'e', 'f', 'i']
 

 

감사합니당!

'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 | 약수(factor) 리스트업 함수 작성하기 + 메모화 (memorization)  (0) 2024.04.01

+ Recent posts

티스토리툴바