PinguiOS

문제 링크 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로..

문제 링크 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B,..

안녕하세요 Ick입니다. 오늘은 여러 정렬 알고리즘 중 힙 정렬에 대해 공부했고 그에 대한 내용을 정리해볼까 합니다! 힙 정렬 (Heap Sort) 우선 정렬 알고리즘에는 버블 정렬, 병합 정렬, 퀵 정렬 등 여러 방법이 있는데요, 힙 정렬은 그중 시간 복잡도 O(N*logN)의 성능을 보이는 정렬 알고리즘입니다! 이러한 힙 정렬을 이해하기 위해선 힙(Heap)이라는 개념을 이해하셔야 합니다. 가장 중요한 것은 완전이진트리구조를 갖는다는 것입니다. 힙에는 최대 힙, 최소 힙이 있는데 최대 힙은 부모 노드가 자식 노드보다 값이 큰 힙을 말하며, 최소힙은 부모 노드가 자식 노드보다 값이 작은 힙을 말합니다. 그림으로 힙을 살펴보면 위와 같습니다. 최대 힙같은 경우엔 부모 노드가 자식 노드보다 커야 하므로 자..