기록방

👉 문제링크🔸 문제 분석 🔸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^세대 수이다.세대를 반복 할 때마다 이전 회전 정보를 역순으로 조회해서 드래곤 커브를 계산하면 된다.마지막으로 칸의 개수를 카운트 할 때는 왼쪽 위 꼭짓점을 기준으로 격자판의 범위를 벗어나지 않게 조회한다.🔸 ..

👉 문제링크🔸 문제 분석 🔸T번의 테스트 케이스로 K개의 양수가 주어진다.연속된 두 값의 합으로 계산했을 때 연산 비용의 최소값을 출력한다.🔸 문제 풀이 🔸K가 500이지만, Brute Force로 확인했을 때 O(K^3) 이상이 나올 것으로 예상해서 더 효율적으로 구하기 위해 DP 를 활용하고자 했다.dp 배열은 다음과 같이 구했다.1번부터 K번 숫자를 합했을 때 최소값을 구하고자 하므로, dp[0][K-1]를 구한다.다시 말해 dp 배열은 해당 범위의 최소연산 비용을 저장한다.dp 배열을 채워갈 때, 연속된 두 값을 더해가므로, 중간에 1번 잘라서 좌우 값을 더했을 때의 최소값을 구한다.따라서 점화식은 다음과 같이 구할 수 있다.K개의 숫자 중 left ~ right 범위를 계산했을 때 최소..

👉 문제링크🔸 문제 분석 🔸N개의 행렬을 곱셈 계산하려고 한다. 행렬의 곱은 곱셉 연산의 순서에 따라 연산 횟수가 달라진다.행렬곱 연산의 최소값을 출력한다.🔸 문제 풀이 🔸다이나믹 프로그래밍으로 풀이할 수 있다.dp배열로 int형 2차원 배열을 만들어 dp[i][j] : i ~ j 번 행렬 곱의 연산 수 최소값을 저장한다.i ~ j 의 크기 size를 2 이상부터 N 이하까지 늘려가며 dp 배열을 채워간다.i == j (size == 1) 일 때, dp[i][j]는 0이다.최대 int형만 사용된다고 문제에서 나타내주었다.🔸 코드 🔸import java.io.*;import java.util.StringTokenizer;public class Main { public static void..