Binary Search(이진탐색)
정렬된 자료를 절반씩 나눠가며 특정 원소의 위치를 찾는 탐색 알고리즘. 시간 복잡도 O(log N).
1. 기본 문제
오름차순으로 정렬된 nums 정수 배열과 찾고자하는 값 target이 주어진다. target의 인덱스 번호를 찾아 반환하고 nums에 target 값이 없을 경우, -1을 반환한다.
public int solution(int[] nums, int target){
int left = 0;
int right = nums.length -1;
while(left <= right){ //좌측이 우측보다 작거나 같을 때까지만 while문 동작.
int mid = (left + right) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
2. Lower bound 를 이용한 Binary Search
타겟보다 같거나 큰 값이 나오는 처음 위치를 찾는다.
nums에 바구니에 최대한으로 담을 수 있는 과일의 개수가 오름차순으로 주어진다. A가 가지고 있는 과일의 총 개수는 n개이다.
각 바구니의 가격은 바구니에 최대한으로 담을 수 있는 과일의 개수 곱하기 100을 한 값이다. 이때 A가 써야할 최소비용은?
가능한 바구니가 존재하지 않을 경우, -1 반환.
public int lowerBound(int[] nums, int n){
int answer = -1;
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] >= n){ // n보다 nums[mid] 값이 크거나 같으면
answer = mid; // answer을 mid로 초기화한 후,
right = mid - 1; // right를 mid - 1로 초기화하여 더 작은 값 구하기.
}else left = mid + 1;
}
return nums[answer] * 100;
}
nums[mid]가 n보다 클 경우에는 A가 살 과일을 모두 담을 수 있으므로 우선 answer = mid 로 한다.
그 후, 더 작은 바구니로 과일을 모두 넣을 수 있는지 확인하기 위해 right = mid - 1을 한다.
* Upper bound
타겟보다 큰 값이 나오는 처음 위치를 찾는다.
public int upperBound(int[] nums, int n){
int answer = -1;
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] > n){ // n보다 nums[mid] 값이 크거나 같으면
answer = mid; // answer을 mid로 초기화한 후,
right = mid - 1; // right를 mid - 1로 초기화하여 더 작은 값 구하기.
}else left = mid + 1;
}
return nums[answer] * 100;
}
3. 백준 1654번 / 랜선 자르기
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
import java.util.*;
public class Main {
public long solution(int[] arr, int N){
long left = 1;
long right = arr[arr.length - 1];
long result = 0;
while(left <= right){
long mid = (left + right) / 2;
long linesCnt = 0;
for(long i : arr){
linesCnt += (i / mid);
}
if(linesCnt >= N) {
result = mid;
left = mid + 1; //최대 랜선의 길이를 구해야하므로 line의 개수가 N보다 크면 left를 옮긴다.
}else right = mid - 1;
}
return result;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int k = scan.nextInt();
int n = scan.nextInt();
int[] lines = new int[k];
for(int i = 0; i < k; i++){
lines[i] = scan.nextInt();
}
Arrays.sort(lines);
Main m = new Main();
System.out.println(m.solution(lines, n));
}
}
처음에 Arrays.sort(lines)를 놓쳐서 넣었는데, 넣고 나서도 계속 틀렸다고 나왔다. 한참을 고민했는데도 답이 안나와서 다른 분들의 코드를 참고했는데 변수들의 타입을 int로 넣어서 자꾸 틀렸던 것... int 범위를 넘어설 수 있어서 long으로 선언해줬어야했다.
* BufferedReader가 Scanner보다 속도가 빠르다고 한다.
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
public long solution(int[] arr, int N){
long left = 1;
long right = arr[arr.length - 1];
long result = 0;
while(left <= right){
long mid = (left + right) / 2;
long linesCnt = 0;
for(long i : arr){
linesCnt += (i / mid);
}
if(linesCnt >= N) {
result = mid;
left = mid + 1; //최대 랜선의 길이를 구해야하므로 line의 개수가 N보다 크면 left를 옮긴다.
}else right = mid - 1;
}
return result;
}
public static void main(String[] args) throws IOException{ //BufferedReader쓸 경우 IOException 처리 필요!
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] lines = new int[k];
for(int i = 0; i < k; i++){
lines[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(lines);
Main m = new Main();
System.out.println(m.solution(lines, n));
}
}
BufferedReader를 쓸 경우, IOException은 checked exception이므로 반드시 예외처리를 해줘야한다. (throws IOException(import 필요)) readLine함수는 한줄씩 읽어서 string으로 반환되는 함수로, System.in으로 키보드와 연결된 reader가 이 프로그램에서 인식되지 않을 때 예외를 던진다.(inPutStream == null일 때)
BufferdReader로 라인을 읽고 그 라인 안에서 특정 문자열을 읽으려면 StringTokenizer클래스를 사용해야한다.
라인 읽기 : new StringTokenizer(br.readLine)
공백단위로 읽기 : nextToken() 사용
nextToken()으로 읽어들일 때는 String 타입으로만 가능하다. Integer.parseInt()로 형변환을 해줘야지만 숫자 가능.
라인 한 줄을 읽고 다음 라인을 읽고 싶을 때는 new StringTokenizer(br.readLine()). 특정 문자열 단위로 읽고 싶을 때는 new StringTokenizer(st.nextToken(), 특정문자열))(default)는 공백.
StringTokenizer : String을 token 단위로 끊어준다.
공백말고도 다른 구획문자를 사용한여 끊어줄 수 있다.
String str = "Hello^my%wolrd";
StringTokenizer st = new StringTokenizer(str,"^%");
while(st.hasMoreTokens()) {
System.out.println(st.nextToken())
}
//Hello
//my
//world
*split vs StringTokenizer의 nextToken
split 은 정규식을 기반으로 자르는 로직으로서 내부가 복잡하지만, StringTokenizer의 nextToken()메소드는 단순히 공백자리를 땡겨 채우는 것이므로 효율적이다.
//BufferedReader에서 split 사용. (1, 2, 3 입력)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
// s[0] = "1";
// s[1] = "2";
// s[2] = "3";
4. 제곱근 12의 값을 찾기. 정밀도는 소수 5번째 자리까지 정확
public class Solution {
public double solution(int n){
double left = 0;
double right = n;
double answer = -1;
while(left <= right){
double mid = (left + right) / 2;
double mul = mid * mid;
if(mul <= n){ // if(mul >= n)로 했을 경우 answer에 12의 제곱근보다 더 큰 값이 저장
answer = mid;
left = mid + 0.00001; //0.0001로 할 경우, 소수 5번째자리까지의 정확도가 떨어짐.
}else right = mid - 0.00001;
}
return answer;
}
public static void main(String[] args){
Solution S = new Solution();
System.out.printf("%.5f", T.solution(12)); //소수 5번째자리까지 출력.
}
}
참고)
https://deftkang.tistory.com/215
https://velog.io/@ddungdding/throws-IOException-%EC%82%AC%EC%9A%A9-%EC%9D%B4%EC%9C%A0