새벽 기상을 꿈꾸는 루민

이번 포스팅에서는 도시 분할 계획 문제를 풀어보겠습니다. 1. 문제 2. 입출력 및 예제 3. 문제 풀이 이번 문제는 네트워크 연결(1922번)문제와 유사하게 접근하면 쉽게 풀 수 있습니다. 자세한 1922번 문제 풀이는 아래 링크로 남겨보겠습니다. [백준] 1922번 네트워크 연결 문제 풀기(Java) - 세무민의 코딩일기 이번 포스팅은 알고리즘 문제 풀이 포스팅입니다. 이번 문제는 네트워크 연결이라는 문제입니다. 1. 문제 설명 2. 입출력 예제 3. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결 sg-moomin.tistory.com 문제 풀이의 결론을 말하자면 도시를 2개로 분할시키면 됩니다. 유지비의 합을 최소로 할 수 있도록 하되 도시를 2개로 분할하려면 방법은 한개의 도시로 ..

이번 포스팅은 알고리즘 문제 풀이 포스팅입니다. 이번 문제는 네트워크 연결이라는 문제입니다. 1. 문제 설명 2. 입출력 예제 3. 문제 풀이 위의 그림을 보면 모든 컴퓨터가 최소 비용으로 연결되기 위한 방법은 위와 같을 것이다. 이번 문제에서 가장 중요한 포인트는 모든 컴퓨터를 연결하는데 필요하는 최소비용입니다. 여기서 알 수 있는 건 Kruskal-MST를 이용하여 문제를 풀 수 있다는 것입니다. Kruskal-MST는 최소 비용 신장 트리를 만든되 사이클이 생성되면 안되며 최소 비용이여 하는 것입니다. 따라서 Kruskal-Mst를 이용하면 문제를 풀 수 있습니다. package backjoon_20210920; import java.io.BufferedReader; import java.io.Bu..

오늘 풀어볼 문제는 게임 개발 문제입니다. 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..