기타 알고리즘

Ⅰ. 소수 (Prime Number)

• 소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수입니다.

• 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자추 출제됩니다.

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룹니다.

• 예를 들어 16의 약수는 1, 2, 4, 8, 16 입니다. 4를 기준으로 1,16 2,8은 짝입니다.

• 따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인합니다.

소수의 판별

# 특정 원소가 속한 집합을 찾기
import math

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

print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임

소수의 판별 알고리즘 성능 분석

• 2부터 $X$의 제곱근 (소수점 이하는 무시)까지의 모든 자연수에 대하여 연산을 수행합니다.

• 시간 복잡도는 $O(N^{1/2})$입니다.

Ⅱ. 다수의 소수 판별

• 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때 에라토스테네스의 체를 사용합니다.

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

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

• N보다 작거나 같은 모든 소수를 찾을 때 사용합니다.

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

1. 2부터 $N$까지의 모든 자연수를 나열한다.

2. 남은 수 중에서 아직 처리하지 않는 가장 작은 수 $i$를 찾는다.

3. 남은 수 중에서 $i$의 배수를 모두 제거한다. ($i$는 제거하지 않는다.)

4. 반복할 수 없을 때까지 2번과 3번의 과정을 반복합니다.

다수의 소수 판별 구현

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
# 처음엔 모든 수가 소수(True)인 것으로 초기화
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 * j <= n:
            array[i * j] = False
            j += 1

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

에라토스테네스의 체 알고리즘 성능 분석

• 에라토스테네스의 체 알고리즘의 시간 복잡도는 선형 시간에 가까울 정도로 매우 빠릅니다.

• 하지만 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요한 단점이 있습니다.

• $O( Nlog(logN) )$의 시간 복잡도를 가집니다.

Ⅲ. 투 포인터 (Two Pointers)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘입니다.

• 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때 '2번부터 7번까지 학생' 이라고 부릅니다.

• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있습니다.

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

• N개의 자연수로 구성된 수열이 있습니다.

• 합이 M인 부분 연속 수열의 개수를 구해보세요.

• 수행 시간 제한은 $O(N)$입니다.

* 예를 들어 합 5인 부분 수열 1 2 3 2 5 -> (2,3), (3,2), (5)

부분 연속 수열 찾기 동작 과정

1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.

2. 현재 부분 합이 M과 같다면 카운트한다.

3. 현재 부분 합이 M보다 작다면 끝점을 1 증가시킨다.

4. 현재 부분 합이 M보다 크거나 같다면, 시작점을 1 증가시킨다.

5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

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

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

count = 0
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개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제

• 수열 {10, 20, 30, 40, 50}에서 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90 입니다.

구간 합 계산하기

• N개의 정수로 구성된 수열이 있습니다.

• M개의 쿼리 정보가 주어집니다.

• 각 쿼리는 Left와 Right로 구성됩니다.

• 각 쿼리에 대하여 [Left, Right] 구간에 포함된 데이터들의 합을 출력해야 합니다.

• 수행 시간 제한은 $O(N + M)$입니다.

접두사 합 (Prefix Sum)

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

• $N$개의 수 위치 각각에 대하여 접두사 합을 계산하여 $P$에 저장합니다.

• 매 $M$개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left-1]입니다.

• Left = 1, Right = 3 → P[3] - P[0] = 60

배열 :         10 20 30  40 50

접두사 합 P: 0 10 30 60 100 150

구간 합 계산하기 구현

# 데이터의 개수 N과 전체 데이터 선언
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
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])