기록방

👉 문제링크🔸 문제 분석 🔸스타크레프트 같은 게임에서 각 건물을 짓는데 필요한 최소 시간을 구해보자.N개의 건물 별 짓는 시간과 먼저 지어져야 하는 건물의 번호가 주어진다.🔸 문제 풀이 🔸선행 되어야 하는 번호가 주어지므로 위상 정렬(Topology Sort)을 활용해 풀이할 수 있다.선행 건물 건설 직후 해당 건물을 짓는데, 선행 건물이 여러개일 경우 순서를 정할 수 없다.따라서 선행 건물이 지어지는 시간의 최대값 + 현재 건물을 짓는 시간을 구한다.🔸 코드 🔸import java.io.*;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Queue;import java.util.StringTokenizer;pu..

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

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

👉 문제링크🔸 문제 분석 🔸n * m 배열에서 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다.🔸 문제 풀이 🔸먼저 Brute Force로 풀이 시 시간 복잡도를 계산해 보았다.정사각형의 오른쪽 아래 꼭짓점을 찾는다고 생각했을때, 한 점을 찍고 최대로 그릴 수 있는 정사각형을 찾아야 한다.실제로는 최대로 그려지는 값을 찾아야 해서 더 걸리겠지만,그려지는 정사각형의 한 변의 길이가 k라고 했을 때,어림잡아서 시간 복잡도는 O(n*m*k*k)이다.따라서 1,000 ^ 4 = 1조로 시간 제한인 1초를 가뿐히 넘게 된다.2차원 배열 형식에서 효율을 높이고자 하는 경우여서 DP를 의심하고 점화식을 찾기위해 노력했다.명쾌한 점화식 대신 손으로 적어보며 row, col 합배열을 만든 뒤 dp 배열을 만드..