[알고리즘] 코딩 테스트에서 자주 출제되는 기타 알고리즘

소수(Prime Number)

소수랑 1보다 큰 자연주 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 ( ex. 7 )

 

def is_prime_number(x):
  # 2부터 (x-1) 까지의 모든 수를 확인하며
  for i in range(2, x-1):
    if x % i == 0:
      return False
  return True
print(is_prime_number(4))
print(is_prime_number(13))

# False
# True

소수(Prime Number) 성능 분석

2부터 X-1까지의 모든 자연수에 대하여 확인을 하며 연산을 수행 -> O(X)

개선된 소수 판별 알고리즘

약수의 성질

모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸

특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인 

특정 수의 제곱근 -> math.sqrt(x)

 

import math
# 소수 판별 :: 성능 개선
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
print(is_prime_number(7))

#True

개선된 소수(Prime Number) 성능 분석

2부터 X의 제곱근까지의 모든 자연수에 대하여 연산 수행 -> 시간 복잡도 : O(N^1/2)

다수의 소수 판별(에라토스테네스의 체)

특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 하는 경우 -> 에라토스테네스의 체 알고리즘

1 ) 다수의 자연수에 대하여 소수 여부 판별

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

 

에라토스테네스의 체 알고리즘 수행 동작 과정

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

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

3. 낭믄 수 중에서 i의 배수를 모두 제거

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

import math

n = 1000
array = [True for i in range(n+1)]

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)

BUT, 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요

투 포인터(Two Pointer)

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

예를 들어 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때 간단히 '2번부터 7번까지의 학생'이라고 부름

리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음

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

N개의 자연수를 가지는 수열이 있음 -> 합이 M인 부분 수열의 개수를 찾아야함 -> 수행 시간 제한은 O(N)

투 포인터를 활용 -> 다음과 같은 알고리즘 수행

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리킴

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

3. 현재 부분 합이 M보다 작다면 end + 1

4. 현재 부분 합이 M보다 크다면 start + 1

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

 

n = 5
m = 5 # 찾고자 하는 부분 합
data = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
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]

print(count)

구간 합(Interval Sum)

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

N개의 정수로 구성된 수열

M개의 쿼리 정보가 주어짐

-> 각 쿼리는 Left와 Right로 구성

-> 각 쿼리에 대하여 [Left, Right] 구간에 포함된 데이터들의 합을 출력

수행 시간 제한은 O(N+M)

 

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

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

매 M개의 쿼리 정보를 확인할 때 구간합은 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)

print(prefix_sum)

left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])