[알고리즘] 기타 알고리즘

🫧 소수 판별 알고리즘

✏️ 소수

1보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수
ex) 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니다.
ex) 7은 1과 7을 제외하고는 나누어떨어지지 않으므로 소수이다.

✏️ 기본적인 소스 코드

2부터 X-1까지 모든 자연수에 대해 연산을 수행한다. 시간 복잡도는 O(X)이다.

# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
	# 2부터 (x-1)까지의 모든 수를 확인하며
    for i in range(2, x):
    	# x가 해당 수로 나누어 떨어진다면
    	if x % i == 0:
        	return False # 소수가 아님
            
print(is_prime_number(4)) # False
print(is_prime_number(7)) # True

✏️ 약수의 성질

모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
따라서 제곱근까지만 확인하면 된다.

✏️ 개선된 소스 코드

import math

# 소수 판별 함수 (2이상의 자연수에 대해)
def is_prime_number(x):
	# 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in rane(2, int(math.sqrt(x)) + 1):
    	# x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
        	return False # 소수가 아님
    return True # 소수임
    
print(is_prime_number(4)) # False
print(is_primt_number(7)) # True

✏️ 다수의 소수 판별

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

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

다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다.

✏️ 동작 과정

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

✏️ 소스 코드

시간 복잡도는 O(NloglogN)이다.
하지만 각 자연수에 대한 소수 여부를 저장해야하므로 메모리가 많이 필요하다.

import math

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

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

🫧 투 포인터

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

✏️ 특정한 합을 가진 부분 연속 수열

N개의 자연수로 구성된 수열이 있을 대, 합이 M인 부분 연속 수열의 개수를 구하라.

1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면, 카운트한다.
3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

✏️ 소스 코드

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

count = 9
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
	# end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
    	interval_sum += data[end]
        end += 1
   	# 부분합이 m일 때 카운트 증가
    if interval_sum == m:
    	count += 1
   	interval_sum -= data[start]
    
print(count)

🫧 구간 합 (Interval Sum)

연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제
예를 들어 5개의 데이터로 구성된 수열{10, 20, 30, 40, 50}이 있다고 가정했을 때, 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90이다.

✏️ 구간 합 빠르게 계산하기

1. N개의 정수로 구성된 수열이 있다.
2. M개의 쿼리 정보가 주어진다.
   2-1. 각 쿼리는 Left와 Right로 구성된다.
   2-2. 각 쿼리에 대하여 [Left, Right] 구간에 포함된 데이터들의 합을 출력해야 한다.
3. 수행 시간 제한은 O(N + M)이다.

-> 접두사 합을 이용한다.

✏️ 접두사 합 (Prefix Sum)

배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것

접두사 합을 이용한 알고리즘은 다음과 같다.
1. N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다.
2. 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right]-P[Left-1]이다.

✏️ 소스 코드

# 데이터의 개수 N과 데이터 입력받기
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])

---

Reference

이코테