문제 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 풀이 부등호를 만족하는 최소와 최대 정수를 백트래킹으로 찾는 문제이다. 입력받은 부등호에 따라 올바른 숫자를 선택하고 재귀적으로 탐색을 진행한다. 가장 먼저 완성된 답이 최소 정수, 가장 나중에 완성된 답이 최대 정수가 되는 것으로 각각 출력해주면 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val num = br.readLine(..

문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 주어진 도로와 도시 정보에서 모든 도시간의 거리가 1이라는 점을 이용해 너비 우선 탐색(BFS)으로 해결할 수 있다. 시작 도시로부터 BFS를 수행하며 거리를 계산하고 거리 배열에 저장해준다. 여기서 모든 도시간의 거리가 1이기 때문에 도시에 처음 도착했을 때의 거리가 최단 거리일 것이다. 탐색이 끝난 후 찾으려는 거리에 도시가 있다면 도시를 출력해주고, 없다면 -1을 출력한다. ..

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 이 문제의 풀이 과정과 사용한 알고리즘은 다음과 같다. 1. 섬에 고유 번호 부여 (DFS): 입력받은 지도를 DFS나 BFS를 이용하여 각 섬에 번호를 부여해준다. 입력에서 1이 섬이기 때문에 첫번째 섬부터 2번으로 부여해주었다. 2. 각 섬을 연결할 수 있는 방법 구하기 (BFS): 각 섬을 연결하는 가능한 모든 다리를 찾아준다. 길이가 1보다 큰 다리들을 거리에 따라 오름차순으로 정렬될 수 있게 우선 순위 큐에 저장한다. 3...

문제 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 크루스칼 알고리즘을 사용하였다. 문제는 최대로 절약할 수 있는 비용을 찾는 것이므로, 크루스칼 알고리즘으로 찾음 최소 스패닝 트리(MST)의 비용을 초기 비용에서 빼준 값을 출력하면 된다. 기본적인 유니온 파인드로는 시간 초과 문제가 발생하여 경로 압축을 적용한 유니온 파인드 구현이 필요하다. 경로압축은 파인드 함수에서 부모를 찾아가는 중간에 거치는 모든 노드들..

문제 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 크루스칼 알고리즘을 사용하였다. 문제는 각 정점의 위치가 주어지기 때문에, 정점들 간의 거리를 계산하여 간선의 정보를 리스트에 저장해준다. 그리고 나서 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 구하고 결과를 출력해준다. 코드 import java.util.* import kotlin.math.* // 별의 좌표를 저장..