[알고리즘] 기타 알고리즘

소수(Prime Number)

* 하나의 소수 판별

: 약수의 성질을 이용, 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대칭을 이룸.

  가운데 약수(제곱근)까지만 확인하는 알고리즘 작성.

import math

#소수 판별 함수(2이상의 자연수)
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))    
print(is_prime_number(7))

=> 2부터 X의 제곱근까지 모든 자연수에 대해 연산을 수행, 시간 복잡도는 O(N^(1/2)) (O의 1/2 제곱)

 

 

* 다수의 소수 판별

: 에라토스테네스의 체 알고리즘 사용.

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

 

<동작 과정>

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

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

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

④ 더 이상 반복할 수 없을 때까지 2-3번의 과정을 반복한다.

import math

n=1000 #2부터 1000까지의 모든 수에 대해 소수 판별
#처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
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(NloglogN)이다. 시간 복잡도는 매우 빠르지감, 각 자연수에 대한 소수 여부를 저장해야하므로 메모리가 많이 필요.

 

 

투 포인터(Two Pointers)

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

  시작점과 끝점으로 리스트의 범위를 표현

 

<동작과정>

① 시작점과 끝점이 첫번째 원소의 인덱스(0)를 가리킨다

② 현재 부분 합이 M과 같다면, 카운트를 하나 높인다.

③ 현재 부분 합이 M보다 작다면, end를 1 증가 시킨다.

④ 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.

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

 

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

n=5 #데이터의 개수 N
m=5 #찾고자 하는 부분합 N
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] #더한 start값을 다시 빼서 다음 start 시 연속수열합 초기화하는 것
    
print(count)

 

 

 

구간 합 (Interval Sum)

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

 : 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있을 때 두번째 수 부터 네번째 수까지 합은 20 + 30 + 40 = 90이다.

 

Q. N개의 정수로 구성된 수열이 있을 경우, M개의 쿼리 정보가 주어지면 각 쿼리는 left, right 으로 구성된다. 각 쿼리에 대해  [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M) 이다)

 

-> 접두사 합(Prefix Sum) : 배열의 첫번째부터 특정 위치까지의 합을 미리 구해 놓는 것.

  N개의 수 위치 각각에 대해 접두사 합을 계산해 P에 저장.

  매 M개의 쿼리 정보를 확인할 때 구간 합은 P[right] - P[left - 1]로 구할 수 있음.

 

#데이터 개수 n과 데이터 입력받기
n = 5
data = [10,20,30,40,50]

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

 

 

 

 

 

 

 

 

 

이코테 2021 강의를 듣고 정리한 내용이다.