두부의 코딩일기

https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 풀이 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하면 된다. 해당 문제에서 동근이가 상점으로 갈 수 있는 경로는 시계 방향, 반시계 방향 2가지가 존재한다. 동서남북으로 이루어진 직사각형 모양의 맵을 일직선으로 가정하고 풀면 쉽게 해결할 수 있다. 좌측 상단(0, 0) 부터 시작해서 시계방향으로 이어서 일직선으로 생각해준다. 일직선으로 가정했다면 최단 거리를 계산할 때 쉬워질 수 있다. 동근이..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 어린 시절에 많이 풀었던 스도쿠가 보이길래 한 번 풀어봤다. 문제의 조건은 우리가 알고 있는 스도쿠와 동일하다. 각 행과 열에 중복되지않은 9개의 숫자(1-9)가 존재해야 한다. 3x3 크기의 박스에 중복되지않은 9개의 숫자(1-9)가 존재해야 한다. 스도쿠에서는 위 두 가지 조건만 신경써주면서 빈칸에 1-9를 넣어주는 dfs를 돌려주면 된다. 하지만 dfs만 계속 돌리면 시간 초과가 ..

java: warning: source release 11 requires target release 11 프로젝트를 생성했을뿐인데 발생하는 에러다. Project SDK가 build.gradle에 적힌 버전과 맞지 않아서 발생하는 에러로 쉽게 해결할 수 있다. group = 'hello' version = '0.0.1-SNAPSHOT' sourceCompatibility = '11' build.gradle 파일을 보면 sourceCompatibility 를 볼 수 있다. "Java 11 버전을 쓰겠다." 라는 뜻이다. Project SDK 확인하는 방법 1. File > Project Structure에 들어간다. 2. Project Settings > Project 목록에 SDK 를 확인해보면 bui..

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음엔 완전 탐색으로 접근했다가 메모리 초과가 발생했다. 2중 for문을 이용해서 모든 경우의 수를 변경해준다. 이 과정에서 visited[number][cnt] 2차원 배열로 자리를 바꾼 후에 생기는 중복된 수를 제거했다. 중복된 수를 제거할 때는 변경 횟수도 중요하다. 변경된 숫자가 같더라도 1번 변경했을 때 나온 A와 2번 변경했을 때 나오는 B는 전혀 다르다. 그렇기 때문에 변경 횟수도 방문 여부를 체크해줄 때 꼭 필요하다. for (int i=0; i

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}, ..