Skip to Content
WebJavaScriptJavaScript 코딩테스트14. 그리디 알고리즘

이번 편의 결과물: coding-test/14-greedy/에 회의실 최대 배정·최소 동전 개수·최소 회의실 수·부분 배낭 4문제 풀이와 테스트를 작성해 node --test를 통과시킵니다. · 다루는 개념: 탐욕적 선택 조건 판단, 그리디와 DP의 구분 기준, 구간 스케줄링

이 편에서 만드는 파일

coding-test/
└── 14-greedy/
    ├── 01-max-meetings/
    │   ├── solution.js                (+)
    │   └── solution.test.js           (+)
    ├── 02-min-coin-count/
    │   ├── solution.js                (+)
    │   └── solution.test.js           (+)
    ├── 03-min-meeting-rooms/
    │   ├── solution.js                (+)
    │   └── solution.test.js           (+)
    └── 04-fractional-knapsack/
        ├── solution.js                 (+)
        └── solution.test.js            (+)

개념 정리

그리디 알고리즘이란

그리디(탐욕적) 알고리즘은 매 단계에서 “지금 시점에서 가장 좋아 보이는 선택”을 하고 다시 되돌아보지 않는 방식입니다. 13편의 DP처럼 모든 부분 문제의 결과를 저장하지 않으므로 보통 더 빠르지만, 항상 정답을 보장하지는 않습니다.

그리디가 통하는 조건

조건의미
탐욕적 선택 속성각 단계의 지역 최적 선택을 모으면 전체 최적해가 된다
최적 부분 구조전체 문제의 최적해가 부분 문제의 최적해를 포함한다(DP와 공통)

두 조건을 만족하는지 증명하기 어려울 때가 많으므로, 실전에서는 “정렬 기준을 정하고 그 순서대로 선택했을 때 반례가 있는지” 작은 예시로 먼저 확인하는 편이 실용적입니다.

그리디와 DP의 구분 기준

같은 냅색 문제라도 물건을 쪼갤 수 있는지(부분 배낭)와 없는지(0/1 냅색)에 따라 풀이 방식이 달라집니다. 이번 편의 문제 2와 문제 4는 13편의 DP 풀이와 짝을 지어, 같은 유형의 문제가 조건에 따라 그리디로도 DP로도 풀린다는 것을 비교합니다.

구분그리디가 통하는 경우DP가 필요한 경우
동전 거스름돈500, 100, 50, 10원처럼 큰 단위가 작은 단위의 배수인 표준 체계1, 3, 4원처럼 배수 관계가 아닌 임의 체계
배낭 문제물건을 쪼갤 수 있는 부분 배낭(fractional)물건을 통째로만 담는 0/1 냅색

문제 1. 겹치지 않게 회의실에 배정할 수 있는 최대 회의 수

문제 설명

시작 시각과 끝나는 시각이 있는 회의 목록이 주어집니다. 회의실은 하나뿐이고, 겹치는 두 회의는 동시에 배정할 수 없습니다. 배정할 수 있는 최대 회의 개수를 구합니다.

제약값
회의 개수1 이상 1000 이하
시작·종료 시각0 이상 정수, 시작 < 종료

입출력 예

입력출력설명
[{start:1,end:3},{start:2,end:5},{start:4,end:6},{start:6,end:8},{start:5,end:9},{start:8,end:10}]4[1,3], [4,6], [6,8], [8,10] 순서로 배정

접근

끝나는 시각이 빠른 회의부터 선택하는 것이 유리합니다. 가장 먼저 끝나는 회의를 고르면 다음 회의를 고를 여지가 가장 많이 남기 때문입니다. 회의를 종료 시각 기준으로 정렬한 뒤, 마지막으로 선택한 회의의 종료 시각보다 시작 시각이 크거나 같은 회의를 순서대로 선택합니다. 정렬에 O(n log n), 이후 한 번의 순회에 O(n)이 걸려 전체 시간 복잡도는 O(n log n)입니다.

풀이

// coding-test/14-greedy/01-max-meetings/solution.js
// 시간복잡도: O(n log n) — 종료 시각 기준 정렬 후 한 번 순회한다
// 공간복잡도: O(n) — 정렬된 복사본 배열을 만든다
export function solution(meetings) {
  const sortedByEnd = [...meetings].sort((a, b) => a.end - b.end);
 
  let count = 0;
  let lastEnd = -Infinity;
  for (const { start, end } of sortedByEnd) {
    if (start >= lastEnd) {
      count += 1;
      lastEnd = end;
    }
  }
  return count;
}

테스트

// coding-test/14-greedy/01-max-meetings/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
 
