[알고리즘] Parametric Search

 

이분법 : Bisection Method 

이진탐색 : Binary Search 

 

 

📝 [예제 - 백준 2805 나무 자르기] 

 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

위의 예시는 N개의 서로다른 길이의 나무가 있으며 동일한 높이에서 나무를 잘라낼 때,

총 길이 M을 얻을 수 있는 높이의 최대값을 구하는 문제이다. 

 

이분탐색을 응용하여 푸는 문제이다.

총 길이를 중앙값에서 뺀 값들을 더해가며 원하는 M값에 도달할 때, mid값을 반환하면 되는 문제이다. 

import java.util.Scanner;

public class Main {
	
	public static void main (String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[]arr = new int[N];
        
		for (int i = 0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int start= 0;
		int end = (int) 1e9;
		
		int result = 0;
		
		while(start <=end) {
			long total = 0;
			int mid = (start+end)/2;
            
			for(int i = 0; i<N ; i++) {
				if (arr[i]>mid) total += arr[i] -mid;
			}
            
			if(total<M) {
				end = mid-1;
			}
			else {
				result = mid;
				start = mid+1;
			}
		}
		System.out.println(result);
	}
}

 

*end값은 정수 범위값인 1e9로 해뒀는데, 배열 내 최대값으로 풀어도 무방하지 싶다. 그냥 값을 굳이 또 구하는 번거로움을 줄이기 위해 그냥 1e9를 쓰는 것도 나쁘지 않은 선택지같다.  

 

 

 

이분탐색 개념을 이해하고 문제에 응용하는 참고영상으로 동빈나의 유튜브 강의를 참고했다.  

https://www.youtube.com/watch?v=94RC-DsGMLo&t=814s 

 

위의 영상에서 나온 <떡볶이 떡 만들기> 은 백준의 나무자르기 문제와 같은 풀이법으로 풀 수 있다. 

 

 

---

 

 

📝 [덧]

 

(개념공부하면서 찾은 것)

 

해당 문제를 응용하여 

 

N개의 서로 다른 길이의 나무로 같은 길이의 나무 M개를 얻으려고 할 때,
나무의 최대 길이는?

 

로 바꿔볼 수 있다. 

 

import java.util.Scanner;

public class Main {
	
	public static void main (String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[]arr = new int[N];
		for (int i = 0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int start= 0;
		int end = arr[arr.length-1];
		int result = 0;
		
		while(start <=end) {
			long total = 0;
			int mid = (start+end)/2;
			
			for(int i = 0; i<N ; i++) {
				if (arr[i]>mid) 
				total += arr[i]/mid;
			}
			
			
			if(total<M) {
				end = mid-1;
			}
			else {
				result = mid;
				start = mid+1;
			}
		}
		System.out.println(result);
	}
}

 

그럴때는 잘라낸 값을 더해주는 것이 아니라, mid값으로 나눠주면 arr[i]에서 해당 길이의 나무를 몇개 얻을 수 있는지 알 수 있다. 

 

즉,  mid값으로 나눠준 arr[i]값을 더해주면 원하는 길이의 나무 M개를 얻을 수 있는 최대값이 얼마인지를 구할 수 있다.  

 

 

---

 

 

🔎[참고] 

 

1e9 = 1*10^9 = 1000000000,

2e9 = 2*10^9 = 2000000000

 

---

 

 

이분탐색은 알겠는데, 그걸 값의 범위로 생각하여 탐색하는건 이해가 잘 되지 않아서 아래의 영상을 참고했다. 

 

 

이게 대체 뭔 소린가 했는데 그래프를 통해 설명해주는 것을 통해 이해할 수 있었다. 

 

 

https://www.youtube.com/watch?v=F6lKjRDlOpk 

https://www.youtube.com/watch?v=Fn22nMA00o4 

 

 

도통 이해가 잘 되지 않아서 진짜 문제보고, 하나씩 출력해보고 다시 영상보고, 다시 문제보고~ 를 4~5번 반복해가면서 이해했다. 

한 번 더 꼬아진다면 그건 찾아낼 수 있을런지 싶다... 

 

머리야 ...