문제를 푸는 기준

그리디는 지금 좋아 보이는 것을 고르는 기법이 아니라 그 선택이 이후 최적 가능성을 해치지 않는다는 근거가 있는 알고리즘입니다.

핵심 개념

대표 문제

최대 회의 개수

회의 [start,end] 배열 meetings에서 서로 겹치지 않게 선택할 수 있는 최대 개수를 반환하세요. 끝나는 시각에 다음 회의를 시작할 수 있습니다.

함수 시그니처: solution(meetings)

제한사항

• meetings의 길이는 0 이상 200,000 이하입니다.
• start는 end 이하입니다.

입출력 예

풀이 설계

1. 종료 시각 오름차순으로 정렬합니다.
2. 가장 빨리 끝나는 회의를 먼저 선택합니다.
3. 다음 시작이 마지막 종료 이상이면 선택합니다.

JavaScript 풀이

function solution(meetings) {
  const sorted = [...meetings].sort((a, b) => a[1] - b[1] || a[0] - b[0]);
  let count = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start < lastEnd) continue;
    count += 1;
    lastEnd = end;
  }
  return count;
}

복잡도

• 시간복잡도: O(n log n)
• 공간복잡도: O(n)
• 핵심 패턴: 가장 빨리 끝나는 구간부터 선택
• 경계 사례: 끝과 시작이 같으면 연속 선택 가능

연습 문제

1. 두 명 보트

최대 두 명일 때 최소 보트 수를 구하세요.

2. 숫자 제거

k개를 지워 가장 큰 수를 만드세요.

3. 동전 최소 개수

배수 동전 체계에서 최소 동전 수를 구하세요.

자주 하는 실수

• 정당성 없이 직감으로 기준을 정하는 실수
• 시작 시각이 빠른 회의를 먼저 고르는 실수
• 동률 정렬 기준을 빼는 실수
• 끝과 시작이 같은 경우를 확인하지 않는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• 프로그래머스 코딩테스트 고득점 Kit 
• MDN Array.prototype.sort