기타 알고리즘

소수의 판별

소수?
=> 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다.

• <어떠한 자연수 X가 소수인지 아닌지 판단?>
  => X를 2부터 X-1까지의 모든 수로 나누어보는것이다. 만약 2부터 X-1가지의 모든 자연수가 나누었을 때 나누어떨어지는 수가 하나라도 존재하면 X는 소수가 아니다.

def is_prime_number(x):
  for i in range(2, x) : 
    if x % i == 0 :
      return False
  return True

시간 복잡도가 O(X)이다. 예를 들어 1,000,000을 이라는 숫자를 확인하려면 1,000,000을 2부터 999,999까지의 모든 수에 대하여 하나씩 나누어야 한다.

매우 비효율적

=> 약수의 성질을 이용해서 알고리즘을 개선

"특정한 자연수 X가 소수인지 확인하기 위하여 바로 가운데 약수까지만 '나누어떨어지는지' 확인하면 된다.

다시 말해 제곱근까지만(가운데 약수까지만) 확인하면 됨.
def is_prime_number_2(x) :
for i in range(2, int(math.sqrt(x)) + 1):
if x % i == 0 :
return False
return True

1부터 N까지의 모든 소수를 출력해야 하는 문제
=>에라토스테네스 체 알고리즘
: 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘.
N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

1) 2부터 N까지의 모든 자연수를 나열한다.
2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3) 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거 하지 않는다).
4) 더 이상 반복할 수 없을 때까지 2) 와 3)의 과정을 반복한다.

#처음엔 모든 수가 소수(True) 인것으로 초기화
n = 1000
array = [True for i in range(n + 1)] 


#에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n))+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 = " ")

장점 : 빠르다
단점 : 메모리가 많이 사용됨

따라서 N이 1,000,000이내로 주어지는 경우가 많다.

투 포인터

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

ex) 한 반에 학생이 40명이 있을 때, 2번 부터 7번을 부른다고 하면

-> 2번 학생, ...., 7번 학생 이렇게 다 부를 수도 있고
-> 2번 부터 7번 까지의 학생 이렇게 부를 수도 있는 것

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

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

1 2 3 2 5 를 차례대로 원소로 갖는 리스트가 주어져 있다고 해보자.
이때 합계 값을 5라고 설정하면 다음과 같은 3가지의 경우의 수만 존재

23, 32, 5

그러면 이 문제를 투 포인터 알고리즘을 이용해서 풀어보자

투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이다.
'특정한 합을 가지는 부분 연속 수열 찾기' 문제 에서는 부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록한다. 특정한 부분합을 M이라고 할 때,

1) 시작점과 끝점이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.
2) 현재 부분합이 M과 같다면 카운트 한다.
3) 현재 부분합이 M보다 작으면 end를 1 증가시킨다.
4) 현재 부분합이 M보다 크거나 같으면 start를 1 증가 시킨다.
5) 모든 경우를 확인할 대가지 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 == m :
      count += 1

  interval_sum -= data[start]


print(count)

문제 <정렬되어 있는 두 리스트의 합집합>
=> 이미 정렬되어 있는 2개의 리스트가 입력으로 주어진다. 이때 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하는 것이 문제의 요구사항이다.

sol) 2개의 리스트 A,B가 주어졌을 때, 2개의 포인터를 이용하여 각 리스트에서 처리되지 않은원소 중 가장 작은 원소를 가리키면 된다.

1) 정렬된 리스트 A와 B를 입력받는다.
2) 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 I가 가리키도록 한다.
3) 리스트 B에서 처리되지 않은 원소 증 가장 작은 원소를 J가 가리키도록 한다.
4) A[I]와 B[J]중에서 더 작은 원소를 결과 리스트에 담는다.
5) 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2) ~ 4)의 과정을 반복.

#사전에 정렬된 리스트 A와 B 선언
N,M = 3, 4
A = [1, 3, 5]
B = [2, 4, 6, 8]


# 리스트 A와 B의 모든 워소를 담을 수 있는 크기의 결과 리스트 초기화
result = [0] * (N + M)
I = 0
J = 0
K = 0

#모든 원소가 결과 리스트에 담길 때가지 반복
while I < N or J < M:
  #리스트  B의 모든 원소가 처리되었거나, 리스트 A의 원소가 더 작을 때 
  if J >= M or (I < N and A[I] <= B[J]):
    result[K] = A[I]
    I += 1

  #리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
  else:
    result[K] = B[J]
    J += 1
  K += 1

for i in result:
  print(i, end = " ")
  
정렬되어 있는 두 리스트의 합집합' 알고리즘의 경우 병합 정렬(merge sort)과 같은 일부 알고리즘에서 사용되고 있음.

구간 합 계산

=> 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다.
=> 여러 개의 쿼리로 구성되는 문제 형태로 출제되는 경우가 많다.

항상 우리가 알고리즘을 설계할 때 고려해야 할 점은, 여러 번 사용될 만한 정보는 미리 구해 저장해 놓을수록 유리하다는 것이다.

구간 합 계산을 위해 가장 많이 사용되는 기법이 바로 "접두사 합"이다.

여기서 "접두사 합" 이란? 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다.

1) N개의 수에 대하여 접두사 합(Prefix sum)을 계산하여 배열 P에 저장한다.
2) 매 M개의 쿼리 정보[L,R]을 확인할 때, 구간 합은 P[R] - P[L-1]이다.

10 20 30 40 50의 접두사 합은

0 10 30 60 100 150
P[0] P[1] P[2] P[3] P[4] P[5]

EX) 첫 번째 쿼리는 첫 번째 수부터 세 번째 수까지의 구간 합을 물어보는 [1,3]이라고 해보자.
이 경우, P[3] - P[0] = 60 이 답이 된다.

#데이터의 개수 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 - 1])

순열과 조합

=> 다양한 알고리즘 문제에서 순열과 조합을 찾는 과정을 요구하곤 한다.
=> 파이썬은 순열과 조합 라이브러리를 기본적으로 제공하고 있으므로 이를 간단히 이용할 수 있다.

cf) 경우의 수 : 한 번의 시행에서 '일어날 수 있는 사건의 가지수'
동전 던지기의 경우 앞면 혹은 뒷면이므로 2가지 , 주사위 던지기의 경우 {1,2,3,4,5,6}중 하나 이므로 6가지이다.

순열 : 서로 다른 n개에서 r개를 선택하여 일렬로 나열

nPr = n! / (n - r)! 이다.

순서 상관 x**
다만, 코딩테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우(사건)를 다 출력하도록 요구하기도 한다. 이럴 때는 파이썬의 itertools 라이브러리를 이용한다.

import itertools

data = [1, 2]

for x in itertools.permutations(data, 2):
  print(list(x))

조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택

nCr = n! / r! x (n-r)!

import itertools

data = [1, 2, 3]

for x in itertools.combinations(data, 2):
  print(list(x))
  

ex1)소수 구하기

#소수 구하기 

import math 


#M과 N을 입력받기

m, n = map(int, input().split())
array = [True for i in range(1000001)] #처음에는 모든 수가 소수(True)인 것으로 초기화
array[1] = 0 #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(m, n+1):
  if array[i]:
    print(i)