끄-적끄적🍋

Union-Find개념그래프에서 두 노드가 같은 그래프에 속하는지(연결되어 있는지)를 판별상호 배타적 집합(Disjoint Set)이라고도 함시간 복잡도대표 노드(루트) 찾기 find : $O( \alpha(N))$ → 실전에서 거의 $O(N)$집합 합치기 union : $O( \alpha(N))$ → 실전에서 거의 $O(N)$전체 코드def find(a): if parent[a] != a: parent[a] = find(parent[a]) return parent[a]def union(a,b): pa, pb = find(a), find(b) if a Union-Find 구성하는 함수들find : 대표 노드(root) 찾기def find(a, b): if parent[a] !=..

📍Recap Day: 이번주는 지금까지 진행했던 주제의 문제 중에서 못 푼 문제를 해결하고 공유!1️⃣ DP & DnC점화식이 필요한 문제는 DP 혹은 DnC?!?알고리즘 공부하고 계속 점화식을 보면 DP 혹은 DnC를 떠올렸는데,,단방향으로 흘러갈 때 분할 정복,작은 값을 구해 큰 값에 사용해야 할 때 DP를 흔히 사용한다고 생각 ↑ 이 말을 들으니,, 틀렸을지도 모른다는 생각이 들어따.. 그래서 GPT한테 물어봄DP와 DnC 유형을 구분하는 기준을 세우자면 점화식인가?!? 보다는 부분 문제가 서로 독립적인가!? 가 더 잘 맞는다고 함..DP는 부분 문제가 중복되어서 같은 연산을 반복적으로 해야하는 경우에 더 적합하고 DnC는 부분 문제가 독립적일 때 더 적합하다고 함DP(Top-Down) vs D..