[python_파이썬_Summer/Winter Coding(~2018)]프로그래머스_LV1_소수 만들기_풀이_★소수알고리즘, 조합

공부하는허딩크 : https://www.youtube.com/live/fGbdLowsMmU?feature=shared

이번에는 문제만 읽고 설명은 읽지도 않았지만 이해는 갔다.

 

즉, 조합과 소수판별만 알면 바로 해결 할 수 있을 것 같았다.

 

<첫번째 시도 : 맞았습니다.>

소수문제를 거의 한달만에 풀어봐서 소수판별알고리즘이 생각나지 않았다. 백준에서 그렇게 고생하면서 정리했는데..

역시 나는 똑똑하지는 않네.....

itertools는 다행이 combinations만 기억이 나서 풀 수 있었다.

import itertools

def prime(A):

    if A <= 1:

        return 0

    elif A <= 3:

        return 1

    for i in range(2, int(A**0.5) + 1):

        if A % i == 0:

            return 0

    return 1

   

def solution(nums):

    answer = 0

    for i in itertools.combinations(nums, 3):

        if prime(sum(i)):

            answer += 1

    return answer

 

<다른 사람풀이 참고>

1. 비슷하게 combinations로 조합을 만들어 내고, 그 조합을 바로 for문으로 반복했다.

아래와 같이 하면 소수판별시 시간복잡도가 커서 백준에서는 효육적이지 못할 것 같다.

특이한 점은 잘 사용하지 않는 for else문을 사용했다. for문이 다 종료되면 마지막에 else가 돌아간다.

def solution(nums):

    from itertools import combinations as cb

    answer = 0

    for a in cb(nums, 3):

        cand = sum(a)

        for j in range(2, cand):

            if cand%j==0:

                break

        else:

            answer += 1

    return answer

 

<소수 관련 알고리즘 복습> : 아~ 복습은 정말 귀찮아.......

에라토스테네스의체 알고리즘 : https://heodinkcodingdiary.tistory.com/64

[python_파이썬_pass_에라토스테네스의체 알고리즘]백준_4134번_다음 소수_풀이

소수 관련 알고리즘 참고 : https://heodinkcodingdiary.tistory.com/66

★[python_파이썬_pass_소수관련 알고리즘 종합 복습]백준_1929번_소수 구하기_풀이

1. 소수판별 알고리즘의 가장 쉬운 방법은 정수가 1보다 작거나 같으면 return 0

                                                                   정수가 3보가 작거나 같으면 return 1

                                                                   4부터 검사하는 걸로 해서 반복문을 돌린다.

  이때, 임의의 정수를 어떤 숫자로 나눌 건지가 중요한데, 일단 range(2,X)에서 2는 고정이다. 1은 무조건 나누어 떨어지기 때문이다.

X를 어떻게 할거냐... 일단 그냥 임의의 정수와 동일하게 해도 답은 나오지만 시간 복잡도가 좋지 않다.

즉, 시간복잡도를 높이려면 제곱근을 활용해서 int(X**0.5) + 1을 해줘야 한다.

왜냐..... 약수의 개념 때문이다.

임의의 정수가 36이라고 했을때,

1 * 36

2 * 18

3 * 12

4 * 9

5는 없고

6 * 6 이 나온다.

즉 1~6까지가 36의 약수이다. 즉, 작은 약수들이 나누어 떨어진다면 큰약수들은 굳이 매칭시킬 필요가 없다는 의미이다.

(노가다를 한번 해보자)

임의의 정수 (4, 5, 6, 7, 8, 9)

1) 임의의 정수 

4일때 range(2, 4) : 2, 3 => 4는 2로 나눠지니까 return 0

5일때 range(2, 5) : 2, 3, 4 => 나누어지는게 없어서 for문 pass

6일때 range(2, 6) : 2, 3, 4, 5 => 6은 2로 나눠지니까 return 0

7일때 range(2, 7) : 2, 3, 4, 5, 6 => 나누어지는게 없어서 for문 pass

8일때 range(2, 8) : 2, 3, 4, 5, 6, 7 => 8은 2로 나눠지니까 return 0

9일때 range(2, 9) : 2, 3, 4, 5, 6, 7, 8 => 9는 3으로 나눠지니까 return 0

 

2) 제곱근

4일때 range(2, 2 + 1) : 2 => 4는 2로 나눠지니까 return 0

5일때 range(2, 2 + 1) : 2 => 나누어지는게 없어서 for문 pass

6일때 range(2, 2 + 1) : 2 => 6은 2로 나눠지니까 return 0

7일때 range(2, 2 + 1) : 2 => 나누어지는게 없어서 for문 pass

8일때 range(2, 2 + 1) : 2 => 8은 2로 나눠지니까 return 0

9일때 range(2, 3 + 1) : 2, 3 => 9는 3으로 나눠지니까 return 0

 

2. 제곱근을 활용하지 않고, while문으로 5와 (5 + 2)를 활용해서 소수판별을 할 수 있다.

def prime(A):

    if A <= 1:

        return 0

    elif A <= 3:

        return 1

    elif A % 2 == 0 or A % 3 == 0:

        return 0

   

    p = 5

    while (p * p) <= A:

        if A % p == 0 or A % (p + 2) == 0:

            return 0

        p += 6

    return 1

 

3. 에라토스테네스의 체 알고리즘 복습 

def prime(num):

    is_prime = [1] * (num + 1)

    is_prime[0] = is_prime[1] = 0

   

    p = 2

    while (p * p <= num):

        for i in range(p * p, num + 1, p):

            is_prime[i] = 0

        p += 1

    return [i for i in range(num + 1) if is_prime[i]]

 

<itertools복습>

조합관련 설명 : https://heodinkcodingdiary.tistory.com/21

[python_파이썬]itertools 학습_순열(permutions)과 조합(combinations)_풀이

1. combinations() : (iterable, n) ==> iterable에서 원소개수가 n개인 조합 뽑기 (중복 없음, 순서 고려 안함)

   ㄴ 여기서 중복이 없다는 것은 같은 인덱싱 숫자는 선택이 되지 않는다는 의미 => [1, 1] , [2, 2], [3, 3] 안됨

   ㄴ 순서 고려 안함은 아래 예시에서 [1, 2] 와 [2, 1]은 동일한 것으로 본다 => [2, 3], [3, 2] 안됨

2. permutaions() : (iterable, n = None) ==> n = None의 의미는 개수를 입력하지 않으면 기존 iterable의 개수를 유지함.

   ㄴ combinations와 차이점은 중복없음 동일 / 순서 고려함

   ㄴ 순서를 고려한다는 의미는 [1, 2]와 [2, 1]이 다른 값으로 해석된다.

3. combinations_with_replacement() : (iterable, n) ==> iterable에서 원소개수가 n개인 조합 뽑기 (중복 있음, 순서 고려 안함)

   ㄴ combinations과 다른 점은 중복이 있다는 것 => [1, 1] , [2, 2], [3, 3] ok

4. product() : (*iterable, repeat = 1) ==> *가 붙는건 여러 iterable을 인자로 줄 수 있다는 의미, repeat은 출력개수를 의미

   ㄴ repeat 상세 : a = ['A', 'B'] b = [1, 2]의 이터러블한 인자가 있다면 product(a, b, repeat = 1)로 주면 a와 b에서 각 1개씩 출력함.

   ㄴ product(a, repeat = 3)을 하면 a의 인자들을 3개로 조합해서 출력함