매개 변수 탐색

 

 

 

이분 탐색을 응용한 알고리즘이다.

 

어떤 배열이 0과 1로만 구성되어있고, 이 배열이 정렬된 상태라고 생각해 보자.

0과 1의 경계를 찾으려면 어떻게 해야 할까?

 

인덱스 0부터 시작해서 순차적으로 탐색해 경계를 찾는 방법도 있지만, 딱 봐도 효율적이지 않다.

 

지난번에 배웠던 이분 탐색을 이 문제에 적용해보자.

 

L = 배열의 시작, R = 배열의 끝 으로 설정하고 이분 탐색을 수행하면 순차 탐색보다 훨씬 효율적으로 탐색할 수 있다.

 

 

이를 매개 변수 탐색이라고 하는데, 특정 문제에서 유용하게 사용될 수 있다.

 

1. 정답을 매개 변수로 만들고, 주어진 문제를 예 / 아니오 로 결정할 수 있는 문제로 바꿔 보자.

2. 배열이 정렬된 상태인가?

 

두 가지 조건이 성립한다면 매개 변수 탐색으로 해결할 수 있는 문제이다.

 

문제에서 "최댓값을 구하시오" 혹은 "최솟값을 구하시오" 라고 했을 때 매개 변수 탐색으로 접근할 수 있지는 않을까? 라고 생각해보자.

 

 

매개 변수 탐색 알고리즘을 사용해 문제를 푼다는 건, 특정 문제를 매개 변수 탐색 알고리즘을 사용해서 풀 수 있는 문제로 변환한 후 매개 변수 탐색 알고리즘을 적용해 푼다는 것을 의미한다.

 

그냥 푸는게 더 쉬우면 그냥 풀고.. 어떻게 풀 지 생각이 안 나거나 매개 변수 탐색 알고리즘을 사용해서 더 쉽게 풀 수 있을 것 같으면 시도해보자.

 

대표적인 문제로 백준에서 풀 수 있는 나무 자르기 문제가 있다.

https://13months.tistory.com/266

[백준] 2805 나무 자르기 - Java