코틀린으로 백준 풀기 1일 1코딩테스트를 한 지도 500일이 넘었네요. 아직 보잘 것 없는 실력이긴 하나, 그동안 백준을 풀며 얻은 팁들을 끄적여볼까 합니다. main() 함수의 매개변수는 생략 가능 fun main(args: Array) { } // main 함수 매개 변수는 생략 가능 fun main() { } 자바를 주로 써왔기에 public static void main(String[] args)과 같이 main 함수에 매개변수를 넣는게 익숙했고, 코틀린에서 클래스를 생성했을 때, main() 함수 내 args: Array이라는 매개변수를 자동으로 만들어주길래, 당연히 넣어줘야 하는 줄 알았으나... 사실 생략이 가능합니다. readln(), readLine()으로 입력받기 fun main() {..
https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프이론, 그래프탐색, 분리집합 설명 친구의 친구는 나에게도 친구이므로, 한 친구만 만들면 해당 친구가 속한 그룹은 모두 내 친구가 되므로, 그룹 당 친구비가 가장 적은 친구와 친구를 맺으면 됩니다. 접근방법 1. 분리집합 (유니온 - 파인드)를 사용해 각 친구관계를 그룹화한다. 2. 각 ..
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 뿌요뿌요 게임 시뮬레이션입니다. 연결된 뿌요의 개수가 4개 이상일 경우 뿌요가 삭제되고, 중력의 영향으로 밑으로 내려온 뒤 4개 이상의 뿌요가 새롭게 생기면 연쇄적으로 해당 뿌요 역시 제거됩니다. 뿌요의 상태가 주어졌을 때, 총 몇 번이나 연쇄적으로 뿌요가 삭제되는지 구하는 ..
https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 연구소1이 벽을 세워 안전지대의 최대 크기를 구하는 문제였다면, 연구소2는 모든 칸에 바이러스를 퍼뜨리는 가장 빠른 시간을 구하는 문제입니다. 연구소 1, 3과 마찬가지로 DFS를 사용해 조합을 구하고, 해당 조합으로 바이러스를 퍼뜨리는(BFS 사용) 시뮬레이션을 진행합니다. 소스코드 입력 lateinit..
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 시뮬레이션 설명 지렁이를 그냥 그려놓은 것 같지만, 잘 보다보면 규칙성을 찾을 수 있습니다. 0세대를 봅시다. → 방향입니다. 1세대 입니다. 0세대의 →를 90도 회전한 ↑ 방향입니다. 2세대입니다. 1세대는 →↑였습니다. ↑를 90도 회전하여 ←, →를 90도 회전하여 ↑가 되었습니다. 슬슬 규칙성이 보이시나요? 저는 한참을 계속 ..
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프 이론, 그래프 탐색, 정수론, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체 설명 한 번에 한 글자씩 수를 바꿀 수 있으며, 바꾼 숫자는 소수여야 합니다. 목표 숫자로 바꾸는 최소 횟수를 출력하는 문제입니다. 너비 우선 탐색(BFS)을 사용해 '숨바꼭질' 문제와 같이 최단 경로(최소 횟수)를 찾는 문제입니다. https://www.acmicpc.net/prob..
https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 창영이와 상근이가 차례로 막대기를 던져 미네랄을 파괴하는 문제입니다. 막대기는 수평으로만 날아가며, 미네랄이 파괴되면 해당 미네랄 클러스터를 내립니다. 접근방법 1. 막대기를 던진다. 첫 시작은 왼쪽 -> 오른쪽 이며, 번갈아가며 던진다 2. 막대기가 미네랄을 파괴했을 경우, 공중에 떠 있는 클러스터를 찾는다. 2..
https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 다들 한 번쯤은 해봤을 법한 디펜스 게임을 구현하는 문제네요. 궁수의 위치를 선택해야 했기 때문에 백트래킹을 사용한 수열 구하기를 사용해야하나? 싶었는데, 생각해보니 궁수는 3명으로 고정되어 있으므로, 굳이 백트래킹을 사용하지 않아도 3중 for문으로 간단히 가능합니다. 또, 가장 가까운 ..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 보물의 위치는 한 섬에서 서로 가장 먼 두 점에 있습니다. 최단경로가 아닌, 최장 경로를 찾는 문제인 셈이지요. 어떻게 구해야 하나 싶었는데, 가로, 세로의 길이가 각각 50이하인 것을 보고, 브루트포스적으로 접근하여 육지의 모든 점에서 BFS를 돌려 해당 점에서 가장 먼 점을 찾은 뒤, 가장 먼 점을..