[알고리즘] 이분 탐색과 결정 알고리즘 - Javascript 예제

결정 알고리즘

결정 알고리즘은 이분 탐색을 이용한 알고리즘입니다.

이분 탐색이란 중간값을 기준으로 탐색의 범위를 설정하여 찾고자하는 값을 찾아내는 탐색법입니다.

이분 탐색에 대한 예제는 아래의 게시글로 확인하는 것을 추천합니다.

[알고리즘] 이분 검색 / 이진 탐색 Binary Search - Javascript 예제

---

예제: 
무게가 다른 로봇들을  M개의 박스에 나눠 담고자 한다. 이때 박스의 최소 수용 무게를 구하라. (단, M개의 박스는 다 사용이 되어야한다. 또한, 모두 Nkg짜리 박스로 다 같은 용량의 박스이어야한다. 무게 단위는 kg이다. )
주어진 조건: 3개의 박스, 로봇들의 무게를 담은 배열: [1,2,3,4,5,6,7,8,9] => kg 기준

위의 예제에서 박스들의 무게를 담은 배열이 [1,2,3,4,5,6,7,8,9] 로 주어졌다.

문제를 위한 코드는 아래와 같다. 

  function count(robots, capacity) {
    let cnt = 1,
      sum = 0;
    for (let x of robots) {
      if (sum + x > capacity) {
        cnt++;
        sum = x;
      } else sum += x;
    }
    return cnt;
  }

  function solution(m, robots) {
    let answer;
    let lt = Math.max(...robots);
    let rt = robots.reduce((a, b) => a + b, 0);
    while (lt <= rt) {
      let mid = parseInt((lt + rt) / 2);
      if (count(robots, mid) <= m) {
        answer = mid;
        rt = mid - 1;
      } else {
        lt = mid + 1;
      }
    }
    return answer;
  }

  let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
  console.log(solution(3, arr));

우선 이 예제의 답은 17kg이다. 어떻게 나온 결과인지 살펴보자. 

---

이분 검색 활용하기

function solution(m, robots) {
	let answer;
    let lt = Math.max(...robots);
    let rt = robots.reduce((a, b) => a + b, 0);
    while (lt <= rt) {
    	let mid = parseInt((lt + rt) / 2);
        if (count(robots, mid) <= m) {
        	answer = mid;
            rt = mid - 1;
		} else {
        	lt = mid + 1;
        }
	}
    return answer;
}

lt : 박스의 수용 가능 무게가 될수 있는 최솟값
=>  로봇들의 무게 중 가장 가벼운 무게
rt: 박스의 수용 가능 무게가 될 수 있는 최댓값
=>  로봇들의 전체 무게

lt와 rt라는 변수로 박스의 수용 가능 무게 범위를 정한다. 그 후 범위와 그 범위의 중간값을 이용해 값을 탐색해내는 이분 검색을 활용한다. 범위의 중간값은 mid라는 변수로 선언한다. 

mid는 범위의 중간값이므로 

mid = parseInt((lt+rt)/2)

lt와 rt의 합의 반이 된다. 

 

 function count(robots, capacity) {
        let cnt = 1,
          sum = 0;
        for (let x of robots) {
          if (sum + x > capacity) {
            cnt++;
            sum = x;
          } else sum += x;
        }
        return cnt;
  }

이 count 함수는 robots 배열과 capacity 즉, mid 값을 박스의 수용 가능 무게로 받는다. 

count 함수는 로봇들의 무게가 담긴 배열과 mid값을 박스 최대 수용 가능 무게로 받는다. 

이후 배열을 차례로 돌면서 로봇을 하나씩 넣었을 경우에 박스에 담기게 되는 로봇의 전체 무게를 sum에 담는다. 이때 sum에 해당 차례의 로봇을 담았을 경우 sum의 값이 capacity보다 크면 그 박스엔 더 이상 로봇을 담지 않고 cnt 값을 1 증가 시킨다.

 

1) mid가 27인 경우 ( 박스 당 최대 수용 무게가 27kg인 경우 )

아래와 같이 첫번째 박스에 [1,2,3,4,5,6] , 두번째 박스에 [7,8,9] 이렇게 담기게 된다. 남은 세번째 박스엔 담긴 로봇이 없게되는 것이다. 

결과적으로 count함수는 2를 반환한다. 주어진 m 값인 박스수 3보다 반환값이 작기때문에 첫번째 if문의 경우에 해당하게 된다.

이제 27kg보다 작은 26kg이 박스 최대 수용 가능 무게일때부터 판별해보면 된다.  따라서 rt(박스가 수용할 수 있는 최대 무게) 값을 26으로 둔다. 

2) mid가 17인 경우 ( 박스 당 최대 수용 무게가 17kg인 경우 )

rt = 26, lt = 9이므로 mid = 17이 된다. 따라서 이번엔 mid가 17인 경우에 대해 알아보자.

이번엔 박스에 [1,2,3,4,5], [6,7], [8,9] 이렇게 세 박스에 나눠 담게된다. 따라서 count 함수가 3을 반환하게 되는 것이다. 

이번 경우엔 박스 세개가 모두 사용되었으므로 구하고자 하는 조건에 부합하게 된다. 박스 하나의 수용 가능 최대 무게가 17보다 작거나 크면 박스 3개가 다 사용되어지지 않거나 3개 이상의 박스가 필요한 경우가 되는 것이다. 

그리하여 문제의 답은 17이된다. 

 

---

틀린 부분이 있다면 댓글로 알려주세요!