https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 로봇은 올리는 위치에만 올릴 수 있다. 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는 경사로를 놓을 수 있는 조건을 만족해야 한다. 지나갈 수 있는 길의 개수를 구하기 위해서 먼저 행별로 탐색한 후 열별로 탐색한다. 열별로 탐색할 때는 원래 지도의 전치행렬을 만들어서 탐색한다. private static int n, l; public static void main(String[] args) throws IOExceptio..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 먼저 각 학생마다 좋아하는 학생의 번호를 저장해야 하므로 Map 자료구조를 사용하여 key 값은 학생 번호, value는 ArrayList로 학생이 좋아하는 학생의 번호들을 저장했다. 이 때 단순 HashMap이 아닌 LinkedHashMap을 사용한 이유는, 정해진 순서대로 학생들의 자리를 배치해야 하므로 순서를 유지해야 하기 때문이다. HashMap은 값이 들어가는 순서를 보장..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 처음에는 맨 왼쪽의 블록을 제외하고, 각 블록들을 순차적으로 탐색하다가 맨 왼쪽의 블록과 높이가 같거나 큰 블록이 있는 경우 그 부분을 잘라서 그 안에서 고이는 빗물의 총량을 구하는 방식으로 생각했다. 즉, 빗물이 고이는 부분이 생길 때마다 배열을 잘라서 각 부분마다 빗물의 총량을 구하는 방식을 생각했다. 그리고 각 부분에 대해 각 블록들마다, 양 끝단의 블록들과의 차이를 ..

https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 풀이 위 문제는 다음과 같은 연산을 반복한다. 입력받은 숫자 -> 홀수 개수 카운트 숫자를 짜름 -> 짜른 각각의 숫자를 모두 더한 숫자 -> 홀수 개수 카운트한 다음 이전 카운트에 더함 숫자의 홀수 개수를 카운트한 다음 이전 카운트에 더하는 로직이 반복되므로, 재귀호출 또는 반복문을 사용해야 한다. 또한 만들 수 있는 모든 경우의 수를 구해 그중 최솟값과 최댓값을 구해야 한다. 즉, 재귀호출을 ..

3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 입력으로 보드의 크기, 사과의 위치, 뱀의 방향 변환 정보를 받아 static 변수에 저장한다. static int size; //보드 크기 static boolean[][] apples; //사과가 있는 칸은 true, 없으면 false static HashMap directChange; //뱀의 방향 변환 정보 public static void main(String[] args) throws IOException { BufferedReader br = new ..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 Node 클래스를 생성하고, 클래스 내에 int value, Node left, Node right 인스턴스 변수를 생성하여 각각 노드 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장한다. static class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } } static 변수로 루트 노드 Node root을 생성한다. static ..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 Node 클래스를 생성하고, 클래스 내에 String value, Node left, Node right 인스턴스 변수를 생성하여 각각 노드 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장한다. static class Node { String value; Node left; Node right; public Node(String value, Node left, Node right) { this.value = value; this.left = le..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그래프를 그려서 해결할 수 있다. 인접 리스트로 그래프의 정보를 저장하고, 루트 노드에서부터 DFS또는 BFS로 탐색을 시작하여 아직 방문하지 않은 노드를 찾을 때마다 부모 노드 저장 배열(parent)에 부모 노드 번호를 저장하면 된다. 코드 import java.io.*; import java.util.*; public class Main { static int[] parent; //부모 노드 저장 배열 public static void main(S..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 1 - 크루스칼(Union & Find 활용) 최소 스패닝 트리를 구하는 알고리즘은 두 가지가 있다. 1. 크루스칼 (Union & Find 활용) 2. 프림 (PriorityQueue 활용) 크루스칼 알고리즘의 매커니즘 -> 크루스칼 알고리즘은 기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 주어진 그래프의 모든 간선에 대해서, 간선의 연결비용을 낮은 순으로 오름 차순 정렬한다. 정렬된 간선 순서대로..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 시작 위치에서 도착 위치까지 가는 최소 시간을 구한다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 최단 경로를 구하는 문제지만, 특정 정점을 지나는 최단 경로의 길이를 구해야 한다. 1번 정점 -> N번 정점의 최단 경로를 구해야 하는데, 두 정점 v1, v2를 거치는 최단 경로를 구해야 한다. 즉 위 조건을 만족하는 1번 정점 -> N번 정점의 최단 경로는 두가지가 있다. 1. 1 -> v1 -> v2 -> N 2. 1 -> v2 -> v1 -> N 그렇다면 각 정점부터 정점까지의 최단 경로를 구해서, 모든..