그리디(탐욕법)

• 문제를 해결하는 과정에서 그 순간순간 최적이라고 생각하는 결정을 하는 방식 반드시 최적의 해를 구해준다는 보장은 없다

• 배수 관계를 가지고 있어야지 그리디가 적용된다 그렇지않으면 결과값이 틀림

• 정렬을 해줘야지 풀리는 경우가 많다

동전교환

동전들의 주어져 있을 때 거스름돈을 거슬러 줄 동전의 최소 개수를 출력하자

function solution(nums,m){
  let answer = 0;

  for(let i = nums.length-1 ; i>=0 ; i--){
    answer += parseInt(m/nums[i]);
    m = m %nums[i];
  }

  return answer;
}

console.log(solution([1, 5, 10], 15));

✔동전 교환 문제도 지금 오름차순으로 정렬되어있고 배수인 경우이다

침몰하는 배

구명보트는 2명 이하로만 탈수 있고 보트 한개에 탈 수 있는 총 무게 M kg 이하로 제한
N 명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트 최소개수

function solution(nums,m){

  let answer = 0;
  let left = 0 ; 
  let right = nums.length-1
  nums = nums.sort((a,b)=> a-b);


  while(left < right){

    if(nums[left] + nums[right] > m){
      answer++;
      right--;
    }
    else{
      answer++;
      left++;
      right--;
    }
  }

  return answer;
}

console.log(solution([90, 50, 70, 100, 60], 140));

정렬하고 투포인터 개념으로 접근해서 풀었다!
정렬을 하면 풀리는 문제들이 많으니 앞으로 정렬부터 해보고 적용해본다!!

선긋기

여러개의 수직선을 긋는데 이미 선이 있는 위치에 겹쳐서 그려진 선도 있고 , 여러번 그은 곳과 한번 그은 곳의 차이는 구분할 수 없다

function solution(nums){

  let answer = 0;

  nums.sort((a, b)=>a[0]-b[0]); // 시작 정렬로 정렬하여 앞에서부터 측정 

  let s = nums[0][0]; // 선의 시작 점 세팅
  let e = nums[0][1]; // 선의 끝 점 세팅 

  answer+= e-s; // [0]인덱스의 길이 세팅

  for(let i = 1; i <nums.length; i++){
    if(nums[i][0]<=e && nums[i][1]>=e){ // 선이 앞의 좌표와 겹치는 경우 
      answer+= nums[i][1] - e; //i번째 시작점에서 앞의 끝점을 빼주면 겹쳐서 그린 부분으로 answer 에 누적 
      s = e; // 직전의 끝점을 시작 점으로 세팅 
    } 
    else{ //선이 겹치지 않는 경우 
      answer+=nums[i][1]-nums[i][0]; //  겹치지 않는다면 그냥 해당 좌표의 끝 - 시작 해주면 단독 길이가 나온다 
      s = nums[i][0]; // 시작점을 i번째로 세팅 
    
    }
    e = nums[i][1]; // 끝점은 각 좌표의 마지막 정렬이므로 공통으로 빼줬다 
  }
  return answer;
}
console.log(solution([[1,3] ,[2,5],[7,10]]));
console.log(solution([[5,6] ,[1,3],[7,8],[9,10]]));

x y 는 1~~ 1억 까지의 좌표점을 가지고 있기 때문에 배열은 사용하면안된다

회의실 배정

한 개의 회의실이 있는데 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수를 반환하라

function solution (meeting){

  let answer = 0;

  meeting.sort((a,b) =>{
    if(a[1] ==b[1]) return a[0]-b[0]; // [1,3] [3,3] 이처럼 끝나느 시간과 끝시간이 같아질수 있기 때문에 이럴 때는 시작 시간으로 정렬 !  
    else return a[1]-b[1]}); // 끝시간으로 정렬  , 시작 시간으로 하게되면 시간을 오래 차지하는 부분에서 반례 

  let use_check = 0
  for( let x of meeting){
    if(x[0] >= use_check){ //끝나는 시간보다 시작 시간이 더 큰가?
      answer++; 
      use_check = x[1]; // 끝나는 시간으로 세팅 다음 시작 - 끝 시간 비교를 위해 
    }
  }
  
  return answer;
}

console.log(solution([[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]]));

