[Algorithm] 12. 기타 알고리즘

소수 판별 알고리즘

• 소수(Prime Number) 란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다.
  • 6 은 1, 2, 3, 6 으로 나누어 떨어지므로 소수가 아니다.
  • 7 은 1 과 7 을 제외하고는 나누어 떨어지지 않으므로 소수이다.
• 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제된다.

• 1보다 큰 자연수가 주어졌을 때 그 자연수가 소수인지 아닌지 판별하기 위해서 2 부터 자기 자신 사이의 모든 수를 확인하며 판별할 수도 있다.

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

기본적인 소수 판별 알고리즘 성능 분석

• 2 부터 x-1 까지의 모든 자연수에 대해여 연산을 수행해야 한다. 즉, 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 $O(X)$ 이다.
• 소수인지 확인하고자 하는 수가 커질수록 시간 복잡도가 선형적으로 비례한다.
• 약수의 성질
  • 약수의 성질을 이용하면 시간 복잡도를 줄일 수 있다.
  • 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루고 있다.
    • 예를 들어 16의 약수는 1, 2, 4, 8, 16 이다.
    • 이 때 2 x 8 = 16 은 8 x 2 = 16 과 대칭이다.
  • 따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다.
    • 예를 들어 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미한다.
    • 즉 대칭이라는 성질 때문에 가운데 약수 이후에 나올 각각의 약수에 대해서도 알 수 있는 것이다.

개선된 소수 판별 알고리즘

import math

# 소수 판별 함수 (2 이상의 자연수에 대하여)
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	      

• 제곱근 값이 소수 이하의 데이터를 가지더라도 int() 를 통해 정상적으로 확인할 수 있다.

개선된 소수 판별 알고리즘 성능 분석

• 2부터 x의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대하여 연산을 수행한다.
• 시간복잡도는 $O(N^{\frac{1}{2}})$ 이다.

에라토스테네스의 체

• 다수의 소수 판별
  • 하나의 수에 대해서 소수인지 아닌지 판별하는 방법을, 약수의 성질을 이용해서 특정한 자연수의 약수를 알고자 할 때 그 수의 제곱근 만큼만 나누기 연산을 수행해서 해당 수에 대한 약수를 알아냈다.
  • 하지만 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때는 어떡할까?
  • 이 때 에라토스테네스의 체 알고리즘을 사용할 수 있다.
• 에라토스테네스의 체 알고리즘은 특정 범위 안에 존재하는 각각의 자연수들이 소수인지 아닌지를 한꺼번에 계산할 때 효과적으로 사용할 수 있다.

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

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다.
• 에라토스테네스의 체는 N 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
• 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다.
  1. 2부터 N 까지의 모든 자연수를 나열한다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 를 찾는다.
     • 이 때 i 의 값은 소수가 될 수 있도록 한다. 즉 지워지지 않아서 소수로 남아있는 수 중에서 아직 처리하지 않은 가장 작은 수를 찾는 것이다.
  3. 남은 수 중에서 i 의 배수를 모두 제거한다(i 는 제거하지 않는다).
     • 여기서 i 는 그 자체로 소수이기 때문에 제거하지 않는다.
  4. 더 이상 반복할 수 없을 때까지 2 번과 3 번의 과정을 반복한다.
• 에라토스테네스의 체 알고리즘 이후 남은 수들은 모두 소수가 된다.
• 약수의 성질은 에라토스테네스의 체 알고리즘에도 적용할 수 있다.

• 즉 N 의 제곱근까지만 확인해서 에라토스테네스의 체 알고리즘을 수행하면 성공적으로 수행 가능하다.

    import math
  
    n = 1000 # 2 부터 1,000 까지의 모든 수에 대하여 소수 판별
    # 처음엔 모든 수가 소수(True) 인 것으로 초기화(0과 1은 제외)
    # 이제 각각의 수가 소수인지 아닌지에 대한 내용은 array 테이블의 인덱스에 접근해서 확인 가능.
    array = [True for i in range(n+1)]
  
    # 에라토스테네스의 체
    # 2 부터 n의 제곱근까지 모든 수를 확인
    for i in range(2, int(math.sqrt(n))+1):
        # i 가 소수인 경우(남은 수인 경우)
        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)$ 이다.
