두부의 코딩일기

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 위 문제의 로직은 아래와 같다. 낚시왕이 한 칸 오른쪽으로 이동한다. 해당 열에 해당하는 가장 가까운 상어를 잡는다. 살아있는 상어들은 이동한다. 1. 낚시왕이 한 칸 오른쪽으로 이동한다. for (int i=1; i

https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 풀이 가장 많은 고층 건물이 보이는 건물을 구하고, 거기서 보이는 건물의 수를 출력하라. 고층 건물이 보이기 위해선 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야한다. A와 B를 이은 선분의 기울기를 따져보면 쉽게 문제를 해결할 수 있다. 사실 필자도 기울기를 어떻게 구하는건지 몰라서 검색해봤다. 건물 A와 건물 B를 이은 선분의 기울기를 구하기 위해선 두 건물..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 4 x 4 크기의 공간에 물고기 16마리가 존재한다. 상어가 먹을 수 있는 물고기 번호의 최댓값은? 위 문제의 로직은 아래와 같다. 상어가 물고기를 잡아먹는다. 물고기가 이동한다. 1-1. 맨 처음 상어는 (0, 0)에 있는 물고기를 잡아먹는다. 1-2. 상어는 잡아먹은 물고기의 방향을 갖는다. 1-3. 방향을 유지한 채 범위 내에서 여러 개의 칸을 이동할 수 있다. (ex..

자바에는 얕은 복사 (Shallow Copy) 와 깊은 복사 (Deep Copy) 가 존재한다. 얕은 복사는 복사하려는 배열의 '주소값'을 복사함 깊은 복사는 '실제값'을 새로운 메모리 공간에 복사함 1차원 배열 - 얕은 복사 복사하려는 배열의 주소값을 가져옴 두 개의 배열 중 하나라도 값을 수정한다면 둘 다 수정됨 int[] A = {1, 2, 3}; int[] B = A; B[0] = 5; A[2] = 10; System.out.println(A[0]); // 5 System.out.println(B[2]); // 10 B[0]을 수정했지만 A[0]의 값도 변경되고, A[2]를 수정했지만 B[2]의 값도 같이 변하는 것을 볼 수 있다. - 깊은 복사 복사하려는 배열의 주소값이 아닌 실제값을 가져와서 ..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 요즘 마법사 상어 시리즈를 풀어보고있는데 파이어스톰 마법을 배웠다고 한다... 위 문제는 아래와 같은 과정을 거친다. 파이어스톰 단계를 L이라고 가정했을 때, (0, 0)을 시작으로 $2^{L}$x$2^{L}$ 크기의 부분 격자로 나눈다. 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 특정 칸에서 인접해있는 칸 중 얼음이 존재하는 칸이 3개 미만이라면 특정 칸의 얼음..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 위 문제는 맵 격자의 가운데 칸부터 토네이도가 이동을 시작한다. 한 번에 한 칸씩 이동하며 모래는 아래와 같은 비율로 흩날리게 된다. static double[] per = {1,1,2,2,7,7,10,10,5,0}; static int[][] sdx = { {-1,1,-2,2,-1,1,-1,1,0,0}, // 좌 {-1,-1,0,0,0,0,1,1,2,1}, ..

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) 정의 음의 가중치..