이진탐색

이번 문제의 핵심은 이전에 점프한 거리보다 1이상 더 긴 거리를 뛴다는 것과 밟을 수 있는 징검다리의 최대 개수를 구하라는 것이다. 문제 내용에 2번째 규칙은 "두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다"이고 이 문장을 통해 등차수열인 것을 알 수 있으므로 등차수열의 합 공식을 사용하면 된다. 등차수열 합 공식$ \frac{n(n + 1)}{2} $밟을 수 있는 징검다리의 최대 개수를 구하는 문제이기 때문에 등차수열의 합이 입력 n보다 작거나 같은 수 중에 최댓값을 찾으면 된다. 예를 들어 징검다리가 10개인 경우 1, 2, 3, 4번 징검다리를 건너가면 해결된다. 입력의 범위가 $10^{16}$이기 때문에 자료형은 int가 아닌 long으로 선언하였고 반복문으로 수..

이 문제를 처음 봤을 때 어떤 방식으로 풀어야 하는지 25분 정도 고민을 한 것 같다. 왜냐하면 아래와 같은 방식이나 이와 유사한 방식만 생각이 들었기 때문이다.입력받은 K[i]들을 다 더한 후 N으로 나눈다.나눈 몫을 1씩 줄여가며 각 랜선의 길이에 나눈다(2중 반복문).나눈 몫을 누적하여 N과 동일할 때까지 반복한다.이러한 풀이는 시간복잡도가 $O(n*m)$ (사실상 $O(n^2)$)이라서 풀 수 없다.해당 문제는 시간제한이 2초이고 주어진 값의 범위가 $1    결론적으로 이 문제는 이분탐색 알고리즘을$O(\log_2 n)$ 사용하면 해결된다.그러나 주의할 점이 있다. 문제 해결 시 주의사항1. 오버 플로우를 조심해라.- 이분탐색 로직 중 left와 right 변수를 더할 때 $2^{31}-1$을 ..

이 문제는 M개의 수가 각각 A 배열에 들어있는 지 확인하는 문제이다. M개의 수가 최대 100,000개이고 시간제한은 1초이기 때문에 정렬 후 이진탐색 알고리즘을 사용하면 된다고 생각하였다.이진탐색의 시간복잡도는 $ \log_2 N $ 이다. $ 2^{16} = 65,536 $$ 2^{17} = 131,072 $$ 16   이진탐색 구현private static int[] arrSearch;private static int binarySearch(int num) { int left = 0; int right = arrSearch.length - 1; while(left num) { right = mid - 1; } else if (arrSearch[mi..