얘는 기준을 끝 시간을 잡아줘야한다
한개가 시간을 다 차지해서 사용할수가 없는 사태가 발생할 수 있기 때문이다. -> 제일 먼저 끝나는 회의부터 정렬하는 것이다
et를 끝나는 시간으로 지정

🔥아래 문제들은 구현한 max heap을 바탕으로 풀이

• max heap : 자식보다 부모가 값이 크다
• min heap : 부모가 자식보다 값이 작다

max heap

class maxHeap{

  constructor(){
    this.heap = [];
    this.heap.push(1e9); //10억 세팅 0번은 큰 값으로 생성해줘야한다 
  } //생성자로 배열 하나 생성 

  //노드 추가 
  insert(val){
    this.heap.push(val); // 끝 노드 하나 생성 
    this.upheap(this.heap.length-1); // 끝 노드의 인덱스를 알아야지 값 비교 가능  
  }
  upheap(pos){
    let tmp = this.heap[pos]; // 자기 자리를 찾아가려고 하는 값(위치를 위해서 ), 인서트에서 추가해준 값
    while(tmp > this.heap[parseInt(pos/2)]){ // parseInt(pos/2) temp의 부모노드이다 
      this.heap[pos] = this.heap[parseInt(pos/2)]; 
      pos = parseInt(pos/2) //pos 는 최종적인 위치를 찾는 애다 
    }
    this.heap[pos] = tmp; //upheap 
  }
  get(){
    if(this.heap.length===2) return this.heap.pop();
    let res = this.heap[1]; // 루트값 저장
    this.heap[1] = this.heap.pop(); // 맨 끝노드 하나 나와서 1번에 넣어준다 
    this.downheap(1, this.heap.length-1); //pos는 마지막 부모까지만 내려간다 그래서 마지막 노드의  /2 하면 마지막 부모를 찾을 수 있다 안그러면 인덱스 아웃오브 에러남 
    return res;
  }
  downheap(pos,len){
    let tmp = this.heap[pos],child;
    while(pos<=parseInt(len/2)){ //자기 자리 찾을 때 까지 계속 내려간다 마지막 부모까지 
      child = pos * 2;  //child 는 왼쪽 자식을 가리키고 있다  
      // 두 자식 중에서 큰걸 찾아야한다 
      if(child<len && this.heap[child] < this.heap[child+1]) child++; 
      if(tmp>=this.heap[child]) break; //자식보다 크거나 같으면 더이상 내려가면 안되므로 멈춰야한다 
      this.heap[pos] = this.heap[child];// 자식 값이 부모 위치로 옮겨간다 
      pos=child; // 얘네는 이제 포인트의 위치를 바꿔주는 것 
    }
    this.heap[pos] = tmp;
  }
  size(){
    return this.heap.length-1;  //heap 이 비어있냐 아닌가를 판단도 가능 
  }
}


let maxH = new maxHeap();

maxH.insert(2);
maxH.insert(3);
maxH.insert(4);


console.log(maxH);

마지막 남은 수

• 수열의 가장 큰 두개의 수를 뽑아서 정해진 행동들을 거친 후에 최종적으로 남은 수를 반환하라

function solution(nums){

  let answer = 0;

  let maxH = new maxHeap();

  for(let x of nums){
    maxH.insert(x);
  }


  while(maxH.size() > 1){
    let a = maxH.get();
    let b = maxH.get();

    if(a !==b){
      maxH.insert(a-b);
    }
  }

  if(maxH.size()=== 0){
    return 0;
  }
  else{
    answer = maxH.get();
  }

  return answer;
}


console.log(solution([5,2,4,3,1]));
console.log(solution([7, 6, 3, 2, 4, 5, 1]));

최대 수입 스케쥴

• 강의는 D일 안에 와서 강연을 해주면 M만큼의 강연료를 주기로 한다

• 단 하루에 하나의 기업만 강연 할 수 있다

• [50,2] 는 2일안에 (2일 포함) 와서 강연을 해주면 50의 강연료를 주겠다는 의미

class maxHeap{

  constructor(){
    this.heap = [];
    this.heap.push(1e9); //10억 세팅 0번은 큰 값으로 생성해줘야한다 
  } //생성자로 배열 하나 생성 

