본문 바로가기

알고리즘/이분탐색6

[백준 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.
[백준] 수 찾기 / 자바 문제         레벨: 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.

티스토리툴바