파이썬 알고리즘 공부 - (6) 자주 나오는 알고리즘 문제

📍소수 문제

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

#기본적인 알고리즘 : 시간복잡도 O(X)
def is_prime_numder(x):
	for i in range(2,x):
    	if x % i == 0:
        	return False # 소수 아님
    return True # 소수임

 

약수는 가운데 약수를 기준으로 대칭을 이루기 때문에

가운데 약수(제곱근)까지만 확인하면 모든 약수를 구할 수 있다

# 개선된 소수 판별 알고리즘 : 시간복잡도 O(N^0.5)
# 제곱근은 그냥 x ** 0.5 로 해도 됨
import math
def is_prime_number(x):
	for i in range(2, int(math.sqrt(x))+1):
    	if x%i == 0:
        	return False
        return True

 

하나의 수에 대해서 소수인지 아닌지 판별하는 방법

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

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

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

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

3. 남은 수 중에서 i의 배수를 모두 제거한다. (i 제외)

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

array = True for i in range(n+1)] #모두가 소수인 것으로 초기화

for i in range(2, n ** 0.5 +1):
	if array[i] == True:
    	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='')

 

📍투 포인터 알고리즘

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

 

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

( 합이 M인 부분 연속 수열의 개수를 구하시오 ) M =5, [ 1 2 3 2 5 ]

 

1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다. 

2. 현재 부분 합이 M과 같다면, 카운트한다. 

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

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

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

 

# n : 데이터 개수, m : 찾고자 하는 부분합 
n = 5
m = 5
data = [1, 2, 3, 2, 5]
count, interval_sum, end = 0

for start in range(n):
	while interval_sum < m and end < n:
    	interval_sum += data[end]
        end += 1
    if interval_sum == m:
    	count += 1
    interval_sum -= data[start]

 

📍구간 합 

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

 

[left, right] 구간에 포함된 데이터들의 합을 출력해야 함

 

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

접두사 합을 다 구해놓으면 구간 합은 P[right] - P[left - 1] 이다. 

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])