22/04/24 RESTful API 복습, Union-Find 최적화 방법

220423 Today I learned!

---

• RESTful API 복습
• 백준 문제 풀이 (Union-find 최적화 방법 학습)

---

1. Fact

(1) RESTful API 복습

내일 치루는 시험 준비

• 수, 목에 진행했던 workshop과 금요일의 관통프로젝트를 혼자 구현했다.
  • 1:N, M:N의 관계형 DB를 전달하는 API
  • 클래스 재정의를 통한 fields override
• 정리본

(2) 백준 문제 풀이

• 1717 집합의 표현
• 문제풀이
• Uniton-Find 최적화에 대해 학습했다.

2. Feeling

내일 치루는 RESTful API 시험 준비를 했다. 구현위주의 시험이기 때문에 혼자서 코드를 작성하는 것을 가장 중점으로 진행했다. VS코드의 자동완성기능 넘나 편한 것..

백준 문제의 경우, 시간초과가 연속으로 8번 정도 났다..😭😭 그래서 결국 구글링을 통해 최적화를 하는 방법을 찾아보았다.

그런데!!!!!!

import sys
input = sys.stdin.readline`

최적화고 뭐고 위의 코드를 통해 입력 시간을 줄여야 하는 문제였다. 그래도 Union-Find최적화에 대해 학습할 수 있는 경험이여서 좋았다.

3. Finding

Union-find 최적화 방법

시간초과가 해결되지 않아서, 최적화하는 방법을 찾아보았다. 참고하면 좋은 글 1 참고하면 좋은 글 2

최적화를 해야 하는 이유

트리 구조가 연결리스트의 형태인경우, 원소의 개수가 N일때 트리의 높이가 N-1이므로 시간복잡도가 O(N)이다. 이 문제에서는 N이 최대 1,000,000이기 때문에, 이를 고려하고 코드를 작성해야 한다.

Find 연산 최적화

경로 압축(Path Compression)

# 경로 압축을 하지 않은 코드 
# 단순하게,root만 찾기 때문에 트리의 높을 수록 시간복잡도가 높아진다. 
def find_set(x):
    while set_root[x] != x:
        x = set_root[x]
    return x

# 경로 압축을 한 코드
# root를 찾으면서 만난 모든 값의 부모를 root로 바꾼다. 
# 추후, find 연산을 다시 수행할 때, 중복되는 연산을 줄여준다.(바로 root를 찾을 수 있게 해준다.)
def find_set(x):
    if set_root[x] != x:
        set_root[x] = find_set(set_root[x])
    return set_root[x]

Union 연산 최적화

union-by-rank(union-by-height)

# union-by-rank을 하지 않은 코드
def union(a, b):
    root_a = find_set(a)
    root_b = find_set(b)
    if root_a != root_b:
        set_root[root_b] = root_a

# union-by-rank을 한 코드
# 합집합 연산을 할 때, 높이가 더 낮은 트리를 더 높은 트리 밑에 넣는다.
# 이는 트리가 균형잡힌 형태가 되도록 강제한다. (트리의 높이가 같을 때만 트리의 높이가 증가한다.)

rank = [0]*(N+1) # 각각의 집합은 rank를 갖는다. (초기값은 0) => tree의 높이를 나타낸다. 

def union(a, b):
    root_a = find_set(a)
    root_b = find_set(b)
    if root_a != root_b:
        if rank[root_a] < rank[root_b]: 
            set_root[root_a] = root_b   # a_root의 root를 root_b로 변경한다.
        else:
            set_root[root_b] = root_a   # b_root의 root를 root_a로 변경한다.
            
        # 만약 높이가 같다면 위에서 합친 후 높이를 +1한다.
        if rank[root_a] == rank[root_b]: 
            rank[root_a] += 1

4. Future Action & Feedback

Future Action	진행 상황	Feedback
DOM을 깨우치다	pause 🤦‍♀️	잠시 중단!
강의에서 학습한 flex-website 혼자 제작하기	in progress 🚀	현재 Section2까지 진행한 상태이다. 오는 주에 Section3를 할 예정이다.
1일 1알고! 🔥	in progress 🚀