[ 코테python반 스터디 ] 3주차 후기

[스터디/10기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 학습중!

https://school.programmers.co.kr/app/courses/14135/dashboard

 

3주차 스터디는 탐색에 관한 개념을 다루었다.

 

그 중에서 소수를 다루는 문제가 기억에 남는다. 

1. 소수 만들기

---

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

 

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

---

 

소수는 1과 자기 자신외에는 나눠지지 않는 수이다. 1부터 n까지 정수 사이에 존재하는 소수를 계산해낼 때 주로 사용하는 방법에 '에라토스테네스의 체'이다. 체는 말 그대로 걸러내는 것인데,  2부터 순서대로 1씩 올려서 그 수의 배수들을 찾아서 제거하는 방식으로 소수를 걸러낸다.

ex) 1, 2, 3, 4, 5, 6, ..., n

=> 1은 소수가 아니므로 제거

=> 2의 배수들을 n까지 찾아서 제거 (4, 6, 8, 10, ...)

=> 3의 배수들을 n까지 찾아서 제거 (6, 9, 12, ...)

=> ...

=> n-1의 배수들을 n까지 찾아서 제거

남은 수들을 정렬하여 리스트화하면 소수 탐색 완료

def get_prime_nums(n):
    
    arr = [i for i in range(n)]
    arr[1] = 0
    
    for i in range(2, n):
        if arr[i] == 0:
            continue
            
        for j in range(2 * i, n, i):
            arr[j] = 0
            
    arr = list(set(arr))
    return arr[1:]

 

그리고 이 예제에서는 리스트에서 숫자 3개를 뽑아 합이 소수인지 확인해야 하기 때문에 combination 함수를 사용할 수 있다.

from itertools import combinations

def solution(nums):
    answer = 0
    
    prime_nums = get_prime_nums(max(nums) * 3)
    combination = combinations(nums, 3)
    for c in combination:
        sum_c = sum(c)
        if sum_c in prime_nums:
            answer += 1
    
    return answer

 

combination을 통해 만든 리스트로 for문을 돌려 합이 소수에 포함되는지 확인하면 끝이다.

 

이걸 하면서 또 느낀 것이 파이썬은 코테 준비하기 정말 좋다는 점이다.

이제 다음주가 마지막 주차이다.

3주동안 많은 문제를 접하며 점점 코테 문제에 접근하는게 어렵게 느껴지지 않는 스스로에 뿌듯함을 느낀다.

앞으로도 많은 문제를 풀어야겠지만 그래도 한달 간 꽤 많은 성취를 얻었다고 생각한다.

다음주 세션때는 기쁜 마음으로 맥주나 마시면서 참가해야겠다.