https://www.acmicpc.net/problem/1547 1547번: 공 첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것 www.acmicpc.net 난이도 : 브론즈 3 태그 : 구현, 시뮬레이션 설명 3개의 컵을 섞어, 공의 최종 위치를 찾는 문제입니다. 첫째 줄에 공이 들어있는 컵의 번호를 출력한다. 공이 사라져서 컵 밑에 없는 경우에는 -1을 출력한다. 이 문장때문에, 공이 사라지는 경우가 있나? 싶었지만, -1을 출력하는 코드가 없어도 잘 작동하는 걸 보니 그냥 장난삼아 넣은 문구인 것 같네요. 소스코드 fun main() = wi..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 같은 육지 내에서 최단 경로로 이동했을 때, 거리가 가장 긴 경로를 찾는 문제입니다. BFS를 응용하여 풀 수 있을 것 같은데요. 그럼, 같은 육지 내 겨올가 최대가 되는 경우는 어떻게 찾을 수 있을까요? 단순히 육지의 모든 점에서 BFS를 수행하면 됩니다. 가로, 세로의 크기가 최대 50밖에 되지 않..
https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 난이도 : 실버 4 태그 : 수학, 구현, 정렬 설명 Solved.ac 의 문제 난이도 계산 방법을 바탕으로 만든 문제인 것 같네요. 솔브드의 난이도 계산 시스템은 극단적인 값으로 인해 평균이 왜곡되는 것을 막기 위해 절사 평균을 사용하는데요. 단순히 의견 개수 * 0.15 (반올림)개 만큼 양극값을 제거하고 평균을 계산하면 됩니다. 소스코드 fun main() = w..
https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 난이도 : 골드 2 태그 : 자료구조, 우선순위 큐 설명 수를 차례로 입력받아가면서, 홀수 번째 수를 입력받았을 때 중앙값을 출력하는 문제입니다. 음.. 매번 정렬을 하면 당연히 시간초과가 날 것 같고, 정렬을 하는게 목적이 아니라, 단순히 중앙값을 찾는게 목적이기 때문에 우선순위 큐를 두 개 사용하면 해결할 수 있을 것 같습니다. 저는 일단, 절반을 기준으로 작은 값..
https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합, 플로이드–워셜 설명 다소 복잡한 문제라, 지문을 두 세번 정도 정독했던 것 같네요. 서로 알고 있는 사람들의 관계가 주어질 때, 서로 알고 있을 경우 무조건 같은 위원회지만, 위원회는 최대한 많아야 하므로, 서로 알고 있지 않을 경우 무조건 다른 위원회로 분리합니다. 위의 말은 최댓값이... 최소가 된다...?는 ..
https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 난이도 : 실버 1 태그 : 구현, 브루트포스 설명 다섯개를 연속으로 놓으면 승리하는 오목게임 문제입니다. 단, 육목이 되면 계속 진행합니다. 저는 한 점을 기준으로 오른쪽, 대각선 오른쪽 아래, 아래쪽 세 방향으로 탐색하면서, 같은 색의 돌이 5개 연속이고, 6개 연속이 되지 않으면서, 1칸 이전(왼쪽, 대각선 왼쪽 위, 위쪽)에 돌이 있는지 체크해줬습니다. 1칸 이전에 돌이 있으면 육목이기 때..
https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 난이도 : 골드 2 태그 : 브루트포스, 백트래킹 설명 처음엔 그리디적으로 생각해, 큰 색종이 부터 붙이면 되겠구나! 생각했으나, 6x6의 경우, 3x3 색종이를 쓸 경우 4장이면 가능한 것에 비해, 5x5를 쓸 경우, 5x5 색종이 한개와, 1x1 색종이 11장이 필요하기 때문에, 색종이 개수를 초과하여, 붙이는게 불가능합니다. 흠... 그리디는 아니겠고, 그럼 백트래킹 + 브루트포스인..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 난이도 : 골드 5 태그 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 설명 한 시간대에 동시에 진행중인 강의가 몇 개인지 체크하는 문제입니다. 가장 처음 든 생각은 아무래도 int 배열을 체크해놓고 하나씩 체크해볼까? 생각했지만, 시작, 끝 시간의 범위 (0 ≤ Si < Ti ≤ 109)를 보고 바로 다른 방법을 고민하였습니다. 아무래도 우선순위 큐를 사용해 그리디적으로 풀 수 있을 것 같네요. 위와 같이 그림으로 그려 나타내면 쉬울 ..
https://www.acmicpc.net/problem/17371 17371번: 이사 $(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의 www.acmicpc.net 난이도 : 골드 1 태그 : 그리디, 기하학 설명 다소 삽질을 좀 했던 문제였습니다. 가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표 가장 먼 편의시설까지의 거리는 잘 모르겠지만, 가장 가까운 편의시설까지의 거리는 사실 계산을 하는 로직이 필요하지 않습니다. 바로 편..
https://www.acmicpc.net/problem/17142 난이도 : 골드 3 태그 : 그래프 이론, 브루트 포스, 그래프 탐색, 너비 우선 탐색 설명 연구소 시리즈 3번째 문제입니다. 해당 문제는 크게 1. 입력 2. 바이러스 m개를 고르는 조합 (DFS를 사용한 브루트포스) 3. 바이러스 퍼뜨리기 (BFS) 으로 나눌 수 있겠습니다. 입력값을 받을 때, 바이러스의 위치를 저장 및 빈 공간을 카운트 한 뒤, 이를 DFS을 사용해 바이러스를 m개 고르고, bfs로 바이러스를 퍼뜨립니다. 소스코드 값 입력 import java.util.* import kotlin.collections.ArrayList data class Virus(val x: Int, val y: Int) lateinit var..