소수판별 알고리즘
# 소수 판별
def is_prim_number(x):
# 2부터 (x-1)까지의 모든수를 확인:
for i in range(2, x):
# x가 해당수로 나누어 떨어진다면
if x % i == 0:
reutrn False # 소수가 아님
return True # 소수모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X)
약수를 이용하여 시간 복잡도 줄이기
약수의 특징
- 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
- 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다.
# 소수 판별
def is_prim_number(x):
# 2부터 x의 제곱근 까지의 모든수를 확인:
for i in range(2, int(math.sqrt(x)) + 1):
# x가 해당수로 나누어 떨어진다면
if x % i == 0:
reutrn False # 소수가 아님
return True # 소수
특정한 수 범위 안에 존재하는 모든 소수 찾기
특정 수 범위 안의 존재하는 소수를 모두 찾기 위해서는 에라토스테네스의 체 알고리즘을 사용할 수 있다.
에라토스테네스의 체 알고리즘
에라토스테네스의 체의 동작과정
- 2부터 N까지 모든 자연수를 나열한다.
- 남은 수 중에서 처리 되지 않은 가장 작은 수 i를 찾는다.
- 남은 수 중에서 i의 배수를 모두 제거한다. 이때 i는 제거 하지 않는다.
- 더이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.
import math
n = 1000 # 2부터 1000까지의 모든 수에 대하여 소수 판별
# 처음엔 모든 수가 소수(True)인 것으로 초가화 (0, 1 제외)
arary = [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]: # array에서 True인 값만 출력
print(i, end=' ')에라토스테네스의 체 알고리즘 성능 분석
- 시간복잡도는 O(NloglogN)이라 선형 시간에 가까울 정도로 매우 빠르다.
- 모든 수에 대해서 찾기 때문에 메모리가 많이 필요하기 때문에, 매우 큰 수에 대해서는 적합하지 않을 수 있다.
투 포인터 알고리즘
투 포인터알고리즘은 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 말한다.
리스트에 담긴 데이터에 순차적으로 접근해야 할 때에는 시작점과 끝점 2개의 점으로 접근할 범위를 표현할 수 있다.
특정한 합을 가지는 부분 연속 수열 찾기 문제에서의 투 포인터 알고리즘.
문제 : 수열에서 합이 M인 부분 연속 수열의 개수를 구하기.
동작과정
- 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.
- 현재 부분 합이 M과 같다면, 카운트 한다.
- 현재 부분 합이 M보다 작다면, 끝점을 1증가 시킨다.
- 현재 부분 합이 M보다 크거나 같다면, 시작점을 1 증가시킨다.
- 모든 경우를 확인할 때끼지 2~4번 과정을 반복한다.
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 == n:
count += 1
interval_sum -= data[start]
print(count)구간 합 빠르게 구하기
- N개의 정수로 구성된 수열이 있다
- M개의 쿼리 정보가 주어진다.
* 각 쿼리는 lef와 right로 구성된다.
- 각 쿼리에 대하여[left, right]구간에 포함된 데이터들의 합을 출력해야 한다.
접두사 합(Prefix Sum)
접두사 합: 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것
동작과정
- N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다.
- 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left - 1]이다.
# 데이터의 개수 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]
## 실행결과 : 70