소수(Prime Number)

소수 판별

모든 약수는 약수 중 가운데 약수를 기준으로 대칭을 이루므로, 약수를 찾을 때는 가운데 약수(제곱근)까지만 확인하면 됨

import math


# x가 소수인지 아닌지 판별하는 함수(x는 2 이상의 자연수)
def is_prime_number(x):
	# 2~x의 제곱근까지의 수 중에 x의 약수가 있는지 확인
	for i in range(2, int(math.sqrt(x))+1):
    	if x % i == 0:
        	return False
    return True

다수의 소수 판별

n 미만의 모든 소수 찾기
에라토스테네스의 체 알고리즘 활용
시간 복잡도는 O(NloglogN)
소수인지 여부를 저장할 리스트가 필요하므로 메모리가 많이 필요
1. 2~n까지의 모든 자연수를 나열
2. 남은 수 중 아직 처리하지 않은 가장 작은 수 i 찾기
3. 남은 수 중 i의 배수 모두 제거(남아있는 수인 i는 무조건 소수 -> 제거하지 않음)
4. 더 이상 반복할 수 없을 때까지 2.~3. 반복

import math

# 2~1000 사이의 모든 소수 판별 예시
n = 1000 # 범위
array = [True for i in range(n+1)] # 소수인지 여부가 담긴 리스트(처음에는 0,1 제외하고는 모두 소수인 것으로 초기화)

# 에라토스테네스의 체 알고리즘 수행
# 2 ~ n의 제곱근까지 반복
for i in range(2, int(math.sqrt(n))+1):
	if array[i] == True:
    	# i를 제외한 i의 모든 배수들 지우기
        j = 2
        while i * j <= n:
        	array[i*j] = False
            j += 1

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

투 포인터(Two Pointers)

리스트에 순차적으로 접근해야 할 때 두 개의 점(시작점~끝점)의 위치를 기록하면서 처리하는 알고리즘

[예제] 특정한 합을 가지는 부분 연속 수열 찾기

n개의 자연수(음수가 있을 경우 아래의 방법으로 풀 수 없음)로 구성된 수열에서 합이 m인 부분 연속 수열의 개수 구하기
수행 시간 제한: O(N) (완전 탐색으로 해결할 경우에는 O(N2) 의 시간 소요)
1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 함
2. 현재 부분 합이 m과 같다면 -> 카운트
3. 현재 부분 합이 m보다 작다면 -> end를 1 증가시킴(부분합 증가)
4. 현재 부분 합이 m보다 크거나 같다면 -> start를 1 증가시킴(부분합 감소)
5. 모든 경우를 확인할 때까지 2.~4.의 과정 반복

n = 5 # 데이터의 개수
m = 5 # 찾고자 하는 부분합 m
data = [1,2,3,4,5] # 전체 수열

count = 0 # 부분합의 개수
interval_sum = 0 # m과 비교할 부분합
end = 0 # 끝점

# 시작점(start)을 차례대로 증가시키며 반복
for start in range(n):
	# 끝점(end)을 가능한 오른쪽으로 이동
    while interval_sum < m and end < n:
    	interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 + 1
    if interval_sum == m:
    	count += 1
    interval_sum -= data[start]

# 결과(부분합의 개수) 출력
print(count)

구간 합(Interval Sum)

연속적으로 나열된 n개의 수열에서 특정 구간의 모든 수를 합한 값을 구하기

[예제] 구간 합 계산하기

n개의 정수로 구성된 수열에서, m개의 쿼리에 대해 각 쿼리 구간에 포함된 데이터의 합을 구하기
쿼리 = [시작점, 끝점]
수행 시간 제한은 O(N+M)
-> 접두사 합(Prefix Sum) 알고리즘 활용

• 접두사 합: 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해서 저장하여 캐시처럼 사용

1. N개의 수 위치 각각에 대하여 접두사 합을 계산하여 리스트 P에 저장
2. M개의 쿼리별로 쿼리의 구간합 = P[끝점] - P[시작점-1]

# 데이터의 개수 n과 데이터
n = 5
data = [1,2,3,4,5]

# 접두사 합 배열 prefix_sum 구하기
sum_value = 0
prefix_sum = [0]
for i in data:
	sum_value += i
    prefix_sum.append(sum_value)

# 세 번째부터 네 번째까지의 구간 합 계산
left, right = 3, 4
print(prefix_sum[right] - prefix_sum[left-1])

순열

서로 다른 n개에서 r개를 선택하여 일렬로 나열(순서 O)
경우의 수는 nPr = n! / (n-r)!
각각의 경우를 직접 구할 경우 itertools 라이브러리 사용

import itertools

data = [1,2]
for x in itertools.permutations(data,2):
	print(list(x), end=' ') # [1,2] [2,1]

조합

서로 다른 n개에서 순서에 상관없이 서로 다른 r개 선택(순서x)
경우의 수는 nCr = n! / r! * (n-r)!
각각의 경우를 직접 구할 경우 itertools 라이브러리 사용

import itertools

data = [1,2,3]
for x in itertools.combinations(data,2):
	print(list(x), end=' ') # [1,2] [1,3] [2,3]