[알고리즘] 소수의 판별 / 투 포인터 / 구간 합 계산 / 순열과 조합

소수의 판별

[특정 숫자 소수 판별]

• 제곱근 사용.
• 시간 복잡도 : O(X^1/2)

import math

def is_prime_number(x):
	for i in range(2,int(math.sqrt(x))+1):
		if x%i==0:
			return False   #소수 아님
	return True   #소수

is_prime_number(숫자)

 

[특정 범위 소수 판별 (에라토스테네스의 체)]

• 시간 복잡도 : O(NloglogN).
• 메모리를 많이 필요하기 때문에 N이 1,000,000 이내여야 함
  1. 2부터 N까지의 모든 자연수를 나열한다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다
  3. 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다

import math

n = 1000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
	if array[i]==True:
		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=' ')

---

투 포인터

[리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘]

• 리스트 내 원소에 음수 데이터가 포함되어 있는 경우에는 투 포인터 알고리즘으로 문제를 해결할 수 없음
  1. start와 end가 첫 번째 원소의 인덱스(0)을 가리키도록 한다
  2. 현재 부분합이 M과 같다면 카운트한다
  3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다
  4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다
  5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다

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

count = 0
interval_sum = 0
end = 0

for start in range(n):
	while interval_sum < m and end < n:
		interval_sum += data[end]
		end += 1
	if interval_sum == m:
		count += 1
	interval_sum -= data[start]

print(count)

 

 

[정렬되어 있는 두 리스트의 합집합 같은 문제에 효과적으로 사용 가능]

• 시간 복잡도 : O(N+M)
  1. 정렬된 리스트 A와 B를 입력받는다
  2. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다
  3. 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다
  4. A[i]와 B[j] 중에서 더 작은 원소를 결과 리스트에 담는다
  5. 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번의 과정을 반복한다

n,m = 3,4   #a,b의 개수
a = [1,3,5]
b = [2,4,6,8]

result = [0] * (n+m)
i = 0
j = 0
k = 0

while i<n or j<m:
	if j>=m or (i<n and a[i]<=b[j]):
		result[k] = a[i]
		i += 1
	else:
		result[k] = b[j]
		j += 1
	k += 1

for i in result:
	print(i, end=' ')

---

구간 합 계산

 

• 시간 복잡도 : O(N+M)
• N개의 수에 대하여 접두사 합을 계산하여 배열 P에 저장한다
• 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R]-P[L-1]이다

n = 5
data = [10,20,30,40,50]

sum_value = 0
prefix_sum = [0]
for i in data:
	sum_value += i
	prefix_sum.append(sum_value)

left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])

---

순열과 조합

 

• 순열(permutation) : 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것. 모든 경우의 수
• 조합(combination) : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것. 앞뒤가 같은 건 뺀 경우의 수

from itertools import permutations
from itertools import combinations

permutations(리스트,숫자)
combinations(리스트,숫자)