이분/삼분 탐색과 구현
1. 이분 탐색 이분 탐색이란 탐색의 범위를 절반으로 줄여나가는 방법을 말한다. 결정 문제 답이 yes 혹은 no로 나오는 문제. 일반적으로 이분탐색으로 풀 수 있는 문제들은 우리가 정할 수 있는 어떤 값 x가 있다. 이 x에 따라, 어떤 결정 문제의 yes/no가 정해진다. 문제에서는 그 값이 yes가 나오는 최소/최대의 x를 요구한다. x에 의한 결과는 연속적으로 변한다. 즉, x의 값이 증가/감소하다보면, 어느 순간 yes가 no로 바뀐다. 즉, x일때 yes이면 x+1(혹은 x-1)일때 no이다. 이러한 성질들을 만족한다. 즉 O와 X의 경계를 찾는 것이 목적인 문제이다. l-4 l-3 l-2 l-1 l r r+1 r+2 r+3 O O O O O X X X X KOI 2012 중,고등부 1번 : ..
2015. 7. 7. 01:02