[SW사관학교정글] WEEK01 개발일지 - Ⅴ

수학

순열

순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다. 즉, 서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시한다.

순열은 순서를 고려하기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 순서를 정해 나열하면 [(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] 가 나오게 된다. 즉 순열에서는 (A, B)와 (B, A)는 다른 것이다.

import itertools
arr = ['A', 'B', 'C']
nPr = itertools.permutations(arr, 2)

조합

조합이란 서로 다른 n개 중에서 r개(n>=r)취하여 조를 만들 떄, 이 하나하나의 조를 n개 중에서 r개를 취한 조합이라고 한다.

조합은 순서를 고려하지 않기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 나열하면 [(A, B), (A, C), (B, C)] 가 나오게 된다. 조합은 (A, B)와 (B, A)는 같은 것으로 취급한다.

import itertools
arr = ['A', 'B', 'C']
nPr = itertools.combinations(arr, 2)

소수

소수란 수학에서 1과 그 수 자신 이외의 자연수로 나눌 수 없는, 1보다 큰 자연수이다.

에라토스테네스의 체 알고리즘

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다
• 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다
• 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다
  1. 2부터 𝑁까지의 모든 자연수를 나열한다
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 𝑖를 찾는다
  3. 남은 수 중에서 i의 배수를 모두 제거한다(𝑖는 제거하지 않는다)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다
  [Step 4] 마찬가지의 과정을 반복했을 때 최종적인 결과는 다음과 같다

에라토스테네스의 체 알고리즘 동작 과정

	[초기 단계] 2부터 26까지의 모든 자연수를 나열한다 
	[Step 1] 아직 처리하지 않은 가장 작은 수 2를 제외한 2의 배수는 모두 제거한다
	[Step 2] 아직 처리하지 않은 가장 작은 수 3을 제외한 3의 배수는 모두 제거한다
	[Step 3] 아직 처리하지 않은 가장 작은 수 5를 제외한 5의 배수는 모두 제거한다
    [Step 4] 마찬가지의 과정을 반복했을 때 최종적인 결과는 다음과 같다
    

에라토스테네스의 체 알고리즘

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            array[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

수학 관련 백준 문제 Github 링크
백준 수학 관련 문제