Algorithms etc part2 (기타 알고리즘 파트2)

In [6]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

9. Algorithms ETC part2¶

Objective¶

1. Priority Queue & Heap
2. Tree Data Structure
3. Bellman Ford Algorithm
4. Binary Indexed Tree (Fenwick Tree)
5. Lowest Common Ancestor Algorithm (LCA)

1. Priority Queue & Heap (우선순위 큐와 힙)¶

1-1. 우선순위 큐 (Priority Queue)¶

• 우선순위 큐 는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 입니다.
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.
  • 예시) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우
• Stack : FILO 구조로 가장 나중에 삽입된 데이터가 가장 먼저 추출됩니다.
• Queue : FIFO 구조로 가장 먼저 삽입된 데이터가 가장 먼저 추출됩니다.
• Priority Queue : 가장 우선순위가 높은 데이터가 가장 먼저 추출됩니다.

1-2. 우선순위 큐 (Priority Queue) 의 구현¶

• 리스트(List) 를 이용하여 구현
• 이중 연결 리스트(Doubly Linked List) 를 이용하여 구현
  • 이중 연결 리스트로 구현한 우선순위 큐

• 힙(Heap) 을 이용하여 구현

  • 힙 자료구조 1
  • 힙 자료구조 2

• 구현 방식에 따른 시간 복잡도

  • 리스트 : 삽입 $O(1)$ 삭제 $O(N)$
  • 이중 연결 리스트 : 삽입 $O(N)$ 삭제 $O(1)$
    • 구현 방식에 따라 삽입, 삭제 가 뒤바뀔수 있음
  • 힙 : 삽입 $O(logN)$ 삭제 $O(logN)$
    • 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 $O(NlogN)$이며 정렬과 동일

1-3. 힙 (Heap)¶

• 힙은 완전 이진 트리 자료구조의 일종입니다.
  • 완전 이진 트리
• 힙에서는 항상 루트 노드 (root node) 를 제거합니다.
• 최소 힙
  • 루트 노드가 가장 작은 값을 가집니다.
  • 따라서 값이 작은 데이터가 우선적으로 제거됩니다.
• 최대 힙
  • 루트 노드가 가장 큰 값을 가집니다
  • 따라서 값이 큰 데이터가 우선적으로 제거됩니다.
• 힙 자료구조 1
• 힙 자료구조 2

1-4. 힙 (Heap) 의 동작¶

• 새로운 원소가 삽입되었을 때 $O(logN)$의 시간 복잡도로 힙 성질을 유지하도록 할 수 있습니다.
  • (상향식) 원소가 추가되 었을 때는 가장 마지막에 노드를 위치시켜, 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체합니다.
• 원소가 제거 되었을 때 $O(logN)$의 시간 복잡도로 힙 성질을 유지하도록 할 수 있습니다.
  • (하향식) 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 합니다. 이후 자식 노드들과 값을 비교 후 자식노드보다 자신의 값이 더 큰 경우 위치를 교체합니다.

1-5. 힙 (Heap) 을 활용한 힙 정렬¶

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []

for i in range(n):
    arr.append(int(input())

res = heapsort(arr)

for i in range(n):
    print(res[i])

2. Tree Data Structure (트리 자료 구조)¶

2-1. Tree (트리)¶

• 트리 는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조입니다.
• 트리 관련 용어
  • 루트 노드 (root node) : 부모가 없는 최상의 노드
  • 단말 노드 (leaf node) : 자식이 없는 노드
  • 크기 (size) : 트리에 포함된 모든 노드의 개수
  • 깊이 (depth) : 루트 노드로부터의 거리
  • 높이 (height) : 깊이 중 최댓값
  • 차수 (degree) : 각 노드의 (자식 방향) 간선 개수
• 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1 입니다.
• 트리 자료구조
• 이진 트리 자료구조

2-2. Binary Search Tree (이진 탐색 트리)¶

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종
• 이진 탐색 트리의 특직 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  • 부모 노드보다 왼쪽 자식 노드가 작습니다.
  • 부모 노드보다 오른쪽 자식 노드가 큽니다.
• 이진 탐색 트리 자료구조
• 이진 탐색 트리 연산

2-3. Tree Traversal (트리의 순회)¶

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미합니다.
  • 트리의 정보를 시각적으로 확인할 수 있습니다.
• 대표적인 트리 순회 방법
  • 전위 순회 pre-order traverse : 루트를 먼저 방문합니다.
  • 중위 순회 in-order traverse : 왼쪽 자식을 방문한 뒤에 루트를 방문합니다.
  • 후위 순회 post-order traverse : 오른쪽 자식을 방문한 뒤에 루트를 방문합니다.
• 트리 순회

In [1]:

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
        
def pre_order(node):
    print(node.data, end = ' ')
    if node.left_node != None:
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])

def in_order(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end = ' ')
    if node.right_node != None:
        in_order(tree[node.right_node])

def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end = ' ')

In [7]:

n = int(input())
tree = {}

for i in range(n):
    data, left_node, right_node = input().split()
    if left_node == "None":
        left_node = None
    if right_node == "None":
        right_node = None
    tree[data] = Node(data, left_node, right_node)
