매개 변수 탐색
이분 탐색을 응용한 알고리즘이다.
어떤 배열이 0과 1로만 구성되어있고, 이 배열이 정렬된 상태라고 생각해 보자.
0과 1의 경계를 찾으려면 어떻게 해야 할까?
인덱스 0부터 시작해서 순차적으로 탐색해 경계를 찾는 방법도 있지만, 딱 봐도 효율적이지 않다.
지난번에 배웠던 이분 탐색을 이 문제에 적용해보자.
L = 배열의 시작, R = 배열의 끝 으로 설정하고 이분 탐색을 수행하면 순차 탐색보다 훨씬 효율적으로 탐색할 수 있다.
이를 매개 변수 탐색이라고 하는데, 특정 문제에서 유용하게 사용될 수 있다.
1. 정답을 매개 변수로 만들고, 주어진 문제를 예 / 아니오 로 결정할 수 있는 문제로 바꿔 보자.
2. 배열이 정렬된 상태인가?
두 가지 조건이 성립한다면 매개 변수 탐색으로 해결할 수 있는 문제이다.
문제에서 "최댓값을 구하시오" 혹은 "최솟값을 구하시오" 라고 했을 때 매개 변수 탐색으로 접근할 수 있지는 않을까? 라고 생각해보자.
매개 변수 탐색 알고리즘을 사용해 문제를 푼다는 건, 특정 문제를 매개 변수 탐색 알고리즘을 사용해서 풀 수 있는 문제로 변환한 후 매개 변수 탐색 알고리즘을 적용해 푼다는 것을 의미한다.
그냥 푸는게 더 쉬우면 그냥 풀고.. 어떻게 풀 지 생각이 안 나거나 매개 변수 탐색 알고리즘을 사용해서 더 쉽게 풀 수 있을 것 같으면 시도해보자.
대표적인 문제로 백준에서 풀 수 있는 나무 자르기 문제가 있다.
https://13months.tistory.com/266
[백준] 2805 나무 자르기 - Java
매개 변수 탐색을 활용해 풀 수 있는 문제이다. 알고리즘 분류에 매개 변수 탐색이라고 나와있어서 쉽게 찾을 수 있지만.. 어떤 문제를 매개 변수 탐색으로 풀 수 있는지, 어떤 경우에 매개 변수
13months.tistory.com
'Algorithm > Theory && Tip' 카테고리의 다른 글
재귀 (0) | 2022.05.16 |
---|---|
그래프 (0) | 2022.05.12 |
정렬 기본 - Java (0) | 2022.05.03 |
최소 신장 트리 - Kruskal (Union Find) (0) | 2022.04.14 |
최단 경로 - 다익스트라 (0) | 2022.04.13 |
댓글
이 글 공유하기
다른 글
-
재귀
재귀
2022.05.16 -
그래프
그래프
2022.05.12 -
정렬 기본 - Java
정렬 기본 - Java
2022.05.03 -
최소 신장 트리 - Kruskal (Union Find)
최소 신장 트리 - Kruskal (Union Find)
2022.04.14