[인프런 자바스크립트 알고리즘] 마구간 정하기(결정알고리즘)

요새 알고리즘 공부를 다시 하고 있는데 그 중에 결정알고리즘은 좀 헤매면서 풀어서 복기할 겸 포스팅을 하게 되었다.

결정알고리즘은 주어진 범위내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다. 결정알고리즘은 이진탐색을 활용해서 풀 수 있다.

먼저 이진탐색에 대해 알아보자.

이진탐색(Binary Search)

• 이진탐색이란 정렬된 데이터에서 특정 값을 빠르게 찾이 위해 사용하는 탐색 알고리즘이다.

• 이진 탐색은 데이터를 반복적으로 반으로 나누어서 검색 범위를 줄이는 방식으로 동작한다.

• 시간 복잡도가 𝑂(log𝑛) 이다.
  
  

예제 문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수
중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는
프로그램을 작성하세요. 단 중복값은 존재하지 않습니다

예제 코드

function solution(target, arr) {
  arr.sort((a, b) => a - b);// 오름차순으로 정렬

  let lt = 0; // 시작 포인트
  let rt = arr.length - 1; // 끝 포인트

  while (lt <= rt) {
    let mid = Math.floor(lt + rt / 2); // 중간 숫자
    if (arr[mid] === target) {
      return mid + 1;
    } else if (arr[mid] > target) {
      rt = mid - 1; // 더 작은 숫자 탐색
    } else {
      lt = mid + 1; // 더 큰 숫자 탐색
    }
  }

  return -1;// 탐색 실패 시 -1 반환
}

console.log(solution(32, [23, 87, 65, 12, 57, 32, 99, 81]));

동작원리

1. 초기설정

• 데이터는 반드시 오름차순 혹은 내림차순으로 정렬되어 있어야 한다.
• 탐색 범위의 시작점과 끝점을 설정한다.

2. 중간값 확인

• 현재 탐색 범위의 중간 인덱스를 계산한다.

  let mid = Math.floor(lt + rt / 2);

3. 조건 확인

• 목표 값이 중간 값과 같은 탐색 성공
• 목표 값이 중간 값보다 작으면 탐색 범위를 중간보다 왼쪽으로 좁힘
• 목표 값이 중간 값보다 크다면 탐색 범위를 중간보다 오른쪽으로 좁힘

4. 반복

• 탐색 범위를 줄여가며 계속 반복한다.
• 시작포인트 > 끝 포인트가 되면 탐색 실패

그럼 이제 결정 알고리즘을 풀어보자.

마구간 정하기(결정알고리즘) 문제

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

문제풀이

function count(mid, coordinate) {
  let cnt = 1; // 첫 번째 말을 배치함
  let endPosition = coordinate[0]; // 첫 번째 마구간 좌표

  for (let i = 1; i < coordinate.length; i++) {
    if (coordinate[i] - endPosition >= mid) {
      cnt++;
      endPosition = coordinate[i];
    }
  }
  return cnt;
}

function solution(c, coordinate) {
  let answer = 0;
  coordinate.sort((a, b) => a - b); // 좌표를 정렬
	
  //범위 설정
  let lt = 1; // 가능한 최소 거리
  let rt = coordinate[coordinate.length - 1] - coordinate[0]; // 가능한 최대 거리
  while (lt <= rt) {
    let mid = Math.floor((lt + rt) / 2); // 중간 거리
    if (count(mid, coordinate) >= c) {
      // C마리 이상 배치 가능
      answer = mid; // 거리 후보를 업데이트
      lt = mid + 1; // 더 큰 거리 탐색
    } else {
      rt = mid - 1; // 더 작은 거리 탐색
    }
  }
  return answer;
}

console.log(solution(3, [1, 2, 8, 4, 9])); // 출력: 3

해당 문제에서 요구하는 것은 c마리의 말을 배치할 대 가장 가까운 두 말의 최대값이다.

이를 결정 알고리즘으로 바꾸면

가장 가까운 두 말의 거리가 mid일 때, 말을 C마리 이상 배치할 수 있는가?

이 질문에따라 조건을 좁혀 나가야 한다.

동작원리는 위에 이진탐색 알고리즘과 동일하고 말을 배치하는 로직만 추가로 구현하면 된다.