🖋️ 그리디 알고리즘 풀이

구명보트

• 한 번에 최대 2명씩
• 무게 제한 O
• 사람들을 구출할 수 없는 경우는 없음
• 모든 사람들을 구명보트를 최대한 적게 이용하여 구출
  
  
• 사람들의 몸무게를 담은 배열 people
• 구명보트의 무게 제한 limit
• 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return

- 나의 코드 (효율성 시간초과, bad) ```javascript function solution(people, limit) { let count = 0; // 내림차순 people.sort((a, b) => a - b); // 구명보트 반복문 while (people.length) { let biggest = people.pop(); // filter 를 사용하는 것보다 일반 반복문이 더 빠름 // limit 의 가장 가까운 제일 큰 idx 계산 const idx = people.filter((v) => v + biggest <= limit).length; if (idx) people.splice(idx - 1, 1); count++; } return count; } ```

• 비슷한 성공 코드

function solution(people, limit) {
  let count = 0;
    
  people.sort((a, b) => a - b);
  while (people.length && people[0] + people[1] <= limit) {
      let idx = 0;
      let biggest = people.pop();
      while (idx < people.length) {
           if (people[idx] + biggest <= limit) idx++
           else break;
      }
      if (idx) people.splice(idx - 1, 1);
      count++;
  }
  return count + people.length;
}

섬 연결하기

• 다리를 여러 번 건너기 OK
• 도달할 수만 있으면 통행 가능
• 다리 건설하여 모든 섬을 통행 가능한 필요 최소 비용 구하기
  
  

1 <= n <= 100
costs.length <= ((n-1) * n) / 2 

* costs[i][0], costs[i][1] : 각 다리가 연결되는 두 섬의 번호
* costs[i][2] : 두 섬을 연결하는 다리를 건설할 때 드는 비용
* 같은 연결은 두 번 X (순서가 바뀌더라도 같은 연결)
* 연결할 수 없는 섬은 주어지지 않음

• 섬 개수 n
• 섬 사이에 다리를 건설하는 비용 costs
• 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때
  필요한 최소 비용을 return

• 그리디 코드

function solution(n, costs) {
    let result = 0;
    const p = Array.from({length: n}, (_, i) => i);
    costs.sort((a, b) => b[2] - a[2]);
    
    const find = (v) => {
        if (p[v] !== v) return find(p[v]);
        return v;        
    }
    
    const union = (a, b) => {
        a = find(a)
        b = find(b)
        if (a < b) p[b] = a;
        else p[a] = b;
    }
     
    while (costs.length) {
        const [a, b, c] = costs.pop();
        if (find(a) !== find(b)) {
            union(a, b)
            result += c
        }
    }
    
    return result
}

단속 카메라

• 고속도로를 이동하는 모든 차량이 고속도로를 이용
• 단속용 카메라를 한 번은 만나도록 카메라를 설치
• 최소 몇 대 카메라를 설치해야 단속 가능한지 구하기
  
  

routes[i][0] : i번째 차량이 고속도로에 진입한 지점
routes[i][1] : i번째 차량이 고속도로에서 나간 지점

- 고속도로를 이동하는 차량의 경로 routes - 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면
최소 몇 대의 카메라를 설치해야 하는지를 return

• 그리디 코드

const solution=(routes)=>{
  let cnt = 0;
  let camera = -30001;
  routes.sort((a,b)=>a[1]-b[1]);
  for(let item of routes){
    if(item[0]>camera){
      cnt++;
      camera=item[1];
    }
  }
 return cnt;
}