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

Index

1. 소수 판별

2. 에라토스테네스의 체

3. 투 포인터

4. 구간 합

5. 최소 공통 조상

5. 참고자료

---

1. 소수 판별

소수(Prime Number)

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

 

# 시간 복잡도: O(N)
def is_prime(x):
  for i in range(2, x):
    if x % i == 0:
      return False
  return True
  
# 시간 복잡도: O(sqrt(N))
import math

def is_prime(x):
  for i in range(2, int(math.sqrt(x)) + 1):
    if x % i == 0:
      return False
    return True

 

2. 에라토스테네스의 체

에라토스테네스의 체

- 특정한 수의 범위 안에 존재하는 모든 소수 찾기

- O(NloglogN)

- 메모리가 많이 필요

 

(동작 과정)

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

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

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

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

 

(구현)

import math

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

 

3. 투 포인터

투 포인터(Two Pointers)

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

 

(exam)

- 부분 연속 수열 찾기

1. start와 end가 첫 번째 원소의 index(0)를 가리키도록 함

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

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

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

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

 

# n(데이터의 개수), m(찾고자 하는 부분 합), data(전체 수열)

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]

 

4. 구간 합

구간 합(Interval Sum)

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

- Prefix Sum: 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓는 것, P[Right] - P[Left-1]이 구간 합

#n(데이터 개수), data(데이터)

sum_value = 0
prefix_sum = [0]
for i in data:
  sum_value += i
  prefix_sum.append(sum_value)​

 

5. 최소 공통 조상

최소 공통 조상(Lowest Common Ancestor)

- 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제

 

(동작 과정)

1. 모든 노드에 대한 depth를 계산(+2^i번째 부모 정보 계산)

2. 최소 공통 조상을 찾을 두 노드를 확인

- 먼저 두 노드의 depth가 동일하도록 거슬러 올라감

- 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감

3. 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복

 

(기본 구현)

- LCA(https://www.acmicpc.net/problem/11437)

- O(NM): 부모 방향으로 올라갈 때 O(N)

import sys
sys.setrecursionlimit(int(1e5))
n = int(input())

parent = [0] * (n+1)             # 부모 노드 정보
d = [0] * (n+1)                  # 각 노드까지의 깊이
c = [False] * (n+1)                  # 각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n+1)] # 그래프의 정보

for _ in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  
# 깊이를 구하는 함수
def dfs(x, depth):
  c[x] = True
  d[x] = depth
  for y in graph[x]:
    if c[y]:
      continue
    parent[y] = x
    dfs(y, depth + 1)
    
# 최소 공통 조상을 찾는 함수
def lca(a, b):
  while d[a] != d[b]:
    if d[a] > d[b]:
      a = parent[a]
    else:
      b = parent[b]
  while a != b:
    a = parent[a]
    b = parent[b]
  return a
  
dfs(1, 0) # root는 1번

for i in range(m):
  a, b = map(int, input().split())
  print(lca(a,b))

 

(심화 문제)

- LCA2(https://www.acmicpc.net/problem/11438)

- 거슬러 올라가는 속도를 빠르게 만드는 방법: O(logN)

- 각 노드에 대하여 2^i번째 부모에 대한 정보를 기록: NlogN 공간 사용

- DP를 이용하여 시간 복잡도를 개선, 세그먼트 트리도 이용 가능

- O(MlogN)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(le5))
LOG = 21                        #2^20 = 1,000,000

n = int(input())
parent = [[0] * LOG for _ in range(n+1)]
d = [0] * (n+1)
c = [False] * (n+1)
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

# 루트 노드부터 시작하여 깊이를 구하는 함수
def dfs(x, depth):
  c[x] = False
  d[x] = depth
  for y in graph[x]:
    if c[y]:
      continue
    parent[y][0] = x
    dfs(y, depth+1)

# 전체 부모 관계를 설정하는 함수
def set_parent():
  dfs(1, 0)
  for i in range(1, LOG):
    for j in range(1, n+1):
      parent[j][1] = parent[parent[j][i-1]][i-1]
      
# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
  # b가 더 깊도록 설정
  if d[a] > d[b]:
    a, b = b, a
  # 먼저 깊이가 동일하도록
  for i in range(LOG-1, -1, -1):
    if d[b] - d[a] >= (1 << i):
      b = parent[b][i]
  # 부모가 같아지도록
  if a == b:
    return a
  for i in range(LOG-1, -1, -1):
    # 조상을 향해 거슬러 올라가기
    if parent[a][i] != parent[b][i]:
      a = parent[a][i]
      b = parent[b][i]
  # 이후에 부모가 찾고자 하는 조상
  return parent[a][0]

set_parent()

m = int(input())

for i in range(m):
  a, b = map(int, input().split())
  print(lca(a,b))

 

 

---

참고 자료

[Video: 동빈나의  이코테 2021(기타 알고리즘)] https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=10

[Video: 동빈나의  이코테 2021(최소 공통 조상)] https://www.youtube.com/watch?v=O895NbxirM8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=15