# 7
# A B C
# B D E
# C F G
# D None None
# E None None
# F None None
# G None None

7
A B C
B D E
C F G
D None None
E None None
F None None
G None None

In [13]:

print('pre-order : ', end = ' ')
pre_order(tree['A'])
print()
print('in-order : ', end = ' ')
in_order(tree['A'])
print()
print('post-order : ', end = ' ')
post_order(tree['A'])

pre-order :  A B D E C F G 
in-order :  D B E A F C G 
post-order :  D E B F G C A 

3. Bellman Ford Algorithm (벨만 포드 알고리즘)¶

3-1. Bellman Ford Algorithm (벨만 포드 알고리즘)¶

• 최단 거리 알고리즘 중 하나로서 음의 간선이 포함된 그래프에서 사용됩니다.
  • 모든 간선의 비용이 양수일 때는 다익스트라 알고리즘을 사용하면 됩니다.
• 최단 경로 알고리즘
• 백준 문제

3-2. 음수 간선이 포함된 그래프의 문제¶

• 음의 간선이 포함되어 있더라도 최단 거리는 계산 가능합니다.
• 음수 간선의 순환 이 포함되어 있으면, 최단 거리가 음의 무한인 노드가 발생합니다.
• 간선에 따른 최단 경로 문제 분류
  • 모든 간선이 양수인 경우
  • 음수 간선이 있는 경우
    • 음수 간선 순환이 없는 경우
    • 음수 간선 순환이 있는 경우
• 벨만 포드 최단 경로 알고리즘 은 음의 간선이 포함된 상황에서도 사용가능 합니다.
  • 음수 간선의 순환을 감지합니다.
  • 시간 복잡도는 $O(VE)$ 입니다.
  • 다익스트라의 최적해를 포함합니다.

3-3. 벨만 포드 알고리즘의 동작 과정¶

• 동작 과정
  1. 출발 노드를 설정합니다.
  2. 최단 거리 테이블을 최기화합니다.
  3. 다음의 과정을 N-1번 반복합니다. 3-1. 전체 간선 E를 하나씩 확인합니다. 3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
• 만약 음수 간선 순환이 발생하는지 체크 하고 싶다면 3번의 과정을 한번 더 수행 합니다.
  • 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것입니다.

3-4. vs 다익스트라¶

• 다익스트라
  • N-1 번 확인할때 매번 방문하지 않은 노드 중에서 최단 거리가 가장짧은 노드를 선택하여, 그 노드로 부터 연결되어 있는 간선들을 확인합니다.
  • 음수 간선이 없다면 최적의 해를 찾을 수 있습니다.
• 벨만 포드 알고리즘
  • N-1 번 마다 모든 간선들을 확인합니다.
    • 다익스트라 알고리즘의 최적의 해를 항상 포함합니다.
  • 다익스트라 알고리즘에 비해 오래 걸리지만 음수 간선 순환을 탐지할 수 있습니다.

In [14]:

def bf(start):
    # 시작 노드에 대해서 초기화
    dist[start] = 0
    # 전체 n번의 라운드(round)를 반복
    for i in range(n):
        # 매 반복마다 "모든 간선"을 확인
        for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                # n 번째 라운드에서도 값이 갱신 된다면 음수 순환이 존재
                if i == n - 1:
                    return True
    return False

In [15]:

INF = int(1e9)

# 노드, 간선 의 개수
n, m = map(int, input().split())
edges = []
dist = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
    
# 3 4
# 1 2 4
# 1 3 3
# 2 3 -1
# 3 1 -2

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

In [16]:

negative_cycle = bf(1)

if negative_cycle:
    print('-1')
else:
    for i in range(2, n+1):
        if dist[i] == INF:
            print("-1")
        else:
            print(dist[i])

4
3

4. Binary Indexed Tree (Fenwick Tree)¶

4-1. Binary Indexed Tree (Fenwick Tree)¶

• 바이너리 인덱스 트리(binary indexed tree) 는 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결 해 줄 수 있는 자료구조 를 의미합니다.
  • 펜윅 트리 (fenwick tree) 라고도 합니다.
• 정수에 따른 2진수 표기 |정수|2진수 표기| |:---:|:---:| |7|00000000 00000000 00000000 00000111| |-7|11111111 11111111 11111111 11111001|
• 0이 아닌 마지막 비트를 찾는 방법
  • 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K & -K 를 계산하면 됩니다.
• 백준 문제

4-2. K & -K 계산 결과 표시 (-> 0이 아닌 마지막 비트)¶

정수	2진수 표기	K & -K
0	00000000 00000000 00000000 00000000	0
1	00000000 00000000 00000000 00000001	1
2	00000000 00000000 00000000 00000010	2
3	00000000 00000000 00000000 00000011	1
4	00000000 00000000 00000000 00000100	4
5	00000000 00000000 00000000 00000101	1
6	00000000 00000000 00000000 00000110	2
7	00000000 00000000 00000000 00000111	1
8	00000000 00000000 00000000 00001000	8

n = 8
for i in range(n+1):
    print(i, "의 마지막 비트: ",(i&-i))