test('겹치지 않는 최대 회의 수는 4', () => {
  const meetings = [
    { start: 1, end: 3 },
    { start: 2, end: 5 },
    { start: 4, end: 6 },
    { start: 6, end: 8 },
    { start: 5, end: 9 },
    { start: 8, end: 10 },
  ];
  assert.strictEqual(solution(meetings), 4);
});
 
test('모든 회의가 겹치면 1개만 선택된다', () => {
  const meetings = [
    { start: 0, end: 10 },
    { start: 1, end: 9 },
    { start: 2, end: 8 },
  ];
  assert.strictEqual(solution(meetings), 1);
});
 
test('회의가 하나면 항상 1개', () => {
  assert.strictEqual(solution([{ start: 0, end: 1 }]), 1);
});
node --test coding-test/14-greedy/01-max-meetings/solution.test.js

함정

  • 시작 시각 기준으로 정렬하면 반례가 생깁니다. 반드시 종료 시각 기준으로 정렬해야 합니다.
  • start >= lastEnd 대신 start > lastEnd를 쓰면 끝나는 시각과 시작 시각이 정확히 같은 회의를 겹친다고 잘못 판단합니다(문제 조건에 따라 확인 필요).

문제 2. 최소 동전 개수로 거스름돈 만들기

문제 설명

사용 가능한 동전 단위 목록과 거슬러 줘야 할 금액이 주어질 때, 필요한 동전의 최소 개수를 구합니다. 각 단위는 원하는 만큼 사용할 수 있습니다.

제약값
동전 단위500, 100, 50, 10처럼 큰 단위가 작은 단위의 배수인 표준 체계
금액0 이상 100000 이하

입출력 예

입력출력설명
coins = [500, 100, 50, 10], amount = 12606500×2 + 100×2 + 50×0 + 10×6 = 6개
coins = [500, 100, 50, 10], amount = 17308500×3 + 100×2 + 10×3 = 8개

접근

동전 단위를 큰 것부터 정렬한 뒤, 남은 금액에 큰 단위를 최대한 많이 사용하고 남은 금액으로 다음 단위를 반복합니다. 500, 100, 50, 10원처럼 큰 단위가 작은 단위의 배수인 표준 체계에서는 이 방식이 항상 최소 개수를 만듭니다. 시간 복잡도는 동전 종류 수를 k라 하면 O(k log k)(정렬) + O(k)입니다.

동전 단위가 1, 3, 4원처럼 배수 관계가 아니면 그리디가 최소 개수를 보장하지 못합니다(6원을 그리디로 풀면 4+1+1=3개지만 실제 최소는 3+3=2개). 이런 경우는 13편의 타뷸레이션 DP로 모든 조합을 확인해야 합니다.

풀이

// coding-test/14-greedy/02-min-coin-count/solution.js
// 시간복잡도: O(k log k) — 동전 종류 k개를 내림차순 정렬한다
// 공간복잡도: O(k) — 정렬된 복사본 배열을 만든다
export function solution(coins, amount) {
  const sortedDescending = [...coins].sort((a, b) => b - a);
 
  let remaining = amount;
  let count = 0;
  for (const coin of sortedDescending) {
    if (coin <= remaining) {
      count += Math.floor(remaining / coin);
      remaining %= coin;
    }
  }
  return remaining === 0 ? count : -1;
}

테스트

// coding-test/14-greedy/02-min-coin-count/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
 
test('1260원을 표준 동전 체계로 6개에 만든다', () => {
  assert.strictEqual(solution([500, 100, 50, 10], 1260), 6);
});
 
test('1730원을 표준 동전 체계로 8개에 만든다', () => {
  assert.strictEqual(solution([500, 100, 50, 10], 1730), 8);
});
 
test('금액이 0이면 0개', () => {
  assert.strictEqual(solution([500, 100, 50, 10], 0), 0);
});
 
test('표준 체계가 아니면 그리디가 최소값을 보장하지 못할 수 있다', () => {
  const greedyResult = solution([1, 3, 4], 6);
  assert.strictEqual(greedyResult, 3);
});
node --test coding-test/14-greedy/02-min-coin-count/solution.test.js

함정

  • 동전 단위가 표준 체계(큰 단위가 작은 단위의 배수)인지 확인하지 않고 그리디를 적용하면 틀린 답이 나올 수 있습니다.
  • 정렬을 오름차순으로 하고 그대로 순회하면 작은 단위부터 소진해 개수가 늘어납니다. 반드시 내림차순으로 정렬합니다.

문제 3. 회의를 모두 진행하는 데 필요한 최소 회의실 수

문제 설명

회의 목록이 주어질 때, 겹치는 회의를 동시에 진행할 수 있도록 필요한 최소 회의실 개수를 구합니다(문제 1과 달리 모든 회의를 반드시 진행해야 합니다).

