기록방

👉 문제링크🔸 문제 분석 🔸총 m개의 컨테이너가 n개의 칸에 나누어 쌓여져 있다.n개의 각 칸의 컨테이너 높이가 1이하가 되도록 재배치할 때, 최소 이동 횟수를 출력한다.🔸 문제 풀이 🔸컨테이너의 높이를 평탄화 하는 문제이다.가장 먼저 정렬을 n번 수행해서 최대값을  -1 최소값을 +1 하는 방법이 있다n이 최대 10만이므로, 시간 복잡도는 O(n^2logn) 으로 1초를 초과하게 된다.최대힙, 최소힙 두 가지 우선순위 큐로 최대값과 최소값만 빠르게 구하는 방법이 있지만, 이 문제에서는 시간 초과가 나게 된다.그리디 알고리즘으로 효율적으로 계산해야한다.n개의 각 칸에 컨테이너는 결국 평균(m/n)에 수렴하게 된다.여기서 높이차가 1이하인 이유가 나오는데, 평균에 수렴할 때 몇 개의 칸은 평균+1..

👉 문제링크🔸 문제 분석 🔸R x C 격자판에서 지훈이의 위치와 불들의 위치가 주어진다.지훈이는 1분에 상하좌우 4방향으로 이동할 수 있고, 불도 1분에 4방향으로 확산된다.격자판의 가장자리로 가면 미로를 탈출 할 수 있다.지훈이가 불을 피해 미로를 탈출하기 위한 최단시간을 출력한다.만약 탈출하지 못한다면 "IMPOSSIBLE"을 출력한다.🔸 문제 풀이 🔸격자판에서 최단 거리를 구하는 단순 BFS 문제이다. 하지만 지훈이의 이동과 불의 확산 모두 고려해야 한다.큐를 이용한 BFS 구현에서 큐 사이즈만큼 반복해서 '1분'의 움직임을 제한해야 한다.지훈이의 위치는 맵에 그리지 않고 큐에만 넣고, 불은 맵에 'F'로 표시해 간다.지훈이는 불로 이동할 수 없을 뿐만 아니라, 큐에서 꺼냈을 때 현재 위치..

👉 문제링크🔸 문제 분석 🔸n x n 격자판에서 상하좌우로 움직였을 때 가장 긴 이동거리를 출력한다.이동 시 현재 위치 보다 큰 쪽으로만 이동할 수 있다.🔸 문제 풀이 🔸최장 이동 거리를 찾는 그래프 탐색 문제이고, 4방향 이동에 대한 정보를 따로 저장할 필요 없게 할 수 있도록 깊이 우선 탐색(DFS)를 사용한다.이동은 항상 격자판의 숫자가 큰 쪽으로 이동하므로, 특정 칸으로 진입하는 방향이 달라도 나가는 최적의 방법은 항상 같다. DP를 이용한다.이 원리를 이용해서 한 격자 칸에서 시작해서 최장 몇 길이까지 이동할 수 있는지 dp 배열에 저장해간다.이미 탐색했던 칸이라면, 재탐색 할 필요 없이 기존 최장값을 이용하면 된다.모든 칸에서 시작해보고 최대값을 구해 출력한다.🔸 코드 🔸impor..

👉 문제링크🔸 문제 분석 🔸N x N 지도에 2개 이상의 섬이 주어진다. 섬은 1로 상하좌우 연결된 덩어리이다.서로 다른 두 섬 사이에 다리 하나를 놓을 때, 다리의 길이의 최소값을 출력한다.🔸 문제 풀이 🔸단순한 그래프 탐색 문제이다.먼저 지도 상의 같은 섬 소속 1들을 묶어줄 필요가 있다.다리를 지을 때, 서로 다른 섬인지 알아야 하므로 섬 덩어리 별 다른 값을 넣는다.단순한 4방 탐색이므로, DFS나 BFS 상관 없이 사용하면 되는데, 여기서는 DFS로 통일해서 사용했다.섬 사이에 다리가 놓이는지 확인해야 한다.DFS로 한쪽 섬의 끝에서 다른 섬을 발견 할 때까지 탐색한다.한번 다리가 완성되면, 최소값으로 저장하고 백트래킹에 이용한다.🔸 코드 🔸import java.io.*;import..

👉 문제링크🔸 문제 분석 🔸좌표가 0부터 시작하는 101 x 101 격자판이 있다.N번의 드래곤 커브를 수행한 후에 한 격자의 네 꼭짓점이 모두 드래곤 커브에 포함 된 칸의 개수를 출력한다.드래곤 커브란 세대를 걸칠 수록 이전 세대의 마지막 점을 기준으로 기존 커브 그림을 90도 시계방향으로 돌려 추가로 이어 그리는 것이다.🔸 문제 풀이 🔸단순 구현/시뮬레이션 문제이다. 세대를 반복 할 때, 이전 세대의 회전 정보가 필요하다. 따라서 회전 정보를 누적해서 저장해야 하는데, 그 크기는 2^세대 수이다.세대를 반복 할 때마다 이전 회전 정보를 역순으로 조회해서 드래곤 커브를 계산하면 된다.마지막으로 칸의 개수를 카운트 할 때는 왼쪽 위 꼭짓점을 기준으로 격자판의 범위를 벗어나지 않게 조회한다.🔸 ..