기록방

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

👉 문제링크🔸 문제 분석 🔸전형적인 최장 증가 부분 수열 (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;..

최장 증가 부분 수열(LIS: Longest Increasing Subsequence)은 원소 n개의 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 말한다. ex) 수열 A = {10, 20, 10, 30, 20, 50} 의 경우 LIS = {10, 20, 30, 50} 이고, 길이는 4이다. LIS의 풀이 알고리즘은 대표적으로 DP와 이분 탐색이 있다. DP를 활용한 LIS 구현dp[ i ] = max( dp[ i ] , dp[ i - 1] + 1 )dp 배열에 각 인덱스의 원소를 포함 한 LIS의 최대 길이를 저장한다.(현재 인덱스의 앞쪽 dp 배열을 확인해 최대값 + 1. 혹은 현재 dp 배열 값 중 큰 것을 저장한다.)..

👉 문제링크 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 🔸 문제 분석 🔸 앞선 건물들이 모두 지어져야 해당 건물을 지을 수 있게 되는 건물 순서 규칙이 존재한다. 건물은 동시에 여러 개를 지을 수 있다. 목표 건물을 짓는데 드는 최소 시간을 출력한다. 🔸 문제 풀이 🔸 건물이 지어지는 순서가 달라질 수 있는데 선행 작업이 존재하므로, 위상 정렬을 사용해서 풀이한다. 동시에 건물을 지었다고 할 때, 가장 오래 걸리는 건설 시간이 최소값이다. 따라서 최대값을 갱신해서 저장하기 위해 DP를 사용한다. 점..

👉 문제링크 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 🔸 문제 분석 🔸 중간 원소를 기준으로 오름차순 후 내림차순이 이어지는 수열을 바이토닉 수열이라고 한다. 주어지는 수열의 부분 수열 중 가장 긴 바이토닉 수열의 길이를 출력한다. 🔸 문제 풀이 🔸 각 인덱스 별로 가장 긴 오름차순 수열과 가장 긴 내림차순 수열의 길이를 따로 구해 저장한다. 같은 인덱스의 두 값의 합 중 최대값을 출력한다. 🔸 코드 🔸 import java.io.*; import java.util.StringTokenizer; public class Ma..