[코딩 테스트] 21일차: 그리디 알고리즘 문제

그리디 알고리즘 문제

이번 글에서는 그리디 알고리즘을 이용한 문제 해결 방법에 대해 다뤄보겠습니다. 주로 거스름돈 문제와 활동 선택 문제를 예제로 사용하여 그리디 알고리즘의 적용 방법을 이해하겠습니다.

거스름돈 문제

거스름돈 문제는 가장 적은 수의 동전으로 거스름돈을 주는 방법을 찾는 문제입니다. 그리디 알고리즘을 이용하여 가장 큰 단위의 동전부터 거슬러주면 됩니다.

 

예제: 거스름돈 문제 구현

JavaScript

function minCoins(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (let coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

const coins = [1, 5, 10, 25];
const amount = 63;
console.log(minCoins(coins, amount)); // 6 (25 + 25 + 10 + 1 + 1 + 1)

Python

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

coins = [1, 5, 10, 25]
amount = 63
print(min_coins(coins, amount)) # 6 (25 + 25 + 10 + 1 + 1 + 1)

활동 선택 문제

활동 선택 문제는 시작 시간과 종료 시간이 주어진 여러 활동 중에서 서로 겹치지 않게 최대한 많은 활동을 선택하는 문제입니다. 그리디 알고리즘을 이용하여 종료 시간이 빠른 활동부터 선택하면 됩니다.

 

예제: 활동 선택 문제 구현

JavaScript

function activitySelection(start, end) {
  const activities = [];
  for (let i = 0; i < start.length; i++) {
    activities.push({ start: start[i], end: end[i] });
  }
  activities.sort((a, b) => a.end - b.end);

  const selected = [];
  let lastEnd = 0;

  for (let activity of activities) {
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }

  return selected;
}

const start = [1, 3, 0, 5, 8, 5];
const end = [2, 4, 6, 7, 9, 9];
console.log(activitySelection(start, end)); // [{start: 1, end: 2}, {start: 3, end: 4}, {start: 5, end: 7}, {start: 8, end: 9}]

Python

def activity_selection(start, end):
    activities = sorted(zip(start, end), key=lambda x: x[1])
    selected = []
    last_end = 0

    for activity in activities:
        if activity[0] >= last_end:
            selected.append(activity)
            last_end = activity[1]

    return selected

start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, end)) # [(1, 2), (3, 4), (5, 7), (8, 9)]

연습 문제

문제 1: 최소 화폐 개수 구하기

주어진 금액을 거슬러 주기 위해 필요한 최소 화폐 개수를 구하는 프로그램을 작성하세요.

JavaScript

function minCoins(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (let coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

const coins = [1, 5, 10, 25];
const amount = 87;
console.log(minCoins(coins, amount)); // 6 (25 + 25 + 25 + 10 + 1 + 1)

Python

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

coins = [1, 5, 10, 25]
amount = 87
print(min_coins(coins, amount)) # 6 (25 + 25 + 25 + 10 + 1 + 1)

문제 2: 회의실 배정

회의실 사용 시간을 나타내는 시작 시간과 종료 시간이 주어질 때, 회의가 겹치지 않도록 하기 위해 필요한 최소 회의실 수를 구하는 프로그램을 작성하세요.

JavaScript

function minMeetingRooms(intervals) {
  const starts = intervals.map(interval => interval[0]).sort((a, b) => a - b);
  const ends = intervals.map(interval => interval[1]).sort((a, b) => a - b);

  let rooms = 0;
  let endPointer = 0;

  for (let start of starts) {
    if (start < ends[endPointer]) {
      rooms++;
    } else {
      endPointer++;
    }
  }

  return rooms;
}

const intervals = [[0, 30], [5, 10], [15, 20]];
console.log(minMeetingRooms(intervals)); // 2

Python

def min_meeting_rooms(intervals):
    starts = sorted([interval[0] for interval in intervals])
    ends = sorted([interval[1] for interval in intervals])

    rooms = 0
    end_pointer = 0

    for start in starts:
        if start < ends[end_pointer]:
            rooms += 1
        else:
            end_pointer += 1

    return rooms

intervals = [[0, 30], [5, 10], [15, 20]]
print(min_meeting_rooms(intervals)) # 2

결론

이번 글에서는 코딩 테스트 준비를 위해 그리디 알고리즘 문제에 대해 배웠습니다. 이를 통해 거스름돈 문제, 활동 선택 문제의 구현 방법을 익혔습니다. 다음 글에서는 수학 문제에 대해 알아보겠습니다.

다음 글에서 만나요!