보통의 개발자

이 글을 보기 전에 다음 문제를 한 번 풀어보는걸 추천한다(포스팅을 하게 된 이유)https://www.acmicpc.net/problem/1197직접 문제를 풀어 보면, 메모리 제한이 128MB이기 때문에 생각보다 까다로울 수 있다. 정점의 개수도 10,000개라서 섣불리 인접 행렬을 사용했다가는 입구부터 막힐 수 있다. 특히나 이 글에 대한 내용을 잘 모르면, 사이클을 탐색하는 과정에서 DFS로 접근하다가 매모리 초과를 수 없이 겪을 수 있다(경험담).서로소 집합 자료 구조(Union-Find)최소 스패닝 트리를 알아보기 전에 먼저 서로소 집합 자료 구조에 대해 알아야 한다. 서로소 집합 자료 구조란 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조 우리가 알고 있는 수학..

자료 구조란? 데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것. 예를 들어 한정된 크기의 책장이 있고, 넣어야 될 책들이 있다고 하자. 가장 많은 책을 넣는 방법은 아무 규칙 없이 있는 책을 모두 꽂아 넣는 것이다. 그럼 당장은 이 책장의 공간을 가장 효율적으로 사용한 것 같지만, 이후 책을 찾을 때 큰 문제가 발생한다. 아무 규칙 없이 책을 꽂아 넣었기 때문에 찾을 때도 규칙 없이 모든 범위를 찾아야 한다. 따라서 이번에는 책의 제목을 오름차순 형태로 꽂아 넣는다는 규칙을 세워 넣어 보면, 이후에 책의 제목을 이용해 어디에 꽂혀있는지 찾기가 훨씬 수월해질 것이다. 또한 책의 모든 공간을 모두 사용할 수 있..