• 에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.
• 그러나 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.
• 10억이 소수인지 아닌지 판별해야 할 때 에라토스테네스의 체를 사용할 수 있을까? 만약 10억 수 하나만 소수 판별을 위한 목적으로 에라토스테네스의 체 알고리즘을 사용한다면 메모리 공간이 크게 필요하다.
• 따라서 경우에 따라서는 메모리 측면에서 비효율적으로 동작할 수도 있다는 것을 기억해둬야 한다.

투 포인터

• 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.
• 흔히 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때 간단히 ‘2번부터 7번까지의 학생’ 이라고 부른다.
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.
• 투 포인터 알고리즘을 사용해서 해결할 수 있는 가장 대표적인 문제는 특정한 합을 가지는 부분 연속 수열 찾기이다.
  • 부분 연속 수열이란 하나의 수열이 있을 때 그 수열에서 연속된 일부분의 데이터만 가지는 수열을 의미한다.

  • N 개의 자연수로 구성된 수열이 있을 때, 합이 M 인 부분 연속 수열의 개수를 구하고자 할 때 어떡할까?

    

  • 수행시간이 $O(N)$ 만큼 제한이 있다면, 다시 말해서 데이터의 개수만큼 원소를 확인하며 선형적으로 동작하는 알고리즘을 설계해야 한다.
  • 이 문제를 완전탐색을 이용해서 간단히 해결하고자 한다면, 각 인덱스에 대해서 해당 인덱스에서 출발하여 합이 M 인 경우를 찾도록 만들면 된다.
  • 그러나 완전탐색을 이용하면 $O(N^2)$ 의 시간 복잡도가 걸리게 된다.
• 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다.
  1. 시작점(start)과 끝점(end)이 첫번째 원소의 인덱스(0)를 가리키도록 한다.
  2. 현재 부분 합이 M 과 같다면, 카운트 한다.
  3. 현재 부분 합이 M 보다 작다면, end 를 1 증가시킨다.
  4. 현재 부분 합이 M 보다 크거나 같다면, start 를 1 증가시킨다.
  5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
• end 가 증가한다는 것은, 모든 원소가 자연수로 구성되어 있기 때문에 현재 부분 합이 증가하는 것을 의미한다. 반대로 start 가 증가한다는 것은 현재 부분 합이 감소한다는 것을 의미하게 된다.
• 이렇게 현재의 부분 합과 M 을 비교해서 그 시작점과 끝점의 위치를 바꾸는 방법을 이용해서 최적의 해를 구할 수 있다.

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
    # while 문을 빠져나올 때는 interval_sum 이 m 보다 크기 때문에 start 값을 빼준다.
    interval_sum -= data[start]

구간 합

• 구간 합 문제란 연속적으로 나열된 N 개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제이다.
• 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50} 이 있을 때, 두번째 수부터 네번째 수까지의 합은 20+30+40 = 90 이다.
• 구간 합을 구하는 과정이 한번만 수행된다면 선형탐색을 이용해 구할 수 있다. 그러나, 구간 합을 구하는 연산을 여러번 해야한다면 어떻게 해야할까?
• 구간 합 빠르게 계산하기
  • N 개의 정수로 구성된 수열이 있다.
  • M 개의 쿼리 정보가 주어진다. 각 쿼리는 left, right 으로 구성된다.
  • 각 쿼리에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다.
  • 수행시간 제한은 $O(N+M)$ 이다.
  • 일반적으로 위 문제에서는 M 번만큼 N 개의 데이터를 반복문을 돌린다. 그래서 $O(N*M)$ 이 된다.
• 구간 합은 접두사 합(Prefix Sum) 을 활용한다. 접두사 합은 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것이다.
• 즉 N 개의 수 위치 각각에 대하여 접두사 합을 계산하여 P 에 저장한다.

• 매 M 개의 쿼리 정보를 확인할 때 구간 합은 P[right] - P[left-1] 이다.

  

• 사전에 계산된 결과를 미리 기록해놓고 그러한 결과를 이용해서 실제 문제들을 빠르게 구할 수 있도록 하는 알고리즘이 여럿 존재하는데, 구간 합 알고리즘도 마찬가지다.
• 시간 복잡도 $O(N)$ 으로 미리 접두사 합을 구할 수 있고, 이를 이용해서 쿼리 정보가 들어올 때마다 값을 출력하도록 한다.

# 데이터의 개수 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])

• 각 쿼리에 대해서 상수시간에 해결 가능하다.

맨 위로 이동 ↑