이전 포스팅에 이어 이번에는 MST 알고리즘을 구현하는 방식 중 하나인 프림 알고리즘에 대해 알아보려 합니다.우선 MST에 대해 다시 한번 짚고 넘어가겠습니다. 📑 MSTMST를 다시한번 간단하게 설명하면 "최소 비용으로 모든 정점을 연결한 트리 구조"입니다.MST도 트리이기 때문에, 트리 구조 특성 상 사이클이 발생하면 안되는데요.이유는 트리는 정점 간 유일한 경로, 최소 연결성이라는 특성이 있기 때문입니다. 이러한 MST를 구하는 방식 중 하나인 크루스칼 알고리즘에 대해서는 아래 포스팅을 참고해주세요.[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm) [JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST ..

최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 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 노드의 공통되..