[알고리즘] 기타 알고리즘 - 소수 판별/에라토스테네스의 체/투 포인터/구간 합

ungnam·2025년 3월 27일

1. 소수 판별

소수란 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)이다. 하지만 약수의 대칭성을 이용하면 시간 복잡도를 O(√X)로 줄일 수 있다.

약수의 대칭성

어떤 수 N의 약수는 일반적으로 (a, b) 형태의 쌍으로 존재한다. 여기서 a * b = N을 만족하므로, 두 수 중 하나는 반드시 √N 이하이다. 즉, b가 √N보다 크다면, a는 √N 이하일 수밖에 없다.

예를 들어, 30의 약수를 생각해보자.

(1, 30)
(2, 15)
(3, 10)
(5, 6)

여기서 5보다 큰 수들은 이미 앞에서 확인한 약수 쌍에 포함되었음을 알 수 있다. 즉, 30의 제곱근인 약 5.47까지만 확인하면 모든 약수 관계를 파악할 수 있다. 따라서 X의 소수 여부를 판별할 때, 2부터 √X까지만 확인하면 충분하다.

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. 에라토스테네스의 체

에라토스테네스의 체는 특정한 범위 내에서 모든 소수를 찾을 때 사용할 수 있는 알고리즘이다.

알고리즘 과정

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

import math

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

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

약수의 대칭성은 에라토스테네스의 체에서도 적용할 수 있다. 따라서, sqrt(n)까지만 순회해도 충분하다.
에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르다 → O(NloglogN)
다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있으나, 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.

3. 투 포인터

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 두 개의 점을 사용하여 처리하는 알고리즘이다.

예를 들어, 2번부터 7번까지의 학생을 지목해야 할 때, 각각 한 명씩 부르는 대신 "2번부터 7번까지"라고 표현하는 것처럼, 리스트 내 특정 범위의 데이터를 효율적으로 탐색할 수 있다.

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

문제 설명

N개의 자연수로 구성된 수열이 주어진다.
합이 M인 부분 연속 수열의 개수를 구하는 문제이다.
수행 시간 제한은 O(N)이다.

일반적인 방법으로는 O(N²)의 시간이 소요될 수 있지만, 투 포인터 알고리즘을 이용하면 O(N)으로 해결할 수 있다.

투 포인터 알고리즘 동작 방식

시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
현재 부분 합이 M과 같다면, 카운트한다.
현재 부분 합이 M보다 작다면, end를 1 증가시킨다.
현재 부분 합이 M보다 크다면, start를 1 증가시킨다.
모든 경우를 확인할 때까지 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)

이 밖에도 투 포인터 알고리즘은 정렬된 두 리스트의 합집합을 구하는 문제에도 사용할 수 있다.

정렬된 리스트의 합집합 구하기

정렬된 리스트 A와 B를 입력받는다.
리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다.
리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 한다.
A[i]와 B[j] 중에서 더 작은 원소를 결과 리스트에 추가한다.
리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번의 과정을 반복한다.

n, m = 3, 4
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)이다. 이는 단순히 각 리스트의 모든 원소를 한 번씩만 순회하면 되기 때문이다. 해당 알고리즘은 병합 정렬과 같은 일부 알고리즘에서도 사용된다.

4. 구간 합

구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제다. 이러한 문제는 여러 개의 쿼리로 구성되는 형태가 많다.

N개의 정수로 구성된 수열과 M개의 쿼리가 주어진다.
각 쿼리는 Left와 Right로 구성되며, 해당 구간 [Left, Right]의 합을 구해야 한다.
만약 M개의 쿼리를 각각 매번 계산하면 O(NM)의 시간 복잡도를 갖지만, 수행 시간 제한은 O(N + M)이다.

이를 해결하기 위해 접두사 합(Prefix Sum)을 사용한다. 접두사 합이란 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것이다.

접두사 합을 이용한 알고리즘

N개의 수 위치 각각에 대해 접두사 합을 계산하여 P에 저장한다.
M개의 쿼리를 확인할 때, 구간 합은 P[Right] - P[Left - 1]로 구한다.

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])