⏰ 시간복잡도

• Python에서 1초에 약 2천만 연산 가능
• 시간복잡도 계산할 때 적용해볼 것

🔎 완전탐색

• input의 개수가 현저히 적을 때 사용 가능

🥞 스택

• 문자열에서 문자열을 출력해야할 때 그리고 그 조건이 입력 문자열을 활용하는 문제에서 사용
• 투스택 사용도 고려해볼 것

📕 해시

• Python에서는 Dictionary로 사용
• 시간복잡도를 완전히 줄여야할 때 떠올려볼 수 있음
• 가끔 Set으로 풀면 더 간단하게 코드 작성 가능

Union Find

• 원소들의 연결 여부를 확인할 때 사용한다.

각 부모 노드는 자기 자신을 자식 노드로 삼고 있다.

이 때 (1-4) (2-4) 노드가 연결된다고 가정하자.
작은 원소가 부모 노드라는 규칙이다.
그러면 4번 노드의 부모 노드는 1번 노드가 된다.

마찬가지로 2번 노드와 4번 노드도 연결되는데
이 때 이미 4번 노드가 1번 노드와 연결되어있음을 주의하라

작은 원소가 부모 노드라는 규칙에 의거해 재귀적으로 2번 노드의 부모 노드도
1번 노드가 된다.

{1,2,4} {3}

따라서 위와 같은 집합들이 생성된다.

Example Code

# Union-Find Example Code

# Find real parent node
def find(x):
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]

# Link y --> x
def union(x,y):
    x = find(x)
    y = find(y)
    parent[y] = x

# Link 1-4 , 2-4
parent = []

# [0,1,2,3,4]
for i in range(5):
    parent.append(i)

union(1,4)
union(4,2)

for i in range(1,len(parent)):
    print(find(i),end=" ")

🧙🏻‍♀️ Skill

list = [(1,4),(2,5),(19,3),(5,7)]

max(list, key=lambda x:x[0])
max(list, key=lambda x:x[1])

출력:
(19,3)
(5,7)

• key값을 기준으로 리스트 내 튜플의 max 값을 뽑아냄
• min도 동일한 방법으로 사용