[TIL] Python 관련 이것저것 - 소수, 구간합, 이터레이터

안녕하세요 ~!

오늘은 파이썬에 관한 여러가지를 공부해보았습니다.

1. 소수 

먼저 소수를 파이썬으로 구현해보았습니다.

우선 소수(Prime)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수를 말합니다. 쉽게 말해서 자기 자신과 1만을 약수로 가지는 수가 소수입니다.

이 소수를 구하는 대표적인 방법이 ' 에라스토테네스의 체(Sieve of Eratosthenes) '입니다. 

고대 그리스 수학자 에라토스테네스가 발견한 방법으로 순서는 다음과 같습니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2는 소수이므로 소수 배열에 체크해둡니다.

3. 2를 제외한 2의 배수들을 모두 지워줍니다 => 2를 제외한 2의 배수들은 최소한 3개의 약수( 1, 2, 자기자신)를 가지기 때문입니다.

4. 다음으로 3은 소수이므로 3을 소수 배열에 체크해둡니다.

5. 2와 마찬가지로 3을 제외한 3의 배수를 모두 지워줍니다. => 3번과 같은 이유입니다.

6. 다음 남아있는 수 중에서 5는 소수이므로 5를 남겨둡니다.

7. 5를 제외한 5의 배수를 모두 지워줍니다.

8. 이 과정을 반복해주면 소수만 남게 되고 이 방법이 바로 에라스토테네스의 체 입니다.

이를 파이썬으로 구현하면 아래와 같습니다.

<코드>

M, N = map(int, input().split())

def prime_second(M, N):

primes = [True]*(N+1)

primes[0] = False

primes[1] = False

for i in range(2, int(N**.5)+1):

if primes[i]:

k = i*2

while k <= N:

primes[k] = False

k += i

for i in range(M, N+1):

if primes[i]:

print(i)

위 코드는 백준 1929번 소수 찾기 문제에서 사용한 코드로 두 숫자가 주어지면 두 숫자 범위내에 존재하는 모든 소수를 출력하는 문제입니다. 간단하게 코드를 설명해보겠습니다.

먼저 해당 인덱스가 소수인지 검사해주는 primes 배열에 0,1번 인덱스는 소수가 아니므로 False로 저장해둡니다.

다음 위에서 설명한 순서대로 2의 배수 , 3의 배수, 5의 배수 ... 를 순서대로 False 처리해주면서 소수가 아닌 수를 제거 해나갑니다.

이를 2 ~ N^1/2 + 1 만큼 반복해주면 됩니다.

2. 구간의 합 구하기

- 배열이 있을 때, 연속한 구간의 합이 k 가 되는 경우의 수를 구하라 

=> 투 포인터를 이용한다. 

배열의 원소, k가 자연수일 때만 가능한 풀이법

1) sum = 0, left , right = 0 

sum은 [left,right) 구간의 합이 sum 이라는 것을 의미 현재 [0.0) 의 합은 0

2) k 가 sum 보다 큰 상황이면 left 인덱스 값을 sum에 뺀다. 그리고 left를 1 증가 시켜준다.

k가 sum 보다 작은 상황이면 right 인덱스 값을 sum 에서 더하고, right를 1 증가시킨다. 

3) sum == k 이면 [left, right) 구간의 합이 k이므로 ans++ 해준다.

4) right 배열의 크기와 같다면 => 구간의 끝을 의미 => break 해준다.

아니면 다시 2번 과정 반복한다.

 

최악의 경우 배열의 크기 * 2번 반복하므로 시간복잡도 O(N)의 해결이 가능하다.

<코드>

while(1){

if (sum >= N) sum -= prime[left++];

else if (right == prime.size()) break;

else sum += prime[right++];

if (sum == N) ans++;

}

left, right 두 개의 포인터를 사용하므로 투포인터라고 부른다.

3. 이터레이터(Iterator) 

파이썬 이터레이터는 파이썬의 자료구조인 list, set, Dictionary와 같은 컬렉션이나 문자열을 for 문을 써서 하나씩 데이터를 처리할 수 있는데, 이렇게 하나하나 처리할 수 있는 것을 iterable 객체라고 부릅니다.

참고 

- https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

- http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220553180497