Algorithm (35) 썸네일형 리스트형 JAVA : Uppered Bounded 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static int UpperBounded(int left, int right, int r, ArrayList list) { if (left == right) { if (left == list.size() - 1) { if (list.get(left).r >= r) return -1; } return left; } int mid = (left + right) / 2; if (list.get(mid).r 비트 연산을 이용해 2^n 이 맞는지 판별하기 문제를 풀다가 2^n이 맞는지 판별하기 위해서 while(){ if(N==2) true N % 2 ==1 false; N /=2; } 로직을 구현한적이있다. 이러한 판별법은 2가 될때가지 구해서 판별한다. 하지만 비트연산자를 보면 1 -> 1 2 -> 10 4 -> 100 8 -> 1000 보면 첫재 자리수 빼고는 전부 0인걸 알 수 있다. 결론부터 말하자면 밑에가 참이면 2의 제곱수이다. if( N == (N&-N)) 예를들어 8을 예시로 들겠다. 8을 비트로 만들면 1000 이된다. -N = 2의보수 와같다. 과 같다. 따라서 1000 이된다. 앞전 부호비트 생략 1000 & 1000 은 1000 즉 N과 같게되서 위의 조건문을 만족한다. 만약 3일경우 11 은 01 이된다. 이처럼 N&-N 연산은 .. JAVA : LIS nlongN 기법 lower_bound 기법 Lower_bound 기법이란 기존 N^2 방식에서 배열 N을 탐색하면서 새로운 벡터 배열에 가장 긴 수를 뽑을 수 있게끔 수들을 저장하는 기법이다. 10 20 40 25 20 50 30 70 85 라는 배열이 있다. 처음에 벡터에 10을 넣는다. 10 10 20 10 20 40 10 20 25 10 20 25 10 20 25 50 10 20 25 30 10 20 25 30 70 10 20 25 30 70 85 N까지 탐색하면서 벡터에 들어가는순서를 생각하면 이렇게 된다. 벡터에 가장 끝에 담긴수보다 현재 수가 더크면 길이를 증가시키고 추가하면 된다. 같은 경우는 버리면 된다. 작은 경우는 이진 탐색을 통해서 현재 이값이 지금까지 쌓아온 벡터중에 어디에 들어가야하는가 생각한다... 이전 1 2 3 4 5 다음