4-3. 트리 구조 만들기¶

• 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수
  
• 특정 값을 변경할 때 : 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경 (예시 = 3rd)
  
• 1부터 N까지의 합(누적 합) 구하기 : 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합을 계산 (예시 = 11th)

In [9]:

# i번째 수까지의 누적합을 계산하는 함수
def prefix_sum(i):
    result = 0
    while i > 0:
        result += tree[i]
        # 0이 아닌 마지막 비트만큼 빼가면서 이동
        i -= (i & -i)
    return result

# i번째 수를 dif만큼 더하는 함수
def update(i, dif):
    while i <= n:
        tree[i] += dif
        i += (i & -i)
        
# start부터 end까지의 구간 합을 계산하는 함수
def interval_sum(start, end):
    return prefix_sum(end) - prefix_sum(start-1)

In [20]:

n, m, k = map(int, input().split())

arr = [0] * (n + 1)
tree = [0] * (n + 1)

for i in range(1, n + 1):
    x = int(input())
    arr[i] = x
    update(i, x)
    
for i in range(m + k):
    a, b, c = map(int, input().split())
    # update 연산인 경우
    if a == 1:
        update(b, c - arr[b]) # 바뀐 크기 (dif) 만큼 적용
    # interval_sum 연산인 경우
    else:
        print(interval_sum(b, c))
        
# 5 2 2
# 1
# 2
# 3
# 4
# 5
# 1 3 6
# 2 2 5
# 1 5 2
# 2 3 5

5 2 2
1
2
3
4
5
1 3 6
2 2 5
17
1 5 2
2 3 5
12

5. Lowest Common Ancestor Algorithm (최소 공통 조상)¶

5-1. Lowest Common Ancestor Algorithm (최소 공통 조상)¶

• 최소 공통 조상(LCA) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 입니다.
• 백준 문제 LCA - 기본
• 백준 문제 LCA2 - 심화

5-2. 최소 공통 조상(LCA) 알고리즘¶

• 최소 공통 조상(LCA) 알고리즘 동작과정
  1. 모든 노드에 대한 깊이(depth)를 계산합니다.
  2. 최소 공통 조상을 찾을 두 노드를 확인합니다. a. 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라갑니다.
     b. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라갑니다.
  3. 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복합니다.

5-3. 최소 공통 조상(LCA) 구현 1¶

• DFS를 이용해 모든 노드에 대하여 깊이(depth)를 계산할 수 있습니다.
  

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

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):
    # 먼저 깊이(depth)가 동일하도록
    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) # 루트 노드는 1번 노드
print(lca(a, b))

• 매 쿼리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우 $O(N)$의 시간 복잡도가 요구 됩니다.
  • 따라서 모든 쿼리를 처리할 때의 시간 복잡도는 $O(NM)$ 입니다.
• 백준 문제 LCA - 기본 은 가능하나
• 백준 문제 LCA2 - 심화 은 시간 초과 판정

5-4. 최소 공통 조상(LCA) 구현 2¶

• 각 노드가 거슬러 올라가는 속도를 빠르기 만드는 방법 에 대하여 고민
  • 만약 총 15칸 거슬러 올라가야 한다면?
    • 8칸 -> 4칸 -> 2칸 -> 1칸
• 2의 제곱 형태로 거슬러 올라가도록 하면 $O(logN)$ 의 시간 복잡도를 보장할 수 있습니다.
• 메모리를 조금 더 사용하여 각 노드에 대하여 $2^{i}$ 번째 부모에 대한 정보를 기록합니다.

• 다이나믹 프로그래밍(dynamic programming)을 이용해 시간 복잡도를 개선할 수 있습니다.
  • 세그먼트 트리를 이용하는 방법도 존재합니다.
• 매 쿼리마다 부모를 거슬러 올라가기 위해 $O(logN)$ 의 복잡도가 필요합니다.
  • 따라서 모든 쿼리를 처리할 때의 시간 복잡도는 $O(MlogN)$ 입니다.

In [27]:

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
    c[x] = True
    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) # 루트 노드는 1번 노드
    for i in range(1, LOG):
        for j in range(1, n + 1):
            parent[j][i] = parent[parent[j][i - 1]][i-1]

# A와 B의 최소 공통 조상을 찾는 함수 
def lca(a, b):
    # b가 더 깊도록 설정
    if d[a] > d[b]:
        a, b = b, a

    # 먼저 깊이(depth)가 동일하도록
    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]

In [28]:

import sys
sys.setrecursionlimit(int(1e5)) # 재귀 깊이 제한 설정
LOG = 21 # 2^20 = 1,000,000 # 데이터가 최대 백만개 들어온다고 가정하고 작성되었음

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

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

set_parent()
for i in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))
    
# 15
# 1 2
# 1 3
# 2 4
# 3 7
# 6 2
# 3 8
# 4 9
# 2 5
# 5 11
# 7 13
# 10 4
# 11 15
# 12 5
# 14 7
# 6
# 6 11
# 10 9
# 2 6
# 7 6
# 8 13
# 8 15

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
2
10 9
4
2 6
2
7 6
1
8 13
3
8 15
1