1.  그리디 알고리즘이란?

  그리디 알고리즘은 욕심쟁이 알고리즘이라고도 불리는데 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 
  이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.
  그리디 알고리즘이 항상 최적해를 보장해주진 못하지만 몇몇 경우에 있어선 아주 효율적으로 최적해를 구할 수 있다.

 

1 - 1) 대표문제 1

function solution(meeting){
  let answer = 0;
  meeting.sort((a, b) => { 
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  })
  let et = 0;
  for (let x of meeting) {
    if (x[0] >= et){
      answer++;
      et=x[1];
    }
  }
  return answer;
}

 

1 - 2) 대표문제 2

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let timeLine = [];
  for (let i = 0; i < arr.length; i++) {
    timeLine.push([arr[i][0], "s"]);
    timeLine.push([arr[i][1], "e"]);
  }
  timeLine.sort((a, b) => {
    if (a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt();
    return a[0] - b[0];
  });
  let cnt = 0;
  for (let x of timeLine) {
    if (x[1] === "s") cnt++;
    else cnt--;
    answer = Math.max(answer, cnt);
  }
  return answer;
}

'Computer Science > 코딩테스트 문제 모음' 카테고리의 다른 글

Binary Search  (0) 2021.07.26
정렬  (0) 2021.07.24
스택/큐 자료구조 문제  (0) 2021.07.23
Hash Map  (0) 2021.06.14
Sliding Window Algorithm  (0) 2021.06.14

+ Recent posts