[코딩 테스트] 19일차: 탐욕 알고리즘

탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘은 매 순간 가장 최적이라고 생각되는 해를 선택하여 문제를 해결하는 방법입니다. 이 방법은 부분적인 최적 해가 전체적인 최적 해가 될 수 있는 문제에 적합합니다. 탐욕 알고리즘은 주로 최적화 문제에 사용됩니다.

탐욕 알고리즘의 주요 개념

• 현재 시점에서 가장 좋은 선택: 각 단계에서 가장 좋은 선택을 하여 문제를 해결
• 부분 최적 해: 각 부분 문제에서의 최적 해가 전체 문제에서도 최적 해가 되는 경우

활동 선택 문제 (Activity Selection Problem)

활동 선택 문제는 시작 시간과 종료 시간이 주어진 여러 활동 중에서 서로 겹치지 않게 최대한 많은 활동을 선택하는 문제입니다. 탐욕 알고리즘을 이용하여 해결할 수 있습니다.

 

예제: 활동 선택 문제 구현

JavaScript

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

  activities.sort((a, b) => a.end - b.end);

  const selectedActivities = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < n; i++) {
    if (activities[i].start >= lastEnd) {
      selectedActivities.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }

  return selectedActivities;
}

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 = list(zip(start, end))
    activities.sort(key=lambda x: x[1])

    selected_activities = [activities[0]]
    last_end = activities[0][1]

    for i in range(1, len(activities)):
        if activities[i][0] >= last_end:
            selected_activities.append(activities[i])
            last_end = activities[i][1]

    return selected_activities

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)]

배낭 문제 (Knapsack Problem)

배낭 문제는 주어진 무게 제한을 초과하지 않으면서 최대 가치를 얻을 수 있는 아이템의 조합을 찾는 문제입니다. 탐욕 알고리즘을 이용한 방법으로는 '분수 배낭 문제'가 있습니다.

 

예제: 분수 배낭 문제 구현

JavaScript

function fractionalKnapsack(values, weights, capacity) {
  const n = values.length;
  const items = [];
  for (let i = 0; i < n; i++) {
    items.push({ value: values[i], weight: weights[i], ratio: values[i] / weights[i] });
  }

  items.sort((a, b) => b.ratio - a.ratio);

  let totalValue = 0;
  let remainingCapacity = capacity;

  for (let i = 0; i < n; i++) {
    if (items[i].weight <= remainingCapacity) {
      totalValue += items[i].value;
      remainingCapacity -= items[i].weight;
    } else {
      totalValue += items[i].value * (remainingCapacity / items[i].weight);
      break;
    }
  }

  return totalValue;
}

const values = [60, 100, 120];
const weights = [10, 20, 30];
const capacity = 50;
console.log(fractionalKnapsack(values, weights, capacity)); // 240

Python

def fractional_knapsack(values, weights, capacity):
    items = sorted(zip(values, weights), key=lambda x: x[0] / x[1], reverse=True)

    total_value = 0
    remaining_capacity = capacity

    for value, weight in items:
        if weight <= remaining_capacity:
            total_value += value
            remaining_capacity -= weight
        else:
            total_value += value * (remaining_capacity / weight)
            break

    return total_value

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity)) # 240

연습 문제

문제 1: 최소 회의실 수 구하기

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

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

문제 2: 최대 이익 구하기

주어진 이익과 작업 시간이 주어질 때, 최대 이익을 구하는 프로그램을 작성하세요.

JavaScript

function jobScheduling(jobs) {
  jobs.sort((a, b) => b.profit - a.profit);
  let maxDeadline = Math.max(...jobs.map(job => job.deadline));
  let result = Array(maxDeadline).fill(null);
  let totalProfit = 0;

  for (let job of jobs) {
    for (let i = job.deadline - 1; i >= 0; i--) {
      if (result[i] === null) {
        result[i] = job;
        totalProfit += job.profit;
        break;
      }
    }
  }

  return totalProfit;
}

let jobs = [
  { deadline: 2, profit: 100 },
  { deadline: 1, profit: 19 },
  { deadline: 2, profit: 27 },
  { deadline: 1, profit: 25 },
  { deadline: 3, profit: 15 }
];

console.log(jobScheduling(jobs)); // 142

Python

def job_scheduling(jobs):
    jobs.sort(key=lambda x: x[1], reverse=True)
    max_deadline = max(job[0] for job in jobs)
    result = [None] * max_deadline
    total_profit = 0

    for job in jobs:
        deadline, profit = job
        for i in range(deadline - 1, -1, -1):
            if result[i] is None:
                result[i] = job
                total_profit += profit
                break

    return total_profit

jobs = [
    (2, 100),
    (1, 19),
    (2, 27),
    (1, 25),
    (3, 15)
]

print(job_scheduling(jobs)) # 142

결론

이번 글에서는 코딩 테스트 준비를 위해 탐욕 알고리즘에 대해 배웠습니다. 이를 통해 탐욕 알고리즘의 개념, 활동 선택 문제, 분수 배낭 문제의 구현 방법을 익혔습니다. 다음 글에서는 동적 프로그래밍에 대해 알아보겠습니다.

다음 글에서 만나요!