최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST 알고리즘에 대해서 정리해볼까 합니다.정리하려는 주된 내용은 아래와 같습니다.❓ MST가 무엇인지, 크루스칼 알고리즘의 구현 및 동작 방식 📑 MST란?MST는 Minimum Spanning Tree의 약자로 최소 신장 트리를 찾기 위한 알고리즘입니다.또한 Spanning Tree(신장 트리)는 간단하게 설명하면 모든 정점을 포함하면서 사이클이 없는 연결 그래프를 의미합니다.더보기왜 사이클이 없어야할까❓ (25.06.21 추가)처음에는 모든 정점이 연결만 되면 된다고 생각했습니다. (이 과정에서 사이클이 생기든 말든지요.)그러나 MST 또한 트리이며, 트리 특성을 생각해보면 사이클이 없어야 합니다.트리에서 한 정점에서 다른 정점으로 가..

백준에서 시뮬레이션 문제를 풀다가 한참을 디버깅하면서 삽질했던 과정을 기록하고자 합니다.. 결론부터 말씀드리자면, double 자료형의 부동소수점 오차로 인한 문제였습니다.추가로 짝수/홀수 구분을 (2&1)로 해야하는데 (2^1)로 하고서는 "왜맞틀"했던 저를 발견할 수 있었습니다..(반성하고 자바의 정석 다시 펼칠게요) 🔗 문제https://www.acmicpc.net/problem/20057문제는 삼성 기출로 유명한 마법사 상어 시리즈입니다. 📝 풀이간단하게 풀이를 설명하자면 달팽이 회전 로직을 구현 후 각 방향에 따른 '위치 및 비율'을 인덱싱하여 구현했습니다.2차원 격자 문제를 많이 풀어봤다면 쉽게 떠올리고 풀 수 있을거라 생각합니다. 조심해야하는 부분은 오른쪽부터 시작하는 달팽이 회전이 아니..

문제https://www.acmicpc.net/problem/3584 풀이해시 + 그래프 탐색접근법“공통 조상” 이라는 키워드만 보고서는 유니온 파인드를 생각했습니다.그러나 “가장 가까운 공통 조상(Nearest Common Ancestor)”을 구하는 문제로써 Union-Find로 구할 시 루트노드가 나오기에 다른 방식으로 접근했습니다. 두 정점의 부모 노드만 탐색하면 되었기에 일반적인 그래프 탐색을 통해서 접근했습니다. (시간복잡도↓)트리 자료구조로는 인접리스트를 활용했고, 자식 노드가 아닌 부모 노드를 탐색해야 했기에 부모를 기준으로 자식노드를 담는게 아닌 자식 노드를 기준으로 부모 노드를 담았습니다.list.get(부모).add(자식) → list.get(자식).add(부모)a와 b 노드의 공통되..

Union-Find?분리 집합이라고도 불리는 유니온 파인드는 그래프 형태의 자료구조에서 정점들의 연결 정보를 알고 싶을 때 사용하는 알고리즘입니다.분리 집합이라고 불리는 이유는 서로 연결된 정점들을 각각의 집합으로 만들기 때문입니다. DFS(BFS) VS Union Find그래프 형태의 자료에서 연결 정보를 알고 싶을 때 DFS, BFS 탐색을 통해서도 알 수 있습니다.그러나 서로 다른 모든 정점의 연결정보를 구하려면 시간이 오래 걸릴 수 밖에 없습니다.10만개의 정점이 있고, 모든 정점이 서로 연결되있을수도 있다면 두 정점의 연결관계를 탐색하는데 최대 10만번의 탐색이 이루어질 수 있기 때문입니다.또한 이러한 연결관계 탐색이 N번 필요하다면 O(N^2)의 시간이 필요합니다. Union Find를 사용하..