이분탐색

문제       풀이 핵심은 이분 탐색을 이용하여 푼다는 것이다. 찾고자 하는 수 중 가장 앞의 인덱스를 찾아야 하므로 기존 이분 탐색 로직에 아래 코드를 추가한다.if (arr[mid] == x) { answer = mid; // x를 찾았다면 위치를 업데이트 rt = mid - 1; // 더 왼쪽에 같은 값이 존재하는지 확인하기 위해 오른쪽 경계 줄이기}     코드package baekjoon._20551;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import..

설명      풀이 결정 알고리즘이란 이분 검색을 이용하는 것이다. lt와 rt 사이에 반드시 답이 있다고 보장할 수 있는 문제에만 적용이 가능하다. 답으로서 가능한지 범위를 좁혀 나가면서 최종적으로 답을 결정한다. 좋은 답을 향해 좁혀 나가는 알고리즘이다.  solution 함수 로직은 다음과 같다.정답이 될 변수 answer를 0으로 초기화 한다.lt는 배열의 최댓값이고, rt는 배열의 합이다.배열의 최댓값은 Arrays.stream(arr).max().getAsInt() 로 구한다.배열의 합은 Arrays.stream(arr).sum() 으로 구한다.이분 탐색을 수행한다. lt가 rt보다 작거나 같을 때 반복한다. while (lt 여기서 mid 변수는 DVD 한 장의 용량을 의미한다. mid 변수..

설명       풀이 이 문제를 통해 이분 검색 (Binary Search) 알고리즘에 대해 학습했다. 이분 검색은 오름차순이던 내림차순이던 정렬된 상태에서 수행해야 한다.앞에서부터 쭉 탐색하는 것은 순차 검색이라고 하며, 시간 복잡도는 O(n)이다.이분 검색의 시간 복잡도는 O(log(n))이다. 핵심은 다음과 같다.배열은 오름차순 정렬 되어있다고 가정한다. (Arrays.sort를 이용한다.)arr은 데이터가 들어있는 int형 배열이고, m은 찾고자 하는 수이다.두 포인터 변수 lt, rt, 그리고 mid 변수를 이용한다. lt는 왼쪽 인덱스 번호를 나타내며, rt는 오른쪽 인덱스 번호를 나타낸다. mid 변수는 (lt + rt) / 2 이다.lt가 rt보다 같거나 작은 동안 반복한다.(arr[mid..