문제 링크 : https://www.acmicpc.net/problem/1991 이 문제는 이진트리를 활용해서 푸는 문제이다.문제에 들어가기 전 이진 트리에 대해 알아보자 이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.편향 이진 트리는 노드들이 한쪽으로 편향돼 생성된 이진 트리이고,포화 이진 트리는 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리,완전 이진 트리는 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은왼쪽부터 채워진 트리이다. 보통 이렇게 트리를 배열로 표현하는 것이 일반적인데 이렇게 했을 때편리한 점은 아래 정리한 표와 같이 부모 노드, 자식 노드들의 인덱스값을 편하게 계산할 수 있다.이동 목표 노드인덱스 연산제약 조건(N = 노드 개..

문제 링크 : https://www.acmicpc.net/problem/17472 문제 설명이 아주 자세하게 나와있다.일반적인 하나의 알고리즘을 이용하는 게 아닌 여러 알고리즘을 사용하여 해결할 수 있는 문제이다.우선 문제에서 구하고자 하는것을 보면 결국 모든 섬이 하나의 집합으로 만들어져야 하는데이때 최단거리를 구하는 문제이다. 얼핏 봤을 때 최소 신장 트리(MST) 알고리즘을 사용하면 될 것처럼 보인다.일반적인 MST알고리즘 문제는 간선과 정점을 직접 제공하는경우가 많다.하지만 이 문제에서는 아무것도 주어져있지 않다. 문제에서 주어진 그림을 자세히 보면 힌트를 주듯 각 섬을 하나의 번호로 묶은 것을 볼 수 있다.따라서 문제를 해결하는 과정은 아래와 같다.1. 섬을 정점이라고 생각하고 맞닿아 있는 점끼..

문제 링크 : https://www.acmicpc.net/problem/1197 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘 구현 문제이다.MST 알고리즘은 모든 노드들을 연결했을 때 가장 적은 비용의 간선 집합을 찾는 알고리즘이다.간단한 MST에 대한 설명은 아래와 같다.  위와 같은 그래프가 있다고 가정한다.정점 사이에는 가중치가 있는 간선이 있다.MST 알고리즘은 해당 그래프의 모든 정점들을 잇는 가장 최소비용의 간선 집합을 찾는 알고리즘이다.여기서 중요한 것은 그래프를 사이클이 생기면 안 된다는 것이다.사이클이 존재하면 가중치의 합이 최소가 될 수 없기 때문이다.또한 정점의 개수가 V라고 하면 정점을 최소 신장 트리를 구성하는 간선의 개수는 무조건 V-1개..

문제 링크 : https://www.acmicpc.net/problem/1389 이 문제는 전형적인 플로이드 워셜 알고리즘을 이용하여 해결할 수 있는 문제이다. 예제 입력을 그래프로 표현하면 위와 같다. 여기서 단방향이 아니라는 것에 주의해서거리 배열을 초기화한다. 거리배열을 초기화하면 인접 정점끼리의 관계를 표현할 수 있다.여기서 무한대는 문제의 조건을 보고 직접 적당히 큰 값을 넣거나,아니면 Interger.MAX_VALUE와 같이 int 범위에서 가장 큰 값을 넣어주면 된다.다만 이럴 경우에는 연산의 과정에서 int의 범위를 넘어 오버플로우가 발생할 수 있기 때문에long 타입으로 캐스팅한 후에 연산을 해줘야 한다. 거리배열을 초기화한 후에는 플로이드 워셜 알고리즘으로 각 정점사이의 최단거리를 구해..