크루스칼

알고리즘 문제) BOJ 17251. 힘 겨루기 링크 : https://www.acmicpc.net/problem/17251문제 요약N명의 선수가 일렬로 있고, 1번부터 N-1까지 수가 적힌 공을 무작위로 뽑아 기준선으로 정하려함예를 들어 3번 공을 뽑으면 3번과 4번 사이가 기준성기준선 왼쪽은 R팀, 오른쪽은 B팀이때, 각 팀에서 가장 센 사람이 나오고 힘을 겨룬다.이때 힘이 더 센 사람이 이긴다.이길 확률이 높은 팀을 찾아라!시간 제한1초입력사람의 수 N이 주어진다.N은 1,000,000보다 작거나 같은 짝수1번 사람부터 N번 사람까지의 힘을 나타내는 정수각 사람의 힘은 10,000보다 작거나 같은 자연수출력이길 확률이 높은 팀을 출력 R 또는 B만약 같다면 X 출력접근법prefix배열과 suffix ..

알고리즘 문제) BOJ 1414. 불우이웃돕기 1414번: 불우이웃돕기첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선www.acmicpc.net문제 요약N개의 방에 각각 컴퓨터 한 개씩 존재컴퓨터는 랜선으로 연결되어 있음이때, N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.그리고 나머지 랜선은 기부를 하려고 할 때, 기부할 수 있는 랜선의 길이의 최댓값 출력시간 제한2초입력컴퓨터 개수 N50보다 작거나 같은 자연수랜선의 길이가 주어짐i번째 줄의 j번째 문자가 0인 경우 컴퓨터 i와 j를 연결하는 랜선이 없음을 의미알파벳은 랜선의 길이a~z : 1~26A~Z..

알고리즘 문제) BOJ 14950. 정복자 14950번: 정복자서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재www.acmicpc.net문제 요약N개의 도시(1~N)와 M개의 도로(양방향)로 구성모든 도시 쌍에는 도로로 이어져 있음각 도로는 비용이 존재모든 도시를 정복하려고 함처음 점거 중인 도시는 1번 도시만약 B도시를 점거하고 싶다면, B와 연결된 도시 중 최소 하나 정복해야 함만약 A선택하면 B정복과정에서 A와 B를 연결하는 도로 비용도 소모한 번 도시가 정복 되면 모든 도로의 비용이 t만큼 증가이미 정복한 도시는 또 정복 X모든 도시 정복하는 데 드는 최소..

알고리즘 문제) BOJ 7569. 토마토 링크 : https://www.acmicpc.net/problem/7569문제 요약M*N크기의 격자가 H개만큼 쌓여 있음익은 토마토의 상, 하, 좌, 우, 앞, 뒤에있는 방향의 토마토는 영향을 받음이때 모든 토마토들이 며칠이 지나야 다 익는지 최소 일수 구하기시간 제한1초입력첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 HM은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸이러한 N개의 줄이 H번..