[코딩테스트] 6주차: 탐욕 알고리즘과 최적화

탐욕 알고리즘과 최적화

학습 주제

• 탐욕 알고리즘의 개념과 적용 방법
• 탐욕 알고리즘을 사용한 문제 풀이 (활동 선택 문제, 최소 신장 트리 - Kruskal, Prim)

학습 목표

• 탐욕 알고리즘의 원리를 이해하고 다양한 문제에 적용할 수 있다.
• 탐욕 알고리즘을 사용하여 최적의 해를 찾는 문제를 해결할 수 있다.
• 활동 선택 문제, 최소 신장 트리 등의 대표적인 탐욕 알고리즘 문제를 해결할 수 있다.

학습 자료

• 탐욕 알고리즘 개요와 원리
• 활동 선택 문제 설명 및 구현
• 최소 신장 트리 알고리즘 (Kruskal, Prim) 설명 및 구현

실습 문제

1. 활동 선택 문제

• 주어진 활동들의 시작 시간과 종료 시간을 기반으로 최대한 많은 활동을 선택하는 문제를 탐욕 알고리즘을 사용하여 해결하는 함수를 작성하세요.

def activity_selection(start, finish):
    n = len(finish)
    selected_activities = []

    # 첫 번째 활동을 선택합니다.
    i = 0
    selected_activities.append(i)

    for j in range(1, n):
        if start[j] >= finish[i]:
            selected_activities.append(j)
            i = j

    return selected_activities

# Test
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
selected_activities = activity_selection(start, finish)
print(f"Selected activities: {selected_activities}")
# Output: Selected activities: [0, 1, 3, 4]

 

2. 최소 신장 트리 (Kruskal 알고리즘)

• 주어진 그래프에 대해 Kruskal 알고리즘을 사용하여 최소 신장 트리를 찾는 함수를 작성하세요.

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

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

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal_mst(self):
        result = []
        i, e = 0, 0

        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# Test
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

mst = g.kruskal_mst()
print("Edges in the constructed MST:")
for u, v, weight in mst:
    print(f"{u} -- {v} == {weight}")
# Output:
# Edges in the constructed MST:
# 2 -- 3 == 4
# 0 -- 3 == 5
# 0 -- 1 == 10

 

3. 최소 신장 트리 (Prim 알고리즘)

• 주어진 그래프에 대해 Prim 알고리즘을 사용하여 최소 신장 트리를 찾는 함수를 작성하세요.

import heapq

def prim_mst(graph):
    V = len(graph)
    selected = [False] * V
    num_edges = 0
    selected[0] = True
    pq = []

    for i in range(1, V):
        if graph[0][i] != 0:
            heapq.heappush(pq, (graph[0][i], 0, i))

    mst = []

    while pq and num_edges < V - 1:
        weight, u, v = heapq.heappop(pq)
        if not selected[v]:
            selected[v] = True
            mst.append((u, v, weight))
            num_edges += 1
            for i in range(V):
                if not selected[i] and graph[v][i] != 0:
                    heapq.heappush(pq, (graph[v][i], v, i))

    return mst

# Test
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
mst = prim_mst(graph)
print("Edges in the constructed MST:")
for u, v, weight in mst:
    print(f"{u} -- {v} == {weight}")
# Output:
# Edges in the constructed MST:
# 0 -- 1 == 2
# 1 -- 2 == 3
# 0 -- 3 == 6
# 1 -- 4 == 5

 

추가 학습 자료:

• Greedy Algorithms - GeeksforGeeks
• Activity Selection Problem - GeeksforGeeks
• Kruskal's Algorithm - GeeksforGeeks
• Prim's Algorithm - GeeksforGeeks

---

추천 문제

백준 (Baekjoon)

1. 문제명: 회의실 배정
   • 설명: 주어진 회의 일정에서 최대한 많은 회의를 배정할 수 있는 방법을 찾는 문제입니다.
   • 문제 유형: 탐욕 알고리즘
   • 난이도: 실버 I
   • 주소: 회의실 배정
2. 문제명: 최소 회의실 개수
   • 설명: 주어진 회의 일정에서 필요한 최소 회의실 개수를 구하는 문제입니다.
   • 문제 유형: 탐욕 알고리즘
   • 난이도: 골드 II
   • 주소: 최소 회의실 개수
3. 문제명: 전깃줄
   • 설명: 전봇대 사이에 연결된 전깃줄이 교차하지 않도록 최대한 많이 설치하는 문제입니다.
   • 문제 유형: 탐욕 알고리즘, 동적 프로그래밍
   • 난이도: 골드 V
   • 주소: 전깃줄

프로그래머스 (Programmers)

1. 문제명: 체육복
   • 설명: 도난당한 체육복을 기준으로 학생들이 체육복을 빌려주고 받을 수 있는 최대 학생 수를 구하는 문제입니다.
   • 문제 유형: 탐욕 알고리즘
   • 난이도: 레벨 1
   • 주소: 체육복
2. 문제명: 큰 수 만들기
   • 설명: 주어진 숫자 문자열에서 k개의 숫자를 제거하여 만들 수 있는 가장 큰 숫자를 찾는 문제입니다.
   • 문제 유형: 탐욕 알고리즘
   • 난이도: 레벨 2
   • 주소: 큰 수 만들기
3. 문제명: 구명보트
   • 설명: 제한된 구명보트로 사람들을 구출할 때 필요한 최소 구명보트 개수를 구하는 문제입니다.
   • 문제 유형: 탐욕 알고리즘
   • 난이도: 레벨 2
   • 주소: 구명보트