  //노드 추가 
  insert(val){
    this.heap.push(val); // 끝 노드 하나 생성 
    this.upheap(this.heap.length-1); // 끝 노드의 인덱스를 알아야지 값 비교 가능  
  }
  upheap(pos){
    let tmp = this.heap[pos]; // 자기 자리를 찾아가려고 하는 값(위치를 위해서 ), 인서트에서 추가해준 값
    while(tmp > this.heap[parseInt(pos/2)]){ // parseInt(pos/2) temp의 부모노드이다 
      this.heap[pos] = this.heap[parseInt(pos/2)]; 
      pos = parseInt(pos/2) //pos 는 최종적인 위치를 찾는 애다 
    }
    this.heap[pos] = tmp; //upheap 
  }
  get(){
    if(this.heap.length===2) return this.heap.pop();
    let res = this.heap[1]; // 루트값 저장
    this.heap[1] = this.heap.pop(); // 맨 끝노드 하나 나와서 1번에 넣어준다 
    this.downheap(1, this.heap.length-1); //pos는 마지막 부모까지만 내려간다 그래서 마지막 노드의  /2 하면 마지막 부모를 찾을 수 있다 안그러면 인덱스 아웃오브 에러남 
    return res;
  }
  downheap(pos,len){
    let tmp = this.heap[pos],child;
    while(pos<=parseInt(len/2)){ //자기 자리 찾을 때 까지 계속 내려간다 마지막 부모까지 
      child = pos * 2;  //child 는 왼쪽 자식을 가리키고 있다  
      // 두 자식 중에서 큰걸 찾아야한다 
      if(child<len && this.heap[child] < this.heap[child+1]) child++; 
      if(tmp>=this.heap[child]) break; //자식보다 크거나 같으면 더이상 내려가면 안되므로 멈춰야한다 
      this.heap[pos] = this.heap[child];// 자식 값이 부모 위치로 옮겨간다 
      pos=child; // 얘네는 이제 포인트의 위치를 바꿔주는 것 
    }
    this.heap[pos] = tmp;
  }
  size(){
    return this.heap.length-1;  //heap 이 비어있냐 아닌가를 판단도 가능 
  }
}




function solution(nums){

  let answer = 0;

  nums.sort((a,b)=> b[1]-a[1]); // 강연 D 일이 큰 순서대로 정렬 

  let day = nums[0][1]; // 제일 큰 day 부터 돌기 
  let maxH = new maxHeap();

  let k = 0  //let k = 0 으로 for문 안에 선언해줬을 시에 3번 돌면서 계속 k = 0 으로 선언되어  nums.length * 3 을 자꾸 더 돌아주려 해서 밖으로 빼서 선언 
  for(let i = day; i > 0; i-- ){ 
    for( ; k<nums.length ; k++){  
      console.log(`${nums[k][1]} ${i}`);
      if (nums[k][1] < i){
        break;
      } 
      maxH.insert(nums[k][0]); // 강연 D일이 1이 아닌경우에만 높은 강연료들을 골라서 스케쥴 선정 가능    
      //console.log(maxH);  
  }

  
  if( maxH.size()>0){ // heap에 값이 존재할 때만 최상값을 가져와 누적 
    answer +=maxH.get();
  }

  }
  return answer; 
}

console.log(solution([[50, 2], [20, 1], [40, 2], [60, 3], [30, 3], [30, 1]]));
//console.log(solution([[50, 2], [40, 2], [20, 1], [10, 1]]));
//console.log(solution([[50, 1], [40, 2], [20, 3], [10, 1]]));


function solution(nums, m){
  let answer=0;
  nums.sort((a, b)=>b[1]-a[1]);
  let maxN=nums[0][1];
  let maxH=new maxHeap();
  let i=0;
  for(let day=maxN; day>=1; day--){
      for( ; i<nums.length; i++){
          if(nums[i][1]<day) break;
          maxH.insert(nums[i][0]);
      }
      if(maxH.size()>0){
          answer+=maxH.get();
      }
  }
  return answer;
}

처음엔 for문을 돌면서 day 마다 for문을 배열만큼 또 돌면서 검사하는 실수를 범했다 (매우 비효율적 ) 한번만 검사하면 되는 부분이라 for 선언 변수를 밖에 선언 후 인덱스 값을 증가 day 가 바뀌어도 유지 했다