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

그리디 알고리즘 (Greedy Algorithm)

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

그리디 알고리즘의 주요 개념

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

최소 신장 트리 (MST)

최소 신장 트리는 그래프의 모든 정점을 포함하면서, 사이클이 없고, 간선의 가중치 합이 최소인 트리입니다. 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 모든 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 신장 트리를 구성하는 알고리즘입니다.

 

예제: 크루스칼 알고리즘 구현

JavaScript

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill(null).map((_, index) => index);
  }

  find(x) {
    if (this.parent[x] === x) {
      return x;
    }
    return this.parent[x] = this.find(this.parent[x]);
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      this.parent[rootX] = rootY;
    }
  }
}

function kruskal(vertices, edges) {
  const mst = [];
  const uf = new UnionFind(vertices.length);

  edges.sort((a, b) => a[2] - b[2]);

  for (const [u, v, weight] of edges) {
    if (uf.find(u) !== uf.find(v)) {
      uf.union(u, v);
      mst.push([u, v, weight]);
    }
  }

  return mst;
}

const vertices = [0, 1, 2, 3, 4];
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

console.log(kruskal(vertices, edges)); // [[2, 3, 4], [0, 3, 5], [0, 1, 10], [1, 3, 15]]

Python

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y

def kruskal(vertices, edges):
    mst = []
    uf = UnionFind(len(vertices))

    edges.sort(key=lambda x: x[2])

    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append([u, v, weight])

    return mst

vertices = [0, 1, 2, 3, 4]
edges = [
    [0, 1, 10],
    [0, 2, 6],
    [0, 3, 5],
    [1, 3, 15],
    [2, 3, 4]
]

print(kruskal(vertices, edges)) # [[2, 3, 4], [0, 3, 5], [0, 1, 10], [1, 3, 15]]

프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 하나의 정점에서 시작하여 인접한 간선 중 최소 가중치를 선택하여 최소 신장 트리를 확장하는 방식입니다.

 

예제: 프림 알고리즘 구현

JavaScript

function prim(vertices, edges) {
  const adjList = new Map();
  vertices.forEach(v => adjList.set(v, []));
  edges.forEach(([u, v, weight]) => {
    adjList.get(u).push([v, weight]);
    adjList.get(v).push([u, weight]);
  });

  const mst = [];
  const visited = new Set();
  const pq = new MinPriorityQueue({ priority: x => x[1] });

  const startVertex = vertices[0];
  visited.add(startVertex);
  adjList.get(startVertex).forEach(([v, weight]) => pq.enqueue([startVertex, v, weight]));

  while (!pq.isEmpty()) {
    const [u, v, weight] = pq.dequeue().element;
    if (!visited.has(v)) {
      visited.add(v);
      mst.push([u, v, weight]);
      adjList.get(v).forEach(([nextV, nextWeight]) => {
        if (!visited.has(nextV)) {
          pq.enqueue([v, nextV, nextWeight]);
        }
      });
    }
  }

  return mst;
}

const vertices = [0, 1, 2, 3, 4];
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

console.log(prim(vertices, edges)); // [[0, 3, 5], [3, 2, 4], [0, 1, 10], [3, 1, 15]]

Python

import heapq

def prim(vertices, edges):
    adj_list = {v: [] for v in vertices}
    for u, v, weight in edges:
        adj_list[u].append((v, weight))
        adj_list[v].append((u, weight))

    mst = []
    visited = set()
    pq = [(0, vertices[0], vertices[0])]

    while pq:
        weight, u, v = heapq.heappop(pq)
        if v not in visited:
            visited.add(v)
            if u != v:
                mst.append((u, v, weight))
            for next_v, next_weight in adj_list[v]:
                if next_v not in visited:
                    heapq.heappush(pq, (next_weight, v, next_v))

    return mst

vertices = [0, 1, 2, 3, 4]
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

print(prim(vertices, edges)) # [(0, 3, 5), (3, 2, 4), (0, 1, 10), (3, 1, 15)]

최단 경로 알고리즘

다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 그래프에서 사용되며, 우선순위 큐를 이용해 구현할 수 있습니다.

 

예제: 다익스트라 알고리즘 구현

JavaScript

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element, priority) {
    let queueElement = { element, priority };
    let added = false;

    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }

  dequeue() {
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

function dijkstra(vertices, edges, start) {
  const adjList = new Map();
  vertices.forEach(v => adjList.set(v, []));
  edges.forEach(([u, v, weight]) => {
    adjList.get(u).push([v, weight]);
    adjList.get(v).push([u, weight]);
  });

  const distances = {};
  vertices.forEach(v => distances[v] = Infinity);
  distances[start] = 0;

  const pq = new PriorityQueue();


 pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { element: current } = pq.dequeue();

    adjList.get(current).forEach(([neighbor, weight]) => {
      const distance = distances[current] + weight;
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        pq.enqueue(neighbor, distance);
      }
    });
  }

  return distances;
}

const vertices = [0, 1, 2, 3, 4];
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

console.log(dijkstra(vertices, edges, 0)); // { '0': 0, '1': 10, '2': 6, '3': 5, '4': Infinity }

Python

import heapq

def dijkstra(vertices, edges, start):
    adj_list = {v: [] for v in vertices}
    for u, v, weight in edges:
        adj_list[u].append((v, weight))
        adj_list[v].append((u, weight))

    distances = {v: float('inf') for v in vertices}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in adj_list[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

vertices = [0, 1, 2, 3, 4]
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

print(dijkstra(vertices, edges, 0)) # {0: 0, 1: 10, 2: 6, 3: 5, 4: inf}

연습 문제

문제 1: 최소 코인 개수 구하기

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

JavaScript

function minCoins(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

let coins = [1, 2, 5];
let amount = 11;
console.log(minCoins(coins, amount)); // 3

Python

def min_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
amount = 11
print(min_coins(coins, amount)) # 3

문제 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

결론

이번 글에서는 코딩 테스트 준비를 위해 그리디 알고리즘에 대해 배웠습니다. 이를 통해 그리디 알고리즘의 개념, 최소 신장 트리(MST) 알고리즘, 다익스트라 알고리즘, 그리고 다양한 예제를 통해 그리디 알고리즘 문제를 해결하는 방법을 익혔습니다. 다음 글에서는 트리 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!