알고리즘 공부/강의 - 4. 이분 탐색(검색),결정 알고리즘

 

 

 

이분 검색이란 정렬된 배열에서 원하는 결괏값을 빠르게 찾는 방법이다. 우리가 보통 업/다운 게임을 하면 정해진 숫자 범위 안에서 절반부터 나누며 시작하는 것을 알 수 있다. 그것과 같은 원리로 정렬이 된 상태에서 업다운 게임을 하며 원하는 배열을 찾는 것이다. 소스의 구현은 다음과 같다.

 

위에 9개의 배열이 있다. 배열의 왼쪽 끝 배열을 left 변수에, 오른쪽 끝 배열을 right 변수에, (left+right)/2를 mid에 넣는다. 그 후에 찾으려는 값을 mid와 비교한다.

예를 들어 내가 원하는 값이 4라면 어떻게 찾을까? 초기 값은 left는 0, right는 배열의 끝, mid는 (left+right)/2이다.

left=0, right=8, mid=4

 

원하는 값이 4라면 mid[(0+8)/2]보다 작으므로 right에 mid-1 값이 들어가게 된다. 그러면 left는 0이고 right는 3이 들어간다. 

left=0, right=3, mid=1

 

mid는 (0+3)/2=1.5이므로 1의 값이 되고(정수) 2번째 배열인 2값을 가리킨다.

2보다 크므로 left에  mid+1이 들어가서 2가 된다.

left=2, right=3, mid=2

 

마지막으로 left는 2, right는 3이므로 mid는 2가 되고 mid가 4가 되었으므로 탐색을 종료한다.

 

장점은 아무래도 모든 값을 조사하는 것보다 훨씬 적은 수를 비교하게 되어 속도면에서 빠르다는 것을 알 수 있다. 그리고 배열을 가리키는 변수를 놓는 방식으로 응용문제를 해결할 수 있다. 예를 들면 다음과 같다. 

 

배열의 크기(1≤N≤1,000), 나누는 수(1≤M≤N), 배열 값(1≤arr≤10000)이 주어진다. 배열의 순서를 바꾸지 않고 나눈다고 했을 때, 나누어진 각각의 배열의 합 중 최대인 것이 가장 작아질 수 있도록 하여라. 아래 예제는 9개의 배열을 3개로 나눌 때 8+9가 17이 되어 1+2+3+4+5, 6+7보다 크지만 가장 작게 나눌 수 있는 방법이다. 왜냐면 8이나 9가 딴 데 붙으면 다른 배열이 17보다 커지기 때문이다.

이런 문제를 풀 때는 정답을 미리 정해놓고 생각할 수 있다.

예를 들면, 이 예제에서 나올 수 있는 최대 정답은 1에서 9까지 모두 더한 45일 것이다. 그러면 정답의 범위가 1부터 45까지이다. 여기서 이분 탐색으로 정답을 정해놓는다. 정답을 (1+45)/2라고 하자. 그러면 23을 기준으로 나누게 된다. 그러면 분명 위의 배열은 3개가 아닌 2개로 나누어진다. 그러면 값이 너무 큰거니 정답을 다시 이분탐색 알고리즘에 넣어 (1+23)/2=12로 놓고 배열을 나눈다. 그러면 3개로 나누고 더 많이 남게 된다.[(1,2,3,4),(5,6), (7)...] 그러면 값이 너무 작은거니 다시 바꾼다.

이렇게 맞춰질 때까지 값을 정해서 푸는 방법을 결정알고리즘이라고 한다.

 

간단한 알고리즘이지만 매우 효과적이며 응용도 가능한 좋은 알고리즘이라 꼭 외워두면 좋은 것 같다.