알고리즘

벽 부수기 게임

요새 알고리즘 실력이 정체가 된 것 같다. 나름 꾸준히 공부한다고 생각했는데 절대적인 양이 부족한건지 최근 백준 문제들이나 학교 과제들을 풀려고 하면 숨이 막히는 기분이 든다. 조고리즘 지난 2문제는 80점으로 대충 제출하고 마무리했다. 둘 다 branch and bound라는 백트래킹의 업그레이드 된 알고리즘이었는데, 시간을 줄이기 위한 bound를 찾기도 어려웠고, 찾는다 해도 세부적인 재귀 함수의 구현에서 벽을 느꼈다. 그래서 시간을 투자해도 내가 풀 수 있을거란 자신이 조금도 들지 않아서 둘 다 적당히 만들어서 제출했다. 2문제 연속 벽을 느끼는 문제였고, 최근 푸는 boj문제들도 시간이 너무 오래 걸리거나 스스로 풀이를 생각해 내지 못한 경우가 종종 있었다. 그래서 벽을 깨보려고 마음먹었다. 오..

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..