이분탐색8 [백준 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. [백준 1300] K번째 수 / 자바 / 이분탐색 #문제 레벨: G1알고리즘: 이분탐색 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1300#문제 풀이 1 ~ N*N의 숫자들을 이분탐색하여 알아낼 것이다. 해당숫자(L포인터와 R포인트에 의한 mid)를 행의 값으로 나눠주면 그 행에서 해당숫자보다 작거나 같은 숫자의 개수가 나오는 것이다. 각행마다 이 과정을 실행하고 더한 값이 B배열의 위치값(인덱스)이다. 이렇게 나온 값이 K보다 작거나 크다면 왼쪽 포인터와 오른쪽 포인터를 조절해서 해당숫자(mid)를 다시 만든다.예시를 들어 설명하겠다.N=4이고 K=9일 때초기 범위: left = 1, right = N * N = 4 * 4 = 16이진 탐색을 시작한다:mid = (1 + .. 2024. 8. 7. [백준 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. [백준] 수 찾기 / 자바 문제 레벨: S4알고리즘: 이분 탐색풀이시간: 10:29힌트 참조 유무:https://www.acmicpc.net/problem/19201 번째 시도 import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.Arrays;import java.util.StringTokenizer; public class Main { public static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp.. 2024. 6. 2. [백준] 숫자 찾기 / 자바 문제 레벨: 알고리즘: 이분탐색풀이시간: 40분힌트 참조 유무: 유https://www.acmicpc.net/problem/10816 1 번째 시도 [upper-bound, lower-bound 차이]lower bound, 즉 하한은 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 의미한다. upper bound, 즉 상한은 찾고자 하는 값을 초과한 값을 처음 만나는 위치다. 중복 원소에 대한 길이 = (상한 - 하한) mport java.util.Arrays;import java.util.StringTokenizer;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;.. 2024. 6. 1. [백준] 공유기 설치 / 자바 문제 레벨: G4알고리즘: 이분탐색 풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/21101 번째 시도 만약, 이 문제를 풀이하기 전에 이분탐색에 대해 조금이나마 헷갈리는 부분이 있다면 필자가 풀이한 숫자카드 2 문제를 한 번 보고 오시는 것을 추천드린다.자카드 2 문제에서 다루었던 Upper Bound, Lower Bound 형식을 그대로 적용시키면서 최대한 코드 재사용성을 높이고자 같은 구조를 띄도록 노력하고 있다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer; i.. 2024. 5. 31. [백준] 가장 긴 증가하는 부분 수열 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. 이전 1 다음
