목록DP (28)
기록방
👉 문제링크🔸 문제 분석 🔸전형적인 최장 증가 부분 수열 (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..
👉 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔸 문제 분석 🔸 정수 x, y, n이 입력된다. x를 3가지 연산 (+n, x2, x3) 으로 y를 만드는 최소 연산 횟수를 반환한다. y를만들 수 없으면 -1을 반환한다. 🔸 문제 풀이 🔸 BFS와 DP로 풀이할 수 있다. BFS는 각 인덱스를 처음 방문했으면 다음 3가지 연산을 수행해서 y를 찾아가는데, y를 초과하거나 이미 방문 했으면 제외한다. DP는 x부터 y까지 인덱스를 늘려가며 계산하는데, 처음 방문이면 현재 값을 넣고 이미 값이 있으면 더 작은 값을 선택하는 방식으로 y를 만들어 ..