김재욱의 이모저모

최소신장트리 (Minimum Spanning Tree)란 무엇인가 최소신장트리의 특징은 크게 3가지가 있다. 그래프에서 모든 정점을 연결해야 한다. 연결된 트리가 사이클을 포함하고 있으면 안 된다. 그러한 트리들 중에서 에지의 가중치 합이 최소가 되는 트리여야 한다. 이러한 최소신장트리는 그래프에서 노드를 연결하는 에지의 부분 집합 중에서 최소한의 비용으로 모든 노드를 연결하는 트리를 찾는 문제에 나온다. 이때 사용하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 존재한다. 프림 알고리즘 (Prim's algorithm) 프림 알고리즘은 최소신장트리를 구하는 알고리즘 중 하나로 그래프에서 노드를 중점으로 탐색하여 최소신장트리를 구합니다. 프림 알고리즘의 순서는 아래와 같습니다. 시작 노드를 선택합니..

문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다. 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다. 출력 문제의 조건에 맞는 A,..

문제 한 변의 길이가 같은 두 개의 정사각형이 주어집니다. 이 정사각형들은 가장 왼쪽 위의 점의 좌표 (a, b)와 (c, d), 그리고 한 변의 길이 r로 표현할 수 있으며, 정사각형의 각 변들은 X축 또는 Y축에 평행합니다. 이 정사각형들은 겹칠 수도 있고, 겹치지 않을 수도 있습니다. 두 정사각형 왼쪽 위 좌표 (a, b)와 (c, d), 두 정사각형의 변의 길이인 r이 매개변수로 주어질 때, 이 두 정사각형이 차지하는 면적을 출력하는 프로그램을 작성하시오. 제한사항 0 ≤ a ≤ 1,000,000 0 ≤ b ≤ 1,000,000 0 ≤ c ≤ 1,000,000 0 ≤ d ≤ 1,000,000 1 ≤ r ≤ 500,000 입출력 예 a b c d r result 1 2 1 2 3 9 1 2 4 2 ..

문제 우리나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 ..

문제 N x M 크기 벌집은 육각형이 가로 N칸이 한 줄로 이어져 있고, 이 줄이 모두 M 줄 있는 형태이다. 예를 들어, 아래 그림은 4 x 3 크기 벌집이다. 벌집의 각 칸마다 (x, y) 형태로 좌표값이 주어지는데, 이는 위에서 x번째 줄, 왼쪽으로부터 y번째 칸에 있다는 뜻이다. 가장 왼쪽 위 칸은 (1, 1)이고, 가장 오른쪽 아래의 칸은 (M, N)이다. 각 칸마다 꿀이 들어있고, 벌이 해당하는 칸을 방문하면 이 꿀을 먹을 수 있다. 처음 벌은 (1, 1)에 있다. 매번 벌은 자신이 있는 육각형의 바로 오른쪽에 인접한 칸, 또는 대각선으로 오른쪽 아래에 인접한 칸으로 이동할 수 있다. 예를 들면 (2, 1)에 있는 벌은 (2, 2) 또는 (3, 2)로 이동할 수 있다. 벌이 (M, N)에 도착..