제약값
회의 개수1 이상 1000 이하

입출력 예

입력출력설명
[{start:0,end:30},{start:5,end:10},{start:15,end:20}]2[5,10]과 [15,20]은 [0,30]과 겹치지만 서로는 안 겹침
[{start:7,end:10},{start:2,end:4}]1두 회의가 겹치지 않아 회의실 1개면 충분

접근

시작 시각들과 종료 시각들을 각각 정렬한 뒤, 시작 시각과 종료 시각을 시간 순서대로 훑습니다. 시작 시각이 나오면 회의실이 하나 더 필요하고(rooms += 1), 종료 시각이 먼저 나오면 회의실 하나가 비워집니다(rooms -= 1). 이 과정에서 rooms가 가장 커졌을 때의 값이 필요한 최소 회의실 수입니다. 시작·종료 배열을 각각 정렬하는 데 O(n log n)이 걸립니다.

풀이

// coding-test/14-greedy/03-min-meeting-rooms/solution.js
// 시간복잡도: O(n log n) — 시작·종료 시각을 각각 정렬한다
// 공간복잡도: O(n) — 시작·종료 시각 배열을 따로 만든다
export function solution(meetings) {
  const starts = meetings.map((meeting) => meeting.start).sort((a, b) => a - b);
  const ends = meetings.map((meeting) => meeting.end).sort((a, b) => a - b);
 
  let rooms = 0;
  let maxRooms = 0;
  let startIndex = 0;
  let endIndex = 0;
 
  while (startIndex < starts.length) {
    if (starts[startIndex] < ends[endIndex]) {
      rooms += 1;
      startIndex += 1;
      maxRooms = Math.max(maxRooms, rooms);
    } else {
      rooms -= 1;
      endIndex += 1;
    }
  }
  return maxRooms;
}

테스트

// coding-test/14-greedy/03-min-meeting-rooms/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
 
test('겹치는 구간이 있으면 회의실 2개가 필요하다', () => {
  const meetings = [
    { start: 0, end: 30 },
    { start: 5, end: 10 },
    { start: 15, end: 20 },
  ];
  assert.strictEqual(solution(meetings), 2);
});
 
test('겹치지 않으면 회의실 1개면 충분하다', () => {
  const meetings = [
    { start: 7, end: 10 },
    { start: 2, end: 4 },
  ];
  assert.strictEqual(solution(meetings), 1);
});
 
test('회의가 하나면 회의실 1개', () => {
  assert.strictEqual(solution([{ start: 0, end: 5 }]), 1);
});
node --test coding-test/14-greedy/03-min-meeting-rooms/solution.test.js

함정

  • 문제 1(최대 배정 가능 회의 수)과 혼동하기 쉽습니다. 문제 1은 “일부만 골라 최대한 많이”, 문제 3은 “전부 진행할 최소 자원”으로 목적이 다릅니다.
  • 시작 시각과 종료 시각이 같을 때(starts[i] === ends[j]) 어느 쪽을 먼저 처리할지 문제 조건을 확인합니다. 여기서는 종료 처리를 먼저 해 회의실을 비웁니다(< 비교).

문제 4. 쪼갤 수 있는 물건으로 배낭 가치 최대화

문제 설명

무게와 가치가 정해진 물건 여러 개와 배낭 용량이 주어집니다. 이번에는 물건을 원하는 비율만큼 쪼개서 담을 수 있습니다(부분 배낭 문제). 담은 양의 가치 합을 최대로 만드는 값을 구합니다.

제약값
물건 개수1 이상 100 이하
무게·가치·용량각각 1 이상 1000 이하인 정수

입출력 예

입력출력설명
items = [{weight:10,value:60},{weight:20,value:100},{weight:30,value:120}], capacity=50240무게당 가치가 높은 순서로 담아 최댓값

접근

각 물건의 “무게당 가치”(value / weight)가 높은 물건부터 담는 것이 유리합니다. 물건을 쪼갤 수 있으므로 용량이 남는 한 가장 효율 좋은 물건을 최대한 담고, 마지막 물건은 남은 용량만큼만 비율로 담습니다. 13편의 0/1 냅색과 달리 물건을 쪼갤 수 있어 그리디가 항상 최적해를 보장합니다. 정렬에 O(n log n), 이후 순회에 O(n)이 걸립니다.

풀이

