기록방

👉 문제링크🔸 문제 분석 🔸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..

👉 문제링크🔸 문제 분석 🔸T번의 테스트 케이스안에서 다음과 같은 입력이 주어진다.n명 (2~10만)의 학생 수가 주어지고, 다음 줄에 각 학생이 같이 팀을 하고 싶은 학생의 번호가 주어진다.자기 자신을 뽑거나, 팀을 하고싶은 학생들끼리 순환구조(서클)이 만들어지면 팀을 만들 수 있다.최종적으로 팀에 속하지 않은 학생의 수를 출력한다.🔸 문제 풀이 🔸제한시간 3초에 각 테스트 케이스의 n이 10만이기 때문에 O(n^2)의 알고리즘은 사용할 수 없다.팀이 만들어지는지 확인하기 위해 깊이 우선 탐색(DFS)를 사용한다.DFS의 경우의 수는 다음과 같다.1) 탐색하다가 시작 번호를 다시 찾음 : 탐색한 모든 학생들은 같은 팀2) 탐색하다가 중간 번호를 다시 찾음 : 중간 번호까지 팀이고, 시작 번호부..