본문 바로가기

LIS5

[백준 14003] 가장 긴 증가하는 부분 수열 5 / 자바 / LIS #문제         레벨: P5알고리즘: LIS(이분탐색)풀이시간: 40분힌트 참조 유무:https://www.acmicpc.net/problem/14003 #문제 풀이        지난 LIS 문제들은 길이를 구하라고 하면 시간복잡도가 빡빡해서  이분탐색으로 풀어야 했고 LIS를 출력하라고 하면 시간복잡도가 넉넉했다. 그 이유는 이분탐색으로 LIS를 구하면 O(n)으로 구할 수는 있지만 LIS가 정확하지 않을 수 있기 때문이다. 그 예로는 아래 배열을을 참고해보자 2 6 3 4 1 5[2][2, 6][2, 3] (6을 3으로 대체)[2, 3, 4][1, 3, 4] (2를 1로 대체)[1, 3, 4, 5]최종적으로 얻은 배열 [1, 3, 4, 5]는 실제 LIS가 아니다. 1은 원래 수열의 맨 뒤쪽에 .. 2024. 8. 11.
[백준 14002] 가장 긴 증가하는 부분 수열4 / 자바 / dp #문제         레벨: G4알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14002#문제 풀이         [1번째 시도: 실패]멍청한 풀이. 시간복잡도 n으로 풀 수 있지 않을까? 그리드 형식으로 랭킹을 매기는 방식. 혹시 나와 같은 사람이 있을까봐 기입해두었다. skip해도 된다.package project;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(.. 2024. 7. 10.
[백준 2565] 전깃줄 / 자바 / dp + LIS 문제         레벨: G5알고리즘: dp + LIS 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/25651 번째 시도   [알고리즘 설명]이 문제는 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘을 사용하여 해결할 수 있습니다. 전깃줄이 교차하지 않으려면, B 전봇대의 연결 위치가 증가하는 순서여야 합니다. 따라서 LIS를 찾으면 교차하지 않는 최대 전깃줄의 개수를 알 수 있고, 전체 전깃줄 개수에서 이를 뺀 값이 제거해야 할 최소 전깃줄의 개수가 됩니다. 시간복잡도 O(n^2) 코드import java.util.*;import java.io.*;public class Main { public s.. 2024. 7. 8.
[백준 11054] 가장 긴 바이토닉 부분 수열 / 자바 /dp 문제         레벨: G5알고리즘: DP풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/110541 번째 시도   위 문제는 LIS와 LDS 합친 문제이다.참고로 LDS는 LIS를 거꾸로 구현하면 된다.[1. LIS 구하는 법: O(N^2)]dp배열에는 LIS 순서가 담긴다.dp[i]를 구할 때마다 i-1까지 탐색한다.// N은 배열의 크기for (int i = 0; i  [2. LIS 구하는 법: O(NlogN)]dp배열에는 LIS 원소가 담긴다.아이디어 컨셉: 숫자마다 간격이 좁을 수록 가장 긴 LIS이다.원본 배열을 탐색할 때마다 이분 탐색(O(logN))을 해야한다. 그래서 O(NlogN)이다int len=0; int idx=0; for(int i=0;.. 2024. 6. 8.
[백준] 가장 긴 증가하는 부분 수열 2 / 자바 ** 문제         레벨: G2알고리즘: 이분탐색풀이시간: 1시간힌트 참조 유무:  유https://www.acmicpc.net/problem/120151 번째 시도   [  LIS (Longest Increasing Subsequence) 란]어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이다.LIS를 구할 때는 DP를 사용한다.LIS의 길이를 구할 때는 이분 탐색(O(nlogn))을 사용한다. DP(O(n^2))로 길이를 구할 시 시간초과가 난다[알고리즘 설명]*이 알고리즘은 고정된 사고를 달리해서 이해해야 합니다*핵심 아이디어: 길이가 동일한 증가 부분 수열 중에서 마지막 값이 작은 것을 유지합니다.지금부터 배열을 순회하면 LIS를 찾아보도록 하겠습니다.수열 A가.. 2024. 5. 29.

티스토리툴바