결정 알고리즘(Decision Algorithm) 이란?

결정 알고리즘 이란  기본적으로 이분 탐색을 이용해서 해를 구하는 알고리즘 이다.

 

그렇다면 이분  탐색은 무엇이냐?

이분 탐색은 기본적으로 오름차순 정렬 되어 있는 배열에서 사용가능하며, 찾고자 하는 수가 몇번째 인덱스에 있는지에 대한

해를 구할때 사용된다. 

 

int [] arr = {1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 }

이러한 배열이 있을때 , 4 가 이 배열의 몇번째 인덱스에 있는지 알고싶다.

이분탐색의 규칙은 다음과 같다.

 

1. lt,  rt , mid 값 설정

2. target > mid 이면  , lt = mid+1

 

3. target  < mid 이면, rt = mid-1

 

4. lt<=rt 라면 계속 반복 (이진탐색을 계속 돌다보면 언젠가 lt가 rt보다 커짐)

5. mid값이 찾으려는 수와 일치하면 종료 if(arr[mid] == target )  return mid+1  

 

그림으로 설명하자면 다음과 같다

1. lt, rt, mid 값 설정 
1-1.  lt (left point)값 설정. 0번째 인덱스를 가르켜야 하기 때문에 ==>  0
1-2.  rt (right point)값 설정. 배열 마지막 인덱스 번호인   ==> 9
1-3. mid(중간 값) 설정. ( lt + rt ) /  2 ==> 4

 

찾으려는 값 target =4 이라고 할 때,

* 초기상태

int [] arr = {1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 } 

// lt = 0 , rt = 9 , mid = 4

 

* arr[mid] = 5 가  target = 4 보다 크기때문에 rt = mid - 1

int [] arr ={1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 }

// lt=0 , rt = 3 , mid = 1

 

 

* arr[mid] = 2 가  target = 4 보다 작기때문에 lt = mid + 1

int [] arr = {1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 }

// lt = 2 , rt = 3, mid=2

 

* arr[mid] = 3 가  target = 4 보다 작기때문에 lt = mid + 1

// lt=3, rt=3, mid=3

int [] arr = {1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 }

 

* arr[mid] == target = 4 이기 때문에 reuturn mid+1 

OUTPUT : 4   

가 출력된다. ( 찾으려는 4는 arr 배열의 4번째에 있다.)

 

이것이 결정 알고리즘에 일반적으로 많이 사용되는 이진탐색 이다.

그렇다면, 결정 알고리즘은 어떨때 사용해야 하는가??

 

- 결정 알고리즘은 배열이 있을때 최소값(lt), 최대값(rt)를 활용해서 주어진 해를 구할 수 있다고 확신할 수 있을때 사용해야 한다.

다음과 같은 문제가 있다고 한다.

* 뮤직비디오를 찍을때 아래와 같은 1~10 번 노래가 있고 1번은 1의 용량, 10은 10의 용량을 가진다고 하자.

또한 노래를 순서대로 녹화해야만 한다. M(3)개의 비디오에 모든 노래를 담아서 녹화하려고 하며 모든 비디오의 용량은 동일해야한다.

이때, 비디오의 최소 용량은??

int [] arr = {1, 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 }  

답: 17

설명: 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다.

17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 녹화가 불가능하다.

아래 링크에서 어떻게 17이라는 해가 구해졌는지 알아보자.

 

https://jung-hey98.tistory.com/4

뮤직비디오 문제 (결정알고리즘) 풀이