두부의 코딩일기

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 이번 문제는 설명에 너무 자세하게 적혀있어서 풀이할 게 없다. 문제에서 시키는대로 하면 된다. 우선 ArrayList 배열로 선언된 Student 에 학생의 번호와 좋아하는 학생의 번호를 넣어준다. 문제 1, 2, 3번의 조건을 쉽게 해결하려면 우선 순위 큐를 사용하면 된다. public static class Position implements Comparable{ int x; ..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 문제의 조건 및 구동 순서는 아래와 같다. 1. 벨트가 각 칸 위에 있는 로봇과 함께 움직인다. 2. 가장 먼저 벨트에 올라간 로봇부터 회전 방향으로 한 칸씩 이동한다. (이동하려는 칸의 내구도가 0 이상이며 로봇이 없을 경우) 3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 로봇을 올릴 수 있다. 4. 위의 과정을 내구도가 0인 칸의 개수가 K개 이상일 때까지 반복..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 생각했던 것보다 오래 걸렸던 문제였다. 위 문제에는 빨간 구슬과 파란 구슬 두 가지가 존재한다. 핵심은 빨간 구슬이 10번 이하로 움직여서 구멍에 들어가야한다. 또한, 빨간 구슬과 파란 구슬이 동시에 들어가면 안된다. 한 번의 움직임에 한 방향으로 벽이 나타날때까지 계속 움직일 수 있다. 빨간 구슬을 예로 살펴보겠다. // 빨간 구슬 int ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 전형적인 다익스트라 알고리즘 문제. 최단경로 응용 문제로 진행 과정을 자세하게 적어뒀다. 다익스트라에 대해서 처음 접하시는 분은 아래 링크를 먼저 읽어보는 걸 추천한다. https://sookr5416.tistory.com/160 자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리 다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치..

https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 이번 문제는 조건이 많아서 고민할 게 많았다. 구동 순서는 아래와 같다. 택시 위치로부터 가장 가까운 손님을 찾는다. (findPerson) - bfs 가까운 손님의 목적지까지 이동 (goTaxi) - bfs 위 내용을 반복한다. 1. 택시 위치로부터 가장 가까운 손님을 찾는다. public static void findPerson(int x, int ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음에 문제를 잘 못 이해해서 꽤 오랫동안 고민했다. 우선 모든 행과 열을 한 줄로 나열해서 체크해야 한다. 예를 들어, 위 그림처럼 6x6 행렬이 있다면 행 6번, 열 6번 총 12번의 체크를 해야 한다. for (int i=0; i 1) { return false; } 이젠 경사로를 놓았을 때의 경우만 생각하면 된다. 경사로를 놓았을 때 생기는 경우의 수는 2가지이다. 오르막 길 내리막 길 오르막 길, 내리막 ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 문제에 이해하기 쉽게 설명이 잘 적혀있으니까 생략하겠다. 위 문제에서는 두 개의 일이 순서대로 이루어진다. 미세먼지 확산: 4방향으로 먼지가 확산된다. 공기청정기 작동: 위 칸과 아래 칸의 바람이 방향이 서로 다르며 한 칸씩 먼지를 밀어낸다. 미세먼지 확산은 dfs 혹은 bfs를 이해하고 있고 관련된 문제를 풀어봤다면 쉽게 해결할 수 있을 것이다. public static void Dust..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 기본적인 bfs 에서 말이 이동할 수 있는 경로만 신경써주면 된다. 말처럼 이동할 수 있는 기회는 K번으로 횟수가 제한되어있으며 벽을 넘을 수 있다. 시작점 (0, 0) 으로 출발해서 (w, h) 까지 최소한의 횟수로 도착하면 된다. 원숭이 상태와 말 상태일 때를 구분해서 돌려주면 쉽게 해결할 수 있다. 1. 원숭이 상태일 경우 1) 이미 방문을 했는지 여부 판단 (visit..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 5가지의 감시 카메라가 상우하좌로 돌면서 사각지대의 최솟값을 찾아야한다. 감시 카메라의 경우의 수는 아래와 같다. 1번 카메라: 4가지 2번 카메라: 2가지 3번 카메라: 4가지 4번 카메라: 4가지 5번 카메라: 1가지 예를 들어 1번과 2번 카메라가 하나씩 존재한다면 경우의 수는 4 x 2 = 8가지이다. 경우의 수를 다 돌려주기 위해서 완전탐색 dfs를 돌려준다. public..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 문제의 조건은 매우 간단하다. 0이 등장하면 전에 입력받았던 숫자를 지우면 된다. 또한, 0이 등장했을 땐 지울 수 있는 숫자가 있음을 보장했기 때문에 예외 처리를 해줄 필요도 없다. 문제를 푸는 방법은 2가지가 있다. 1. 스택 (Stack) 을 이용하는 방법 import java.io.*; import java.util.*; public class Mai..