소수 (Prime Number)

• 1보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

def is_prime_number(x):
	for i in range(2, x):
    	if x % i == 0:
        	return False
	return True

• 2부터 X-1 까지 모든 자연수에 대해 연산 수행 => 시간 복잡도는 O(X)

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
  • 16의 약수 : 1, 2, 4, 8, 16
    • 4를 기준으로 2x8, 8x2 대칭
• 특정 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다.
  • 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미

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

• 2부터 제곱근까지만 확인하도록하여 시간복잡도 개선
• O(N^(1/2))

다수의 소수 판별

• 특정 수 범위 안에 존재하는 모든 소수를 찾아야할 때
• 에라토스테네스의 체 알고리즘 사용 !

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

• N보다 작거나 같은 모든 소수를 찾을 때 사용
• 1. 2부터 N까지 모든 자연수 나열
• 2. 남은 수 중 아직 처리하지 않은 가장 작은 소수 i를 찾는다.
• 3. 남은 수 중에서 i의 배수를 모두 제거 (i는 제거하지 않는다.)
• 4. 더 이상 반복할 수 없을 때 까지 2, 3 과정 반복
• N의 제곱근 까지만 수행하면 더 빨라진다.

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=' ')

• O(NloglogN)
  • 선형 시간에 가까울 정도로 매우 빠르다.
• 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.
  • 각 자연수에 대한 소수 여부를 저장하므로 메모리가 많이 필요
  • 10억이 소수인지 아닌지 판별해야할 때.. ㄷㄷ

Two Pointers

• 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 시작점과 끝점 2개 점으로 접근할 데이터의 범위를 표현할 수 있다.

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

• 합이 M인 부분 연속 수열 개수
• 데이터 개수 만큼 해결해야한다면 ? O(N)
• 1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.
• 2. 현재 부분 합이 M과 같으면 count
• 3. 현재 부분 합이 M보다 작다면 end 1 증가
• 4. 현재 부분 합이 M보다 크거나 같다면 start 1 증가
• 5. 모든 경우 확인할 때까지 2 ~ 4 반복
• 슬라이딩
• 같은 인덱스를 가리키고 있으면 부분합은 해당 원소 값이다.

n = 5
m = 5
data = [1, 2, 3, 2, 5]

count = 0
interaval_sum = 0
end = 0

# start를 차례대로 증가
for start in range(n):
	# end를 가능한 만큼 이동
	while interval_sum < m and end < n:
    	interval_sum += data[end]
        end += 1
        
	if interval_sum == m:
    	count += 1
        
	interval_sum -= data[start]

구간합

• 연속적으로 나열된 N개 수에서 특정 구간의 모든 수를 합한 값을 계산하는 문제

구간 합 빠르게 계산하기

• N : data 수
• M : Query 정보 (각 쿼리가 left, right)
• 수행 제한 시간이 O(N + M)이라면 ?
• Prefix Sum : 배열의 맨 앞부터 특정 위치까지 합을 미리 구해 놓은 것
  • N개의 수 위치 각각에 대해 접두사 합을 계산하여 P에 저장
  • M개의 쿼리 정보를 확인할 때 구간합은 P[Right] - P[Left - 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])