새벽 기상을 꿈꾸는 루민

이번 포스팅에서는 최소 스패닝 트리 문제를 풀어보겠습니다. 1. 문제 2. 예제 3. 문제 풀이 이번 문제는 최소 스패닝 트리를 구하면 되는 문제이다. 위의 그림처럼 가중치 C가 최소인 값으로 구성된 트리를 구하면 되는데 이 또한 기존에 풀었던 union-find 알고리즘을 그대로 사용하면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; import jav..

오늘 풀어볼 문제는 게임 개발 문제입니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제도 동일하게 위상정렬을 이용하는 문제입니다. 이번 문제에서는 크게 봐야할 부분은 건물을 지을 때 건물 번호가 존재한다면 해당 건물이 지어진 시간까지 계산을 해야 한다는 것입니다. 즉 i번째의 건물을 짓는데 걸리는 시간을 구한다면 가장 최대의 시간(MAX)를 구해주면 시간적인 부분에서 문제 없이 건물을 지을 수 있습니다. 4. 코드 package backjoon; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io..

오늘 포스팅할 문제는 줄세우기 문제입니다. 1. 문제 내용 2. 입출력 3. 문제 풀이 우선 이번 문제는 그래프를 이용해서 푸는 문제이며 위상정렬을 이용한 문제이다. 위상정렬이라고 한다면 순서가 정해진 정렬이지만 싸이클이 없는 즉 단방향(사이클 발생 X) 그래프를 말한다. 문제를 좀 더 확인해보자. N명의 학생들의 키를 순서대로 줄을 세울려고 하는데 두 학생의 키를 비교하여 정렬을 한다고 가정한다. 첫번째 예제를 입력했을 때 줄을 세워진 방법이다. 1번의 친구와 3번의 친구를 비교하고 2번의 친구와 3번의 친구를 비교한다고 가정하면 3번의 친구는 1번과 2번의 친구를 비교한 상태 즉 2명과 비교했고 1번과 2번은 3번과 비교한 것을 제외하고 비교 대상이 없다. 즉 1과 2와 진입차수가 없다는 것을 확인할..

이번 포스팅은 2년 전에 C++로 작성해서 문풀 했던 기억이 나는데 파이썬으로 풀면 좀 더 간편하게 풀 수 있을 것이라고 판단해서 파이썬으로 풀어봤다. 문제는 위와 같은데 말 그대로 나이순으로 정렬한다. 그렇지만 나이가 동일한 경우에는 알파벳 순서대로! 이 경우에는 파이썬에서 sort를 이용한다면 쉽게 가능하다는 판단이 나왔다. C++로 문풀한 건 2년 전이지만 파이썬으로 쉽게 만들었지만 문제가 틀렸다고 나왔다. 그래서 무슨 문제인지 처음에 몰랐는데....... 파이썬에서 변수를 설정할 때 정수형을 구분 안해서 틀렸다.... 즉 Number = int(input().split()) 으로 변수를 입력받거나 아니면 변수를 int(number)로 변환해야 했는데... 그렇게 하지 않아서 문제가 틀렸다. # c..