코딩 테스트에서 자주 출제되는 기타 알고리즘

소수 판별 알고리즘

소수 (Prime Number)

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

6 - 1, 6 외에 2, 3으로도 나누어 떨어지므로 소수가 아님
7 - 1, 7을 제외한 수로 나누어 떨어지지 않으므로 소수임

코딩 테스트에서는 임의의 자연수가 소수인지 아닌지 판별하는 문제가 자주 출제

기본적인 알고리즘

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

print(is_prime_number(6)) # False
print(is_prime_number(7)) # True

시간복잡도

O(X) : 2부터 X-1까지의 모든 자연수에 대하여 연산을 수행
→ 약수의 성질을 이용하면 시간복잡도를 줄일 수 있다.

개선된 알고리즘 - 약수의 성질

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

예시

16의 약수: 1 2 4 8 16

이때, 2 x 8 = 16은 8 x 2 = 16과 대칭

따라서, 특정 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 됨

코드

import math

def is_prime_number(x):
  # 2 ~ x의 제곱근까지의 모든 수만 확인
  for i in range(2, int(math.sqrt(x) + 1)):
    if x % i == 0:
      return False
    return True

print(is_prime_number(6)) # False
print(is_prime_number(7)) # True

시간복잡도

O(X1/2) : 2부터 X의 제곱근까지의 모든 자연수에 대하여 연산을 수행

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

다수의 자연수(2 ~ N)에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘

동작 과정

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:
    # 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(NloglogN)
: 선형 시간에 가까울 정도로 매우 빠름

특징

• 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있음

• 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요

---

투 포인터 (Two Pointers)

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

예제

N개의 자연수로 구성된 수열이 있습니다.
합이 M인 부분 연속 수열의 개수를 구해보세요.
수행 시간 제한 O(N)

n = 5 # 데이터의 개수
m = 5 # 찾고하자 하는 부분 합
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개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제

접두사 합(Prefix Sum)

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

S[5] = A[0]+A[1]+A[2]+A[3]+A[4]+A[5]
구간 합 2 ~ 4 = S[4] - S[1]

n = 5 # 데이터의 개수
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = []

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

# 구간 합 계산 index 2 ~ 3
left = 2
right = 3
print(prefix_sum[right] - prefix_sum[left - 1]) # 70