기록방

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

👉 문제링크🔸 문제 분석 🔸N개의 도시와 M개의 버스가 주어진다. 1번 도시에서 나머지 도시로 가는 최단 시간을 출력한다.버스는 시작 도시, 도착 도시, 이동 시간으로 이루어져 있다.이동 시간은 정수로 주어진다.🔸 문제 풀이 🔸그래프에서 최단 거리를 구하는 문제이고, 음의 가중치가 있으므로 벨만 포드 알고리즘을 이용한다.N번 마다 M개의 간선을 모두 검사하므로, 시간 복잡도는 O(NM)이다.이동 시간의 최대값은 499 * 10,000 으로, 약 5,000,000 까지 커지므로 int형으로 처리 된다.(노드가 일렬로 연결되어 있고, 에지의 최대 값인 10,000으로만 연결 된 경우)이동 시간의 최소값은 500 * 6,000 * -10,000 으로, -3,000,000,000(-30억) 까지 커지므..

👉 문제링크🔸 문제 분석 🔸N*M 미로에서 (1, 1) 부터 (N, M) 까지 가는 최소 비용을 구하는 문제이다.미로는 빈 방과 벽으로 이루어져 있고, 벽을 부수는데 비용이 1 소모된다.🔸 문제 풀이 🔸가중치가 0과 1로 이루어진 그래프에서 최소 비용 혹은 최단 경로를 구하는 문제라고 볼 수 있다.최단 경로 문제는 다익스트라(Dijkstra) 알고리즘을 많이 사용한다. 첫 번째 풀이에서 사용했다.다익스트라의 시간 복잡도는 O(E log V) 이다.노드를 방문해 가며, 가중치가 더 적은 경로가 발견되면 해당 노드부터 다시 경로를 탐색해보는 방법이다.가중치가 0과 1로 이루어진 경우에 0-1 BFS를 사용해서 더 효율적으로 풀이할 수 있다.0-1 BFS의 시간 복잡도는 O(V + E) 이다.모든 노..

👉 문제링크🔸 문제 분석 🔸N개의 단어가 주어진다. 단어는 알파벳으로 구성되어 있는데, 각 알파벳은 0~9 숫자로 변환할 수 있다.알파벳은 최대 10종류가 주어지고, 알파벳의 숫자는 겹치지 않아야 한다.N개의 단어를 숫자로 변환했을 때 총합의 최대값을 출력한다.🔸 문제 풀이 🔸각 알파벳이 어떤 숫자와 매칭 되어야 최대값이 되는지 찾는 문제이다.Brute Force로 전부 넣어봐도 찾을 수 있지만, 좀더 효율적으로 찾고자 각 알파벳 별 가중치를 계산한다.가중치 순서대로 9부터 0까지 부여한 후 값을 계산해 출력한다.🔸 코드 🔸import java.io.*;import java.util.Arrays;public class Main { public static void main(String[..

👉 문제링크🔸 문제 분석 🔸전형적인 최장 증가 부분 수열 (LIS) 문제이다.LIS의 DP 풀이는 O(n^2) 이고, 이분탐색 풀이는 O(nlogn)이다.여기서는 n이 1000이므로, DP 풀이를 사용했다.🔸 문제 풀이 🔸DP 배열을 만들어 사용한다.DP 배열에는 현재 인덱스를 포함해서 만들어지는 가장 긴 증가하는 부분 수열의 길이를 저장한다.배열을 순회하며, 이전 인덱스들 중 DP 배열 값의 최대값 + 1을 저장한다.dp[i] = max(dp[i], dp[j] + 1)🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;..