알고리즘/알고리즘 문제풀이

백준) 이분탐색

lusida0131 2022. 6. 1. 18:10
728x90

백준 2417번 정수 제곱근

내가 떠올린 풀이 해설

처음 이 문제를 봤을 때 이분 탐색 문제라는 것을 떠올리지 못했다. 최솟값을 구하기 위해 min에다 long의 최댓값을 선언하고 start를 0 end를 입력 숫자 n으로 잡고 mid를 (start + end) / 2로 정해준다. value라는 변수를 하나 더 만들어 Math.pow(mid, 2) pow 메소드는 제곱근을 구할 수 있는 메소드이다. 제곱근이 0보다 커야 되니 if(value > 0)에서 if(value >= n) 일 때 최솟값 min = Math(min, mid)로 최솟값으로 바꿔준다.  if(value >= n) 일 때 end 값을 mid - 1 value가 n 보다 작으면 start 값을 mid + 1로 바꿔준다. while문 밖에서 min의 값을 출력해준다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2417 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		long start = 0;
		long end = n;
		long min = Long.MAX_VALUE;
		while(start <= end) {
			long mid = (start + end) / 2;
			long value = (long)Math.pow(mid, 2);
			if(value >= 0) {
				if(value >= n) {
					min = Math.min(min, mid);
					end = mid - 1;
				}
				else {
					start = mid + 1;
				}
			}
		}
		System.out.println(min);
	}
}

백준 10815번 숫자 카드

내가 떠올린 풀이 해설

어제 풀었던 29번 수 찾기 문제와 비슷한 접근을 하면 풀리는 문제입니다. 기본 이분 탐색 문제입니다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek10815 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < m; i++) {
			int look = Integer.parseInt(st.nextToken());
			int start = 0;
			int end = arr.length - 1;
			boolean result = false;
			while(start <= end) {
				int mid = (start + end) / 2;
				int midV = arr[mid];
				if(midV < look) {
					start = mid + 1;
				}
				else if(midV > look){
					end = mid - 1;
				}
				else {
					result = true;
					break;
				}
			}
			if(result) {
				System.out.print(1 + " ");
			}
			else {
				System.out.print(0 + " ");
			}
		}	
	}
}

백준 2805번 나무 자르기

내가 떠올린 풀이 해설

이 문제는 이분 탐색 문제인데 언제 이분 탐색을 사용하는지 못 떠올리다가 문제를 풀면서 떠올리게 되었습니다. arr배열에 넣으면서 end값을 최댓값으로 구한다. while(start < end) sum 변수를 만들고 mid 값을 (start + end) / 2 넣어준다. for문을 배열만큼 탐색하면서 arr [i] - mid값이 0보다 클 때 sum에 계속 더해준다. for문 밖에서 만약 sum이 m 보다 작으면 end에 mid를 넣어주고 작지 않으면 start에 mid + 1을 넣어주고 while문 밖에서 start - 1을 출력해준다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2805 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int []arr = new int[n];
		int start = 0;
		int end = 0;
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(end < arr[i]) {
				end = arr[i];
			}
		}
		while(start < end) {
			long sum = 0;
			int mid = (start + end) / 2;
			for(int i = 0; i < n; i++) {
				if(arr[i] - mid > 0) {
					sum += arr[i] - mid;
				}
			}
			if(sum < m) {
				end = mid;
			}
			else{
				start = mid + 1;
			}
		}
		System.out.println(start - 1);
	}
}

오늘의 회고

오늘은 이분 탐색 기본 문제를 풀었습니다. 이분 탐색을 공부하면서 젤 어려운 점이 이분 탐색을 언제 적용해야 되는지 떠올리는데 어려움이 있었습니다. 아직까지 많이 부족하다고 생각하고 알고리즘을 풀면서 계속 복습하고 새로운 문제를 풀겠습니다. 하루하루 열심히 꾸준히 노력하겠습니다.

728x90