https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리 설명 DFS / BFS를 사용해 각 섬을 그룹화 해줍니다. 그리고 각 섬의 모든 점들을 저장해 놨다가, 상하좌우로 방향으로 다리를 만들 수 있는지 확인합니다. 상하좌우 방향으로 현재의 섬을 만난다면 다리를 만들 수 없으며, 다른 섬을 만나..
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 최소 스패닝 트리 설명 최소 스패닝 트리의 입문 문제입니다. 응용문제가 아니기에, 연습용으로 제격인 문제네요. 최소 스패닝 트리를 모르신다면 아래 포스팅을 참고해주세요. https://uknowblog.tistory.com/294 [알고리즘] 최소 스패닝 트리 (MST, Minimum Spanning Tree..
https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프이론, 최소 스패닝 트리, 문자열 설명 몇 가지 기믹이 들어간 최소 스패닝 트리 문제입니다. 해당 문제는 랜선을 가장 많이 기부할 수 있는 길이를 찾는 문제입니다. 따라서, 다솜이가 쓸 랜선은 냅두고, 남은 랜선을 줘야 하는데요. 컴퓨터는 연결된 다른 컴퓨터를 타고 들어가 네트워크를 사용할 수 있으므로, 전체 랜선의 길이에서 최소 스패닝 트리의 가중치의 합을..
https://www.acmicpc.net/problem/15439 15439번: 베라의 패션 베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다. 상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까? www.acmicpc.net 난이도 : 브론즈 4 태그 : 수학, 구현, 조합론 설명 단순히 n * (n-1)로 구할 수 있을 것 같습니다. 소스코드 fun main() = println(readln().toInt().let { it * (it - 1) }) 후기 최근 숏코딩에 맛들려 브론즈 문제들의 경우 요상한 코드를 쏟아내고 있습니다. 현업에서 이러면 짤릴 것 같으니, 백준에서라도 해봐야겠습니다.
https://www.acmicpc.net/problem/5565 5565번: 영수증 첫째 줄에 10권의 총 가격이 주어진다. 둘째 줄부터 9개 줄에는 가격을 읽을 수 있는 책 9권의 가격이 주어진다. 책의 가격은 10,000이하인 양의 정수이다. www.acmicpc.net 난이도 : 브론즈 3 태그 : 수학, 구현, 사칙연산 설명 책 한 권의 가격만 주어지지 않습니다. 즉, 책의 총 가격 - 나머지 9개 가격을 하면 나머지 한 권의 책 가격을 구할 수 있습니다. 소스코드 fun main() = println(readln().toInt() - Array(9) { readln().toInt() }.sum()) 후기 가끔 바쁘지만 스트릭이 깨지지 않게 하려고 브론즈 문제들을 풀곤 하는데, 숏코딩에 맛들려 ..
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 자료 구조, 그래프 이론, 데이크스트라, 우선순위 큐 설명 다익스트라가 최단 경로를 찾는 알고리즘이라면, 이번엔 이 다익스트라를 이용하여 K 번째 최단 경로를 찾는 문제입니다. 해당 문제 같은 경우는 우선순위 큐를 활용할 수 있습니다. 우선순위 큐를 내림차순 정렬로 지정하고, 각 우선순위 큐의 크기가 K개를 ..
https://www.acmicpc.net/problem/15792 15792번: A/B - 2 첫째 줄에 A와 B가 주어진다. (0 < A, B ≤ 10,000) www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 구현, 사칙연산, 임의 정밀도 / 큰 수 연산 설명 A B 시리즈 마지막. A / B - 2 입니다. 해당 문제같은 경우는 조금 까다로웠는데요. BigDecimal을 쓰려니까 런타임 에러가 발생하는 바람에, 별 수 없이 직접 구현하였습니다. 소스코드 fun main() = with(System.`in`.bufferedReader()) { val nums = readLine().split(" ").map { it.toInt() }.toTypedArray() val sb = Str..
https://www.acmicpc.net/problem/15740 15740번: A+B - 9 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 난이도 : 브론즈 5 태그 : 임의 정밀도 / 큰 수 연산, 수학, 사칙연산 설명 이번 문제는 큰 수를 연산해야 하는 만큼, BigDecimal이 효과적일 것 같네요. https://uknowblog.tistory.com/120 [Kotlin] BigDecimal을 사용하여 매우 큰 수, 소숫점 처리하기 fun main() { val n1 = 90.15f val n2 = 30.05f println(n1 / n2) } Java와 Kotlin으로 개발하는 개발자들은 소숫점을 다룰 때 골칫덩어리인 부분이 하나 ..
https://www.acmicpc.net/problem/11021 11021번: A+B - 7 각 테스트 케이스마다 "Case #x: "를 출력한 다음, A+B를 출력한다. 테스트 케이스 번호는 1부터 시작한다. www.acmicpc.net 난이도 : 브론즈 5 태그 : 수학, 구현, 사칙연산 설명 이번엔 앞에 Case와 index를 불여 출력하는 문제네요. 소스코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int i; int a , b; for(i = 0; i < T; i++) { a..
https://www.acmicpc.net/problem/10953 10953번: A+B - 6 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 난이도 : 브론즈 3 태그 : 수학, 사칙연산, 파싱, 문자열 설명 새 언어를 배울 때 마다 한 번씩은 풀었던 A B 시리즈. C, Java, Python에 이어 이번엔 코틀린입니다. 문자열 처리가 들어가서 브론즈 3으로 난이도가 책정되었네요. 소스코드 fun main() { val T = readLine()!!.toInt() repeat(T) { val nm = readLine()!!.split(",") println(nm[0].toInt() + nm[1].toInt()) } }