[이코테] 기타 알고리즘

소수 (Prime Number)

• 1보다 큰 자연수 중에서 1과 자기자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수
• 소수 판별 문제 자주 출제됨

# 일반적인 소수 판별 함수
def is_prime_number(x):
	# 2부터 (x-1)까지 모든 수 확인
    for i in range(2, x):
        #x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False #소수 아님
    return True #소수 O

print(is_prime_number(4))
print(is_prime_number(7))
    

알고리즘 성능

• 2부터 X-1까지의 모든 자연수에 대하여 연산을 수행해야 함
  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X)

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸
• 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 됨
  

개선된 소수판별 알고리즘

# 개선된 소수판별 함수 - 2 이상의 자연수에 대하여
import math
def is_prime_number(x):
    #2부터 x의 제곱근까지의
    for i in range(2, int(math.sqrt(x))+1):
        #x가 해당 수로 나누어 떨어진다면
        if x % 1 == 0:
            return False # 소수가 아님
    return True #소수 O
print(is_prime_number(4))
print(is_prime_number(7))    

알고리즘 성능

• 2부터 X의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대하여 연산
  • 시간 복잡도 O(N½)

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

• 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘
• N보다 작거나 같은 모든 소수를 찾을 때 사용 가능
  1. 2~N까지의 모든 자욘수 나열
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾음
  3. 남은 수 중에서 i의 배수를 모두 제거 (i는 제거 X)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정 반복

# 에라토스테네스의 체 알고리즘 (Python)
import math
n = 1000

# 모든 수가 소수(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의 모든 배수 지우기
        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) : 사실상 선형 시간에 가까움
• but 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요 - 메모리 측면에서 매우 비효율적일 수 O

투 포인터 (Two Pointers)

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

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

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

n,m = 5,5
data = [1,2,3,2,5]

#순차적 접근

start, end, count = 0,0,0
sum = 0
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while sum < m and end < n:
        sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if sum == m:
        count += 1
    sum -= data[start]

print(count)

구간 합 (Interval Sum)

• 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제

문제: 구간 합 빠르게 계산하기

• 접두사 합(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])