// coding-test/14-greedy/04-fractional-knapsack/solution.js
// 시간복잡도: O(n log n) — 무게당 가치 기준으로 정렬한다
// 공간복잡도: O(n) — 정렬된 복사본 배열을 만든다
export function solution(items, capacity) {
  const sortedByRatio = [...items].sort((a, b) => b.value / b.weight - a.value / a.weight);
 
  let remaining = capacity;
  let totalValue = 0;
 
  for (const { weight, value } of sortedByRatio) {
    if (remaining <= 0) break;
 
    if (weight <= remaining) {
      totalValue += value;
      remaining -= weight;
    } else {
      totalValue += value * (remaining / weight);
      remaining = 0;
    }
  }
  return totalValue;
}

테스트

// coding-test/14-greedy/04-fractional-knapsack/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
 
test('물건을 쪼개 담아 최댓값 240을 만든다', () => {
  const items = [
    { weight: 10, value: 60 },
    { weight: 20, value: 100 },
    { weight: 30, value: 120 },
  ];
  assert.strictEqual(solution(items, 50), 240);
});
 
test('용량이 전체 무게보다 크면 가치 합 전체를 담는다', () => {
  const items = [
    { weight: 10, value: 60 },
    { weight: 20, value: 100 },
  ];
  assert.strictEqual(solution(items, 100), 160);
});
 
test('용량이 0이면 가치도 0', () => {
  const items = [{ weight: 10, value: 60 }];
  assert.strictEqual(solution(items, 0), 0);
});
node --test coding-test/14-greedy/04-fractional-knapsack/solution.test.js

함정

  • 가치(value)만 보고 정렬하면 틀립니다. 반드시 무게당 가치(value / weight) 비율로 정렬해야 합니다.
  • 0/1 냅색(13편)과 이 문제를 같은 방식으로 풀면 안 됩니다. 물건을 쪼갤 수 없는 문제에 그리디를 적용하면 최적해를 놓칠 수 있습니다.

직접 해보기

  1. 문제 2의 solution(minCoinCount)에 표준이 아닌 동전 체계 [1, 3, 4]와 금액 6을 넣었을 때 그리디 결과(3개)와 13편 방식의 DP로 구한 최소 개수(2개)를 직접 비교하는 테스트를 추가해봅니다.
  2. 문제 1의 solution(maxNonOverlappingMeetings)을 시작 시각 기준 정렬로 바꿔서 실행해보고, 문제 1의 입출력 예에서 결과가 달라지는지 확인해봅니다.

정답 보기(1번)

// coding-test/14-greedy/02-min-coin-count/solution.test.js (추가)
test('표준이 아닌 동전 체계에서는 그리디와 DP 결과가 다를 수 있다', () => {
  const greedyResult = solution([1, 3, 4], 6);
  assert.strictEqual(greedyResult, 3);
 
  // 13편에서 만든 타뷸레이션 DP로 최소 동전 개수를 구하면 2개(3+3)가 나온다.
  // 이 테스트는 그리디가 항상 최적해를 보장하지는 않는다는 것을 보여주기 위한 것으로,
  // 실제 최소 개수를 구하려면 별도의 DP 함수를 작성해야 한다.
});

동전 체계가 표준(배수 관계)이 아니면 그리디만으로는 부족합니다. 실전에서는 문제의 동전 단위 목록을 보고 표준 체계인지 먼저 판단해야 합니다.

자주 하는 실수

증상원인고치는 법
정렬 기준을 잘못 선택해 결과가 틀림”무엇을 기준으로 먼저 선택해야 유리한지” 검증 없이 정렬작은 반례를 손으로 만들어 정렬 기준을 먼저 확인한다
동전 체계가 표준이 아닌데 그리디를 적용그리디가 항상 최적해를 보장한다고 착각배수 관계가 아니면 13편의 DP로 전환한다
물건을 쪼갤 수 없는 문제에 무게당 가치 그리디를 적용부분 배낭과 0/1 냅색을 혼동문제에서 “쪼갤 수 있는지” 여부를 먼저 확인한다
경계값(시작과 끝이 같은 시각)에서 결과가 문제와 다름>=와 > 비교 연산자를 문제 조건과 다르게 사용문제의 예시로 경계값을 직접 대입해 확인한다

확인 문제

문제 14지선다
그리디 알고리즘이 DP와 다른 점으로 가장 알맞은 것은?
문제 24지선다
회의실 배정 문제(문제 1)에서 종료 시각 기준으로 정렬해야 하는 이유는?
문제 34지선다
동전 단위가 1, 3, 4원처럼 배수 관계가 아닐 때 그리디로 거스름돈을 구하면 어떤 문제가 생기는가?
문제 44지선다
부분 배낭 문제(문제 4)에서 물건을 무게당 가치(value / weight) 순으로 정렬해 담는 방식이 항상 최적해가 되는 이유는?

참고 자료

Last updated on
13. 동적 계획법(DP)15. 구현·시뮬레이션