https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 트리를 사용한 집합과 맵, 우선순위 큐 설명 우선순위가 최대 혹은 최소인 원소만 뺏던 기존 우선순위 큐와 달리, 최대와 최소 모두 뺄 수 있는 우선순위 큐 입니다. LinkedList도 써보고, 직접 배열로 우선순위 큐도 구현해 봤는데... 시간초과에서 헤어나오질 못해 검색해 봤더니 TreeMap이라는 자료구조를 발견하게 되었습니다. TreeMap은 키값..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 난이도 : 골드5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 주변(상하좌우, 대각선 X) 토마토를 익힌다 하였으니, BFS인걸 알 수 있다. 처음엔 초기 토마토 위치로 각각 BFS를 한 사이클씩만 돌리려 하였으나.... 그럴수가 있나..? 하는 생각에 접근법을 달리 하였습니다. 한 사이클이 돌 때마다, x, y값이 -1인 값을 큐에 넣어 확인하여 한 사이클이 돌 때..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 DFS와 BFS 그래프 탐색 문제이며, DFS와 BFS를 통해 구할 수 있습니다. 그러나, 이 문제에서는 BFS가 보다 적합합니다. DFS의 경우 모든 경로를 확인하며, 그중에서 가장 짧은 경로를 선택하여야 합니다. BFS의 경우는, 처음 마지막 좌표에 도착한 시점의 경로가 가장 짧은 경로입니다. 따라서 단순히 그래프를 탐색하는 것이 목적일때는 DFS..
https://www.acmicpc.net/problem/10820 10820번: 문자열 분석 문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있 www.acmicpc.net 난이도 : 브론즈 2 태그 : 구현, 문자열 설명 간단한 문자열 분석 문제입니다. 공백인지, 대문자인지, 소문자인지, 숫자인지 구해야 하는데, 코틀린에선 문자열 체크 메소드를 자체적으로 지원하기에 꽤 간단하게 풀 수 있습니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader fun main() { val br = Buff..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 난이도 : 실버 4 태그 : 다이나믹 프로그래밍 설명 동적계획법 (다이나믹 프로그래밍)을 이용해 풀 수 있는 문제입니다. 2로 나누기, 3으로 나누기, 1 빼기 중 하나를 통해 1로 만들 수 있는 최소한의 연한 횟수를 구하는 문제인데, 그리디(탐욕법)으로 생각할 수 있으나, 때로는 무조건 3으로 나누는 것이 더 효과적이지 않을 수 있습니다. 소스코드 import kotlin.math.min fun main() { val n = readLine()!!.toInt() val dp = Array(n + 1) { 0 ..
https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 난이도 : 실버 4 태그 : 자료구조, 덱 설명 이전에 포스팅했던 스택(https://uknowblog.tistory.com/11?category=989901)과 큐(https://uknowblog.tistory.com/19?category=989901)에 이어 또다른 자료구조인 덱을 사용하는 문제입니다. Deque는 덱, 데크, 데큐로도 불리며 한쪽 방향으로만 push / pop..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 난이도 : 실버 3 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 DFS 혹은 BFS를 이용해 연결된 노드의 갯수를 구하는 문제입니다. DFS, BFS 어느 것을 사용해도 무방하나 DFS를 많이 사용해봤기에 이번엔 BFS를 사용해 풀이해보겠습니다. 소스코드 인풋값 저장 val n = readLine()!!.toInt() val bridgeCnt = readLine()!!...
https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 난이도 : 실버 4 태그 : 큐, 자료구조 설명 이전에 포스팅했던 스택(https://uknowblog.tistory.com/11?category=989901)과 같이, 자료구조 큐를 사용하는 문제입니다. 소스코드 fun main() { var right = -1 var left = 0 val queue: Array val n = readLine()!!.toInt() queue =..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 난이도 : 골드 5 태그 : 브루트포스 설명 이동하려는 채널(target)을 시작으로, 윗 방향(upperBtn)과 아랫 방향(lowerBtn) 채널을 하나씩 체크해 나가며 풀 수 있습니다. 둘중 하나라도 고장나지 않은 버튼들로 이동할 수 있는 채널일때 해당 값을 출력하면 됩니다. 소스코드 val br = BufferedReader(InputStreamReader(System.`i..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 인풋값으로 받는 맵 정보를 두 개의 배열로 받아 적록색약이면 R과 G를 같은 색상으로 판단해 DFS / BFS를 돌리고, 적록색약이 아닌 사람이면 그대로 DFS / BFS를 돌려 풀 수 있는 문제입니다. DFS와 BFS 중 어느 것을 사용해도 무방하나, 본 포스팅에서는 DFS를 사용하였습니다. ..