Skip to main content
HashnodeMy dev journey

Command Palette

Search for a command to run...

Advanced Study of Greedy Algorithms and Matroids

Updated
•38 min read
Advanced Study of Greedy Algorithms and Matroids
H
Heesu Noh
Part of seriesComputer Algorithms

Contents

1️⃣그리디 알고리즘(탐욕법)의 특징 (Overview of Greedy Algorithms)
2️⃣그리디 알고리즘의 예 (Example of Greedy Algorithms)
3️⃣그리디 알고리즘의 최적해 조건 (Conditions for Optimal Solution with Greedy Algorithm)
4️⃣ 그리디 알고리즘 문제 (Example of Greedy Algorithms)
5️⃣매트로이드 (Matroid)
6️⃣매트로이드의 확장(Matroid Expansion)
7️⃣ 문제 공간 탐색 (Problem Space Exploration)

오늘은 그리디 알고리즘에 대해서 배워볼 예정이다. 그리디 알고리즘의 특징에 대해서 먼저 알아본다. 그리디는 “탐욕”이라는 뜻으로 빠른시간에 높은 성능을 보이도록 하기 위해 이것저것 따지지 않고 그대로 현재 시점에서 가장 좋은 옵션을 찾아 나가는 방식이다. "현재 시점" 만 보기떄문에 시야가 좁은 알고리즘이다. 대부분 "최적해"와는 거리가 있다. 하지만 드물게 최적해가 보장되는 경우도 있다. 그 예로는 프림, 크루스칼알고리즘이 있다. 다익스트라 알고리즘도 마찬가지로 최소의 비용을 찾아가는 과정에서 최적해를 보장한다.

1️⃣그리디 알고리즘(탐욕법)의 특징(Overview of Greedy Algorithms)

✅ 그리디 알고리즘의 정의와 특징

  • 그리디 (Greedy)는 탐욕이라는 뜻으로, 매 순간 가장 좋아 보이는 옵션을 선택하는 방식이다.

  • 이 알고리즘은 현재 시점 (current state)만 고려하며, 시야가 좁다 (limited view)는 특징을 가진다.

  • 따라서 대부분의 경우 전체 최적해 (global optimum)를 놓칠 가능성이 높다.

  • 하지만 특정 상황에서는 최적해를 보장할 수 있는데, 그리디 알고리즘의 빠른 성능 (high performance)이 강점으로 작용한다.

  • 어떤 특정 상황인지는 아래 장단점에서 언급하였다.

✅작동 방식: 그리디 알고리즘은 다음과 같이 작동한다.

  •   do {
      우선 가장 좋아보이는 선택을 한다.
  } until (해 구성 완료)

  • 현재 시점 (current state)에서 반복적으로 가장 좋은 선택을 수행한다.

  • 모든 선택이 완료되면 알고리즘이 종료된다.

✅장점과 단점

  • 장점 (Advantages):

    • 빠른 결과를 도출할 수 있다.

    • 특정 문제(예: 프림 알고리즘 (Prim Algorithm), 크루스칼 알고리즘 (Kruskal Algorithm), 다익스트라 알고리즘 (Dijkstra Algorithm))에서 최적해를 보장 (guarantee optimal solution)할 수 있다. 성능도 빠르고 최적해를 찾을 수 있기 때문에 위 알고리즘들이 좋은 알고리즘으로 평가되는 이유이다.

  • 단점 (Disadvantages):

    • 그래프로 표현시, 전체적인 시야 (global perspective)를 보지 못해서 중간의 작은 봉우리 (local peak)나 골 (valley)에서 이를 최적해로 인식하기 때문에 전체 최적해를 놓치게 된다.

    • 예를 들어, 그래프에서 전체 최적해 대신 국소적인 최적해를 선택할 위험이 있다.

✅ 실제 예시

  • 프림 알고리즘 (Prim Algorithm)과 크루스칼 알고리즘 (Kruskal Algorithm): 최소 비용 신장 트리(MST, Minimum Spanning Tree) 를 찾는 과정에서 그리디 방식을 사용하며 최적해를 보장한다.

  • 다익스트라 알고리즘 (Dijkstra Algorithm): 그래프에서 최소 비용 경로(minimum cost path)를 찾는 문제에서 사용되며, 최적해를 제공한다.

✅그리디 알고리즘의 국소적 최적화 (Greedy Algorithm - Local Optimization)

💡정리: 그리디 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하지만, 국소적 최소값을 선택하여 전체 최적 해(전체 최소값)를 보장하지 못할 수 있다. 단, 문제가 전역 최적 해와 국소 최적 해가 동일한 구조(예: 포물선 형태)라면 효과적다.

  • 그래프는 여러 봉우리(peak)와 골짜기(valley)를 가진 곡선을 보여주며, 이는 가능한 해(solution)를 나타낸다.

    • 전체 최대값 (Global Maximum): 그래프에서 가장 높은 지점.

    • 국소 최대값 (Local Maximum): 주변 지점들보다 높지만 전체에서 가장 높지는 않은 봉우리.

    • 전체 최소값 (Global Minimum): 그래프에서 가장 낮은 지점.

    • 국소 최소값 (Local Minimum): 주변 지점들보다 낮지만 전체에서 가장 낮지는 않은 골짜기. 그리디 알고리즘은 이 단계에서 최적이라고 판단되는 선택을 하기 때문에 전체 최적해를 놓치는 경우가 많다.

  • 그래프의 맨 아래에 있는 전체 최소값 (global minimum)가 전체 최적해이다.

  • 전체 최적해(Global Optimal Solution)란, 문제의 모든 가능한 해 중에서 가장 최적(최대 또는 최소)의 값을 가지는 해를 의미한다.

  • 최적해 (optimal solution)를 보장하려면 전체 해 공간이 단순해야 하며, 포물선 형태 (parabolic space)인 경우 그리디 알고리즘이 올바른 최적화를 보장하 게 된다.

  • 혹은 골 (valley)이 하나뿐이거나, 해 공간이 단일 봉우리 (single peak)로 이루어진 문제는 그리디 알고리즘으로 해결 가능하다.

💡 중요한 포인트

  1. 빠른 성능 (High performance): 이것저것 따지지 않고 빠르게 해를 구할 수 있음.

  2. 시야 제한 (Limited view): 전체 최적해를 놓칠 가능성이 큼.

  3. 최적해 보장 조건 (Conditions for optimality): 해 공간이 단순한 구조일 때 가능.

그리디 알고리즘 #1: 과정 (Steps in Greedy Algorithm)

💡핵심은 현재 순간의 최적 해를 선택하고, 이를 점진적으로 전체 해로 확장하는 방식이다.

1. 해 선택 (Select Solution)

  • 현재 시점에서 가장 최선이라고 판단되는 해를 선택한다.

  • 이는 위에서 언급된 국소 최적화(Local Optimization) 접근 방식으로, 문제 해결의 첫 번째 단계이다.

  • 예를 들어, 다익스트라 알고리즘에서는 출발점에서 각 지점까지의 최소 비용을 계산하며 가장 작은 비용을 가진 노드를 선택하게 되는데 현재 시점에서 가장 최선이라고 판단하여 선택하게 되었다.

2. 적절성 검사 (Feasibility Check)

  • 선택한 해가 전체 문제의 제약 조건(constrains)에 맞는지를 검사하게 된다.

  • 제약 조건을 통과하면 다음 단계로 진행하는데, 만약 제약 조건에 맞지 않으면 선택한 해를 제외하거나 다시 수정해야 한다.

3. 해 검사 (Solution Validation)

  • 현재까지 선택한 해가 전체 해의 일부가 되는지 확인한다.

  • 조건에 맞으면 해를 계속 추가하여 다음 단계로 진행한다.

  • 만약 맞지 않다면 (조건 불충족) 다시 이전 단계로 돌아가 반복하게 된다.

  • 예:

    • 다익스트라 알고리즘 (Dijkstra Algorithm): 출발점에서 특정 지점까지의 비용을 계산하며, 새로운 노드를 선택하고 비용을 업데이트하는 경우

    • 크루스칼 알고리즘 (Kruskal Algorithm): 최소 비용 간선을 선택하며, 사이클을 생성하지 않는지 확인 후 간선을 추가한다.

    • 프림 알고리즘 (Prim Algorithm): 현재까지 선택된 정점 집합에서 최소 비용으로 연결되는 간선을 추가한다.

4. 종료 (Termination)

  • 모든 정점이나 노드를 포함하면 알고리즘이 종료된다. 그 전까지는 새로운 해를 선택하고 적절성을 검사하며 최종 해를 찾는다.

  • 최종 해 (final solution)를 출력한다.

  • 예:

    • 다익스트라 알고리즘: 모든 노드에 대한 최소 비용이 계산되면 종료된다.

    • 크루스칼/프림 알고리즘: 모든 정점이 연결된 최소 신장 트리 (minimum spanning tree)가 완성되면 종료된다.

핵심 포인트 (Key Points)

  1. 해 선택 (Solution Selection): 현재 시점에서 가장 좋은 옵션을 선택한다.

  2. 적절성 검사 (Feasibility): 제약 조건에 맞는지 확인한다.

  3. 해 추가 (Solution Expansion): 조건을 만족하면 해를 계속 확장한다.

  4. 종료 (Termination): 모든 요소가 포함되면 전체 해를 출력하고 종료하게 된다.

✅ 그리디 알고리즘의 전형적인 구조 의사코드 (Typical Structure of Greedy Algorithm)

  1. 초기화 (Initialization):

    • S ← ∅ 해집합 S를 공집합으로 설정한다. C는 선택 가능한 원소들의 집합이.

    • S는 선택된 원소들의 집합으로, 초기에는 비어 있게된다(공집합 상태)

  2. 반복 조건(while statement condition): 알고리즘은 다음 두 조건을 만족할 때까지 반복하게 된다.

    • C ≠ ∅ (원소를 선택할 수 있는 집합이 비어 있지 않음).

    • S가 아직 온전한 해(완전한 솔루션)가 아님.

  3. 현재 최선의 원소 선택 (Element Selection):

    • x ← C에서 원소 하나 선택: C에서 현재 시점에서 가장 좋은 해 (best solution)로 판단되는 x를 선택한다.

    • 이 선택은 현재 시점에서 가장 유리한 선택을 의미한다.

    • 예: 최소 비용 노드, 최대 이익 간선 등.

  4. 원소 제거 (Remove element): C ← C - {x}

    • 현재 시점에서 가장 좋은 해 (best solution)로 판단되는 x를 집합 C에서 제거한다.

  5. 조건 검사 및 해 집합 추가: S ← S ∪ {x}

    • 만약 S에 x를 더해도 문제가 없으면, x를 해 집합 S에 추가한다.

  6. 검사와 종료 (Validation and Termination):

    • S가 온전한 해(전체 문제의 해결)를 구성하면 S를 반환한다.

    • C에 더 이상 선택할 원소가 없거나 반복문이 끝났음에도 온전한 해를 찾지 못하면 "해 없음!"을 반환하게 된다.

💡중요한 부분 (Key Highlights)

  1. 현재 시점에서 최선의 선택 (Best Choice at Current State) a.k.a 탐욕적 선택 (Greedy Choice)

    • 핵심은 반복문 안에서 x를 선택할 때, 현재 시점에서 가장 최선의 옵션을 고르는 것

  2. 집합 이동의 의미 (Transition Between Sets):

    • C는 아직 방문하지 않은 원소 집합, S는 이미 선택된 원소 집합으로 간주된다.

    • 선택한 원소는 C에서 S로 옮겨진다.

  3. 반복 (Iteration):

    • 이 과정을 계속 반복하며 S가 전체 해가 될 때까지 진행한다.

2️⃣그리디 알고리즘의 예

이제 그리디 알고리즘의 최적해를 보장할때 사용하는 프림 알고리즘의 작동원리에 대해 알아본다.

그리디 알고리즘의 예 #1 : 최적해 보장하는 프림 알고리즘 (Example of Optimal Solution in Greedy Algorithm - Prim Algorithm)

✅프림 알고리즘의 특징 (Characteristics of Prim Algorithm)

  1. 탐색 범위 제한 (Limited Search Scope):

    • 현재 연결된 노드와 인접한 간선만 탐색한다.

    • 그래프가 크거나 복잡해도 효율적으로 작동한다.

    • 이렇게 함으로써 최적해를 구성하는 선택이 각 단계에서 국소적으로도 최적임을 보장한다.

    • 즉, 부분적으로 최적이면 점진적으로 전체 최적해를 구성할 수 있다는 뜻이다.

  2. 가중치 기준 선택 (Weight-Based Selection):

    • 각 단계에서 가장 낮은 가중치를 가진 간선을 선택하여 진행한다.

  3. 최적해 보장 (Guarantee of Optimal Solution):

    • 모든 노드를 연결할 때, 최소 가중치로 연결된 신장 트리를 생성하게 된다.

  • 시작 노드: 0번 노드

  • 연결된 노드와 가중치: 8번(8), 9번(9), 11번(11)

  • 선택된 노드: 가장 낮은 가중치를 가진 8번 노드

  • 다음 단계: 8번 노드가 현재 시점이 되며, 인접 노드의 가중치를 업데이트.

1. 초기화 (Initialization):

  • 시작 노드(예: 0번 노드)에서 출발한다.

  • 모든 노드의 가중치를 무한대(∞)로 초기화하였다.

  • 시작 노드와 연결된 노드들의 가중치를 확인한다.

2. 해 선택 (Selection of Solution):

  • 시작 노드(0번)와 연결된 8, 9, 11번 노드의 가중치를 탐색한다.

  • 가중치: 8번 노드: 8, 9번 노드: 9, 11번 노드: 11

  • 이 중에서 가장 낮은 가중치를 가진 8번 노드를 선택한다.

3. 반복 (Iteration):

  • 선택된 8번 노드가 현재 시점 (current state)이 된다.

  • 8번 노드에서 연결된 다른 노드를 탐색한다.

  • 기존에 무한대(∞)로 초기화된 가중치 값을 업데이트하게 된다.

    • 8번 노드에서 연결된 노드의 가중치가 10으로 변경된다.

4. 종료 조건 (Termination):

  • 모든 노드가 선택되어 연결되면 알고리즘이 종료된다.

  • 결과는 최소 신장 트리 (Minimum Spanning Tree)가 된다.

그리디 알고리즘의 예 #2 : 프림 알고리즘 의사코드 (Example of Optimal Solution in Greedy Algorithm - Prim Algorithm)

💡요약: 프림 알고리즘은 탐욕적 접근 방식을 기반으로, 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree)를 점진적으로 구성한다. 이 의사코드는 정점 중심(
vertex center) 으로 작동하며, 각 단계에서 비용이 가장 작은 정점을 선택하고, 이를 통해 최적의 MST를 보한다. ExtractMin 연산과 비용 갱신이 알고리즘의 핵심이다.

  • 입력값 정의(Input definition):

    • G = (V, E): 정점 집합 V와 간선 집합 E로 이루어진 그래프.

    • r: 시작 정점(알고리즘이 시작되는 지점).

    • 정점(node): 위치라는 개념. (node 라고도 부름)

    • 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)

  • 초기화 (Initialization):

    • S ← ∅: MST에 포함된 정점 집합을 초기화(비어 있음).

    • 각 정점 v의 비용(u.cost)을 무한대로 설정: u.cost←∞

    • 시작 정점 r의 비용을 0으로 설정: r.cost←0

  • 반복 (Iteration):

    • 조건: S≠V (모든 정점이 MST에 포함될 때까지 반복).

    • ExtractMin: S에 포함되지 않은 정점 중에서 비용(u.cost)이 가장 작은 정점 u를 선택한다.

    • 선택된 정점 u를 정점 집합 S에 추가한다. S←S∪{u}

  • 인접 정점 업데이트(Adjacent Vertex Update)

    • 선택한 정점 u와 연결된 모든 인접 정점 v에 대해:

      • v가 아직 S에 포함되지 않았고, 간선 (u,v)의 가중치 wuv​가 v.cost보다 작으면:

        • v.cost←wuv​: 비용 갱신.

        • v.tree←u: v의 트리에 연결된 정점을 u로 설정.

  • 선택된 정점과 인접한 노드의 비용을 업데이트한다.

  • 종료 (Termination):

    • 모든 정점이 S에 포함되면 종료된다.

    • 최소 신장 트리 (Minimum Spanning Tree)가 완성된다.

💡중요포인트

  1. 탐욕적 접근(Greedy Choice Property):

    • 각 단계에서 S에 포함되지 않은 정점 중에서 비용이 가장 작은 정점을 선택(ExtractMin)한다.

    • 이러한 선택은 항상 최적해(MST)의 일부가 되도록 보장되는 역할을 한다.

  2. ExtractMin:

    • 우선순위 큐(Heap)를 사용하여, 비용(u.cost)이 가장 작은 정점을 효율적으로 선택한다.

    • 이는 알고리즘의 핵심 연산이며, 프림 알고리즘의 시간 복잡도를 결정짓는 요소이다. O (ElogV)

  3. MST(Minimum spanning tree)의 점진적 확장:

    • 선택한 정점을 기반으로 연결된 간선을 탐색하고, 비용이 더 작은 간선을 선택하여 MST를 점진적으로 확장한다.

👀✅ 다음으로 이진트리의 최적합 경로에 대해서 알아본다. 그리디 알고리즘으로 최적해를 구할수없는 대표적인 예이다. 이로써 최적해가 보장되는 예 vs 보장되지 않는 예를 비교하며 어떤 경우에 알맞는 알고리즘을 적용할 것인가를 배우는 것이 이번시간의 목표이다.

그리디 알고리즘의 예 #3: 이진트리 - 최적합 경로 (Optimal Path in Binary Tree)

💡 주제 개요 (Topic Overview)

이진트리의 최적합 경로란 루트에서 리프노드까지 방문할때 각 노드의 가중치를 최대화하는 경로를 찾는 것이다. 그리디 알고리즘이 최적해가 되려면 이전에 선택한 결정이 이후에 영향을 주면 안된다. 현재 시점만 생각하기 때문에 그 다음 시점은 고려하지 않기 때문이다. 그런데 만약 현재 시점이 그 다음 결정에 영향을 준다고 하면 현재 시점에서 더 먼 범위를 바라봐야하므로 이 경우엔 그리디 알고리즘 적용이 불가능하게 된다.

✅ 그리디 알고리즘이 실패하는 이유 (Why Greedy Fails for Binary Tree Paths)

  1. 의존성 문제 (Dependency Issue):

    • 그리디 알고리즘은 현재 시점에서만 최선의 선택을 한다.

    • 그러나 이진트리의 최적합 경로에서는 현재 선택이 이후 선택에 영향을 미치기 때문에, 전체 경로를 고려해야 최적해를 구할 수 있다.

  2. 국소적 최적화와 전체 최적화의 차이 (Local vs Global Optimization):

    • 그리디 알고리즘은 국소적 최적화 (local optimization)를 목표로 한다.

    • 이진트리 문제에서는 전체 최적화 (global optimization)가 필요하므로, 그리디 알고리즘은 부적합하다.

✅ 최적해가 보장되는 예 vs 보장되지 않는 예

(Guaranteed vs Non-Guaranteed Examples)

💡 최적해 보장되는 경우 (Guaranteed Examples):

  • 프림 알고리즘 (Prim Algorithm): 최소 신장 트리를 찾을 때, 간선 가중치만 고려하므로 그리디 방식이 적합하다.

  • 다익스트라 알고리즘 (Dijkstra Algorithm): 특정 노드에서 모든 다른 노드까지의 최소 비용 경로를 찾는 경우이다.

  • 크루스칼 알고리즘 (Kruskal Algorithm): 사이클 없이 최소 비용으로 모든 노드를 연결하는 경우이다.

💡 최적해 보장되지 않는 경우 (Non-Guaranteed Examples):

  • 이진트리의 최적합 경로 (Optimal Path in Binary Tree): 현재 시점에서 최선의 선택이 이후에 더 나은 선택을 방해할 수 있다.

  • 배낭 문제 (Knapsack Problem, 일반형): 물건의 이익/무게 비율만 고려하면 전체 최적해를 놓칠 수 있다.

문제를 해결하기 전에, 문제의 구조를 파악해 독립적인 결정인지, 의존적인 결정인지 분석하는 것이 중요하다. 분석 후에는 적합한 알고리즘 (그래디 vs 동적 프로그래밍)을 선택한다.

그리디 알고리즘의 예 #4 : 그리디 알고리즘이 실패하는 예 (Optimal Path in Binary Tree - Example of Greedy Failure)

1. 문제 정의 (Problem Definition):

  • 트리의 루트 노드에서 리프 노드까지 이동하며 각 경로의 가중치 합이 최대가 되는 경로를 찾는 문제이다.

2. 그리디 알고리즘의 작동 방식 (How Greedy Works):

  • 루트(10)에서 출발하여, 인접 노드 중 가장 큰 값을 가진 60을 선택한다.

  • 60에서 리프 노드 2로 이동하며 경로가 종료된다.

  • 이 과정에서 전체 경로의 가중치 합은 10 + 60 + 2 = 72 이다.

3. 전체 최적경로 (Global Optimal Path):

  • 루트(10)에서 15를 선택한 뒤, 30 → 45 → 67 → 38 → 33 경로를 선택하는 경우, 경로의 가중치 합은 10+15+30+45+67+38+33=238로 그리디 경로보다 훨씬 큰 결과가 된다.

✅ 그리디 알고리즘의 한계 (Limitations of Greedy Algorithm)

  1. 현재 시점만 고려 (Focus on Current State Only):

    • 그리디 알고리즘은 항상 현재 시점에서 가장 큰 값(최선의 선택)을 따른다.

    • 이로 인해 다음 단계에서 발생할 선택의 기회를 놓치게 된다.

  2. 전역 시야 부족 (Lack of Global View):

    • 전체 트리를 보지 않고 인접한 두 노드만 비교하기 때문에 전체 경로의 최적해를 구할 수 없게 된다.

  3. 의존성 문제 (Decision Dependency):

    • 루트에서 특정 노드를 선택한 결과가 이후 경로 선택에 제한을 가하게 된다.

    • 예: 루트에서 60을 선택하면, 이후에는 리프 노드 2로 제한되며 다른 경로를 탐색할 수 없다.

✅이진 트리 최적합 경로의 적합한 알고리즘

  • 동적 프로그래밍 (Dynamic Programming)이 적합하다.

  • 전체 경로를 탐색하며, 각 단계에서의 최적 경로를 저장하고 재활용하기 때문이다.

그리디 알고리즘의 예 #5: 동전 바꾸기 문제 (Coin Change Problem - Limitations of Greedy Algorithm and Optimal Solution)

동전바꾸기 문제는 쉽게 생각하면 거스름돈을 자판기에서 계산해서 출력할때 거스름돈이 600원인데 이 잔돈을 10원짜리로 60개가 나온다면 이용자는 당황할 것 이다. 거스름돈은 최소한의 동전이 되도록 계산해서 배출이 되게 된다. 이러한 상황을 알고리즘으로 구현하면 최적해가 보장되는 상황이 된다.

💡요약 (Summary)

  1. 동전 바꾸기 문제 정의 (Coin Change Problem):

    • 주어진 금액을 가장 적은 수의 동전으로 교환하는 문제이다.

  2. 그리디 알고리즘의 성공 조건 (When Greedy Works):

    • 동전 액면이 모두 아래 액면의 배수여야 최적해를 보장하게 된다.

    • 예) 500원 = 100원 × 5, 100원 = 50원 × 2

  3. 그리디 알고리즘의 한계 (Limitations of Greedy):

    • 액면 간 배수 관계가 없을 경우, 선택이 이후 값 계산에 영향을 미쳐 최적해를 보장할 수 없음.

✅그리디 알고리즘이 성공하는 경우

  1. 예제: 3,256원을 만들기 (Example: Making 3,256 KRW):

    • 동전 액면: 500원, 100원, 50원, 10원, 5원, 1원.

    • 그리디 알고리즘 동작:

      • 500원 × 6개 = 3,000원

      • 100원 × 2개 = 200원

      • 50원 × 1개 = 50원

      • 5원 × 1개 = 5원

      • 총 동전 수: 11개.

    • 액면이 배수 관계를 유지하므로, 그리디 알고리즘이 최적해를 보장하게 된다.

✅그리디 알고리즘이 실패하는 경우

  1. 예제 : 1,300원을 만들기 (Example: Making 1,300 KRW):

    • 동전 액면: 500원, 400원, 100원, 75원, 50원.

    • 그리디 알고리즘 동작:

      • 500원 × 2개 = 1,000원

      • 100원 × 3개 = 300원

      • 총 동전 수: 5개.

      • 자판기 거스름돈 계산과 같은 빠른 계산, 단순 구현 상황에서 적합하다.

    • 최적해 동작:

      • 500원 × 1개 = 500원

      • 400원 × 2개 = 800원

      • 총 동전 수: 3개.

      • DP 배열을 이용하여 각 금액에 대해 최소 동전 수를 계산할 때 적합하다.

    • 위의 첨부된 예제에서도 설명하듯이 동전이 아래 액면의 배수가 아닌 경우 최적해를 보장하지 않게 된다. 나머지 값이 어떤 동전을 선택했느냐에 따라 나눌수있는 값이 달라지기 때문에 최적해가 보장되지 않게 되는 것이다. 위의 문제의 경우 그리디알고리즘이라면 500원 2개 + 100원 3개 = 1300원이되어 총 5개의 동전으로 만들게 된다. 최적해의 경우엔 500원 1개 + 400원 2개 = 1300원 이렇게 3개의 동전만으로 값을 완성 시키게 되는데 이는 가장 큰 값인 500원을 제일 많이 사용하지 않았으므로 그리디 알고리즘에서 나올 수 없는 결과이다. 그렇기 때문에 최적해가 보장되지 않게 된다.

그리디 알고리즘의 예 #6: 최적해가 보장되는 조건 (Conditions for Guaranteeing Optimal Solution with Greedy Algorithm)

그리디 알고리즘이 전체 최적해 (global optimal solution)를 보장하려면 다음 두 가지 조건이 반드시 만족되어야 한다.

✅ 탐욕 선택 조건 (Greedy Choice Property)

  • 현재 시점에서 가장 최선의 선택을 했을 때, 이 선택이 이후의 선택에 영향을 미치지 않아야 한다. 즉 현재 시점에서 내린 선택이 이후의 선택에 독립적이어야 하며, 이는 현재 선택만으로 최적해를 만들 수 있음을 보장한다.

  • 프림 알고리즘 (Prim Algorithm): 최소 가중치를 가진 간선을 선택해도 이후의 간선 선택 과정에 영향을 미치지 않음.

  • 다익스트라 알고리즘 (Dijkstra Algorithm): 현재 최소 비용 노드를 선택해도 이후 노드 탐색에 독립적.

  • 반대의 경우로는 이진트리 최적합 경로: 현재 선택한 노드가 이후 선택 가능한 경로를 제한하므로, 탐욕 선택 조건이 성립하지 않게 된다.

✅ 최적 부분 구조 (Optimal Substructure)

  • 문제를 부분 문제 (subproblem)로 나누었을 때, 부분 문제의 최적해가 전체 문제의 최적해에 포함되어야 한다.

  • 이는 동적 프로그래밍에서도 중요한 성질로, 문제를 재귀적으로 나누고 각 부분의 최적해를 조합해 전체 최적해를 보장할 수 있게 된다.

  • 동전 거스름돈 문제 (Coin Change Problem): 3,256원을 만드는 문제를 500원, 100원, 50원 등으로 나누어 각각의 최적해를 구하고 조합한다.

  • 크루스칼 알고리즘 (Kruskal Algorithm): 최소 신장 트리를 구성할 때, 부분적으로 선택된 간선들의 최적해가 전체 트리의 최적해에 포함한다.

  • 반대의 경우, 1300원 동전 문제: 부분적으로 500원을 최대한 많이 사용하는 선택이 전체 최적해를 구성하지 않음.

4️⃣ 그리디 알고리즘 문제 (Example of Greedy Algorithms)

❤️동전 개수 최솟값 구하기 문제 (Coin Change Problem)
❤️카드 정렬하기 (Card Sorting Problem)
❤️회의실 배정하기 (Meeting Room Allocation Problem)
❤️최솟값을 만드는 괄호 배치 찾기(Finding Minimum Value with Proper Parentheses)

❤️ 동전 개수 최솟값 구하기 문제 (Coin Change Problem - Minimizing Coin Count)

✅ 문제 정의:

  • 일반적으로 자판기에서 상품의 거스름 돈을 받을때 동전 개수가 최소가 되도록 하는 알고리즘이다.

  • 동전은 총 N 종류가 있고 각 동전의 개수는 충분히 많다고 가정한다.

  • 동전의 종류는 미리 정해져있다.

  • 주어진 금액 K 를 동전개수가 최소가 되도록 채워야한다.

✅ 입출력의 예제

  • 오름차순으로 동전의 액면이 입력으로 주어졌다 1원 , 5원 , 10원이렇게해서 50000원까지 포함하였다.

  • 예제 1: 목표 금액 4200원을 만들기 위한 최소 동전 개수 = 6개

  • 예제 2: 목표 금액 4790원을 만들기 위한 최소 동전 개수 = 12개

✅손으로 풀어보기 (Step-by-Step Example)

목표 금액 4200원(K = 4200)

  • 동전 리스트: [1,5,10,50,100,500,1000,5000,10000,50000]
  1. 첫 번째 선택

  • 동전리스트 A를 보면 5000, 10000, 50000은 목표 금액보다 크기 때문에 선택 할수없다. 결국 1000원짜리 부터 선택이 된다.

  • K=4200, 가장 큰 동전은 1000원

  • 4200 ÷ 1000=4 (몫 = 4개, 나머지 = 200).

  • 동전 개수 += 4.

  1. 두 번째 선택

  • 200원을 가지고 다시 진행하게 된다. 동전리스트에서 500원은 200원보다 크므로 선택할수없다. 결국 100원짜리를 선택하게 된다.

  • K(목표금액) = 200, 가장 큰 동전은 100원

  • 200 ÷ 100=2 (몫 = 2개, 나머지 = 0).

  • 동전 개수 += 2.

  1. 세 번째 선택

  • k = 0이 되며 알고리즘이 종료하게 된다. 4+2 의 계산결과 6이 최소한의 동전개수가 되는 것이다.

  • K = 0, 최소 동전 개수 4 + 2= 6

동전 개수 최솟값 구하기 문제 #2: 의사코드 (Pseudocode - Coin Change Problem)

주어진 금액 K를 가장 적은 수의 동전으로 만들기 위해 큰 동전부터 사용한다.
동전 액면값은 내림차순(Descending Order)으로 정렬되어 있다고 가정한다.

내림차순 (Descending Order) 값이 큰 것부터 작은 것으로 정렬되는 순서

2. 동전 액면값 저장

for N만큼 반복:
    A 리스트 저장

  • 목적: N개의 동전 액면값을 입력받아 A리스트에 저장한다.

  • A는 동전의 액면값(예: 500, 100, 50, 10, 5, 1)을 포함하는 배열이다.

3. 큰 동전부터 사용

for N만큼 반복 (N - 1 → 0으로 역순으로 반복): # N: 사용할 동전의 종류(개수).
    if 현재 K보다 동전 가치가 작거나 같으면:
        동전 수 += 목표 금액 // 현재 동전 가치
        목표 금액 = 목표 금액 % 현재 동전 가치

  • 탐색 순서: A(동전 데이터 리스트)를 큰 값부터 작은 값으로 탐색한다.

  • 조건 확인: 현재 동전 A[i]의 가치가 K(목표 금액)보다 작거나 같으면, 해당 동전을 사용할 수 있게 된다.

  • 동작:

    • 동전 사용 개수 계산: K ÷ A[i] (목표 금액에서 해당 동전을 최대한 사용 가능한 개수).

    • 남은 금액 계산: K % A[i] (현재 동전을 사용하고 남은 금액).

4. 결과 출력

  • 반복이 종료되면, 사용한 동전의 총 개수를 출력한다.

동전 개수 최솟값 구하기 문제 #3: 파이썬 코드 (Coin Change Problem - Python Code)

1. 입력 처리

N, K = map(int, input().split())  # 동전 개수 N, 목표 금액 K 입력
A = [0] * N                      # 동전 리스트 초기화 (N개의 0으로 시작)

  • 입력값: N: 사용할 동전의 종류 수, K: 만들고자 하는 목표 금액.

  • A: 동전의 액면값을 저장할 리스트로, 초기값은 0으로 설정한다.

2. 동전 액면값 저장

for i in range(N): # N개의 동전 액면값을 입력받아 리스트 A에 저장
    A[i] = int(input())

  • N개의 동전 액면값을 입력받아 리스트 A에 저장한다.

  • 입력된 액면값은 오름차순 정렬된 상태로 저장된다.

  • 오름차순 (Ascending Order) 값이 작은 것부터 큰 것으로 정렬되는 순서를 말함

3. 동전 개수 계산 (큰 동전부터 사용)

count = 0                    # 사용된 동전 개수를 기록하는 변수 초기화

for i in range(N - 1, -1, -1):# 큰 동전부터 반복 (리스트를 역순 탐색)
    if A[i] <= K:             # 현재 동전 가치가 목표 금액보다 작거나 같으면:
        count += K // A[i]    # 현재 동전의 최대 개수를 추가
        K = K % A[i]          # 남은 금액 계산

  • 탐색 순서: 리스트 A를 역순으로 탐색하여 큰 동전부터 처리한다.

  • 조건: 현재 동전의 액면값 A[i]이 목표 금액 K보다 작거나 같을 경우, 해당 동전을 사용할 수 있다.

  • 동전 개수 계산:

    • K//A[i]: 현재 목표 금액에서 사용할 수 있는 최대 동전 개수.

    • count: 사용한 동전의 총 개수를 누적한다.

  • 남은 금액 계산:

    • K = K % A[i] : 현재 동전을 사용하고 남은 금액을 업데이트한다.

4. 결과 출력

print(count)  # 사용된 동전의 총 개수 출력
  • 모든 반복이 끝난 후, 사용된 동전의 최소 개수를 출력한다.

💡 동전 개수의 최솟값 문제와 우선순위 큐 학습의 연계

✅ 우선순위 큐는 그리디 알고리즘에서 자주 사용되는 도구

그리디 알고리즘의 핵심은 현재 시점에서 가장 최적의 선택을 반복적으로 수행하는 것이다. 이를 구현하기 위해 가장 적합한 자료구조 중 하나가 우선순위 큐이다.

  • 동전 문제에서는 단순히 "가장 큰 동전부터 탐색"하는 방식으로 해결되지만,

  • 복잡한 문제에서는 "가장 비용이 낮은 옵션"을 빠르게 찾기 위해 우선순위 큐가 필요하다.

    • 예: Prim 알고리즘, Dijkstra 알고리즘 등.

따라서, 동전 문제를 통해 그리디 알고리즘의 개념을 배우고, 우선순위 큐를 활용할 수 있게 학습하는 것이다.

✅동전 문제는 간단한 예제, 우선순위 큐는 복잡한 문제로 확장 가능

  • 동전 문제는 비교적 단순한 그리디 문제로, 우선순위 큐 없이도 효율적으로 해결된다.

  • 하지만 복잡한 문제(예: 그래프 탐색, 작업 스케줄링 등)로 확장하면, 최적의 선택을 효율적으로 관리하기 위해 우선순위 큐가 필요하게 된다.

  • 만약 동전의 리스트가 동적으로 변경되거나, 조건이 추가된다면?

  • 모든 후보 중 최적의 선택을 효율적으로 관리해야 한다면?

✅우선순위 큐의 학습이 그리디 알고리즘 확장에 도움된다.

우선순위 큐는 그리디 알고리즘을 구현하거나 확장하는 데 유용한 도구가 된다. 동전 문제에서 단순히 "최적의 선택"을 반복적으로 수행하는 과정을 확장하여, 다음과 같은 문제로 적용할 수 있기 때문이다.

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

    • 우선순위 큐를 사용해, 현재 가장 낮은 비용의 간선을 빠르게 선택.

  2. Dijkstra 알고리즘 (최단 경로):

    • 우선순위 큐를 사용해, 현재 가장 짧은 거리의 노드를 효율적으로 탐색.

  3. Huffman 코딩 (압축 알고리즘):

    • 우선순위 큐를 사용해, 최소 비용으로 이진 트리를 구성.

✅정리: 동전 개수의 최솟값 문제는 그리디 알고리즘의 단순하고 직관적인 예제이다. 우선순위 큐는 이 문제를 직접적으로 최적화하지 않더라도:

  1. 현재 시점에서 최적 선택을 관리하는 도구로서 그리디 알고리즘의 본질과 연결된다.

  2. 복잡한 문제로 확장할 때, 우선순위 큐의 효용성을 이해하도록 돕는다.

  3. 학습의 흐름으로, 간단한 문제에서 출발해 알고리즘의 기본 개념과 도구 활용법을 배우게 된다.

동전 개수 최솟값 구하기 문제 #4: 우선순위 큐(Priority Queue - Coin Change Problem)

💡 우선순위 큐란?

우선순위 큐는 "가장 중요한 데이터"를 먼저 꺼내도록 설계된 구조를 뜻한다.

  • 예시: 만약 은행에서 VIP 고객이 일반 고객보다 먼저 처리되길 원한다면, 우선순위를 VIP > 일반 고객으로 설정할 수 있다.

  • 큐에 넣는 순서와 상관없이, 우선순위가 높은 것부터 꺼내는 것이다.

Python에서 우선순위 큐를 만드는 두 가지 방법

✅ PriorityQueue (스레드-안전 큐)

Python에서 PriorityQueue는 멀티스레드 환경에서도 안전하게 작동하는 우선순위 큐이다.

  • 사용법 간단 요약:

    1. PriorityQueue를 우선순위 큐로 생성한다.

    2. put(data): 데이터를 큐에 넣는다.

    3. get(): 가장 우선순위가 높은 데이터를 꺼낸다.

    4. qsize(): 큐사이즈를 가져온다.

    5. empty(): 큐가 비어 있는지 확인한다.

    from queue import PriorityQueue

    # 우선순위 큐 생성
    myque = PriorityQueue()

    # 데이터 넣기
    myque.put(5)  # 숫자 5 추가
    myque.put(1)  # 숫자 1 추가
    myque.put(3)  # 숫자 3 추가

    # 우선순위 높은 데이터 꺼내기
    print(myque.get())  # 출력: 1 (가장 작은 숫자가 우선)
    print(myque.get())  # 출력: 3
    print(myque.get())  # 출력: 5

✅heapq (간단한 힙 구조 큐)

heapq는 Python에서 우선순위 큐를 구현하는 또 다른 방법이다. 리스트를 최소 힙(Min Heap) 구조로 바꿔서 데이터를 관리한다.

  • 사용법 간단 요약:

    1. 리스트를 생성한다.

    2. heappush(): 데이터를 힙구조로 삽입하며, 자동으로 정렬한다.

    3. heappop(): 가장 작은 값을 꺼내고 힙을 유지한다.

    4. heapify(): 기존 리스트를 힙으로 변환한다.

    import heapq

    # 빈 리스트 생성
    mylist = []

    # 데이터 넣기
    heapq.heappush(mylist, 1)  # 숫자 1 추가

    # 우선순위 높은 데이터 꺼내기
    heapq.heappush(mylist, data)  # 힙에 데이터 추가
    heapq.heappop(mylist)         # 힙에서 가장 작은 데이터 꺼내기
    heapq.heapify(mylist)         # 일반 리스트를 힙 구조로 변환

보통 빠른 성능을 원할 때는 heapq를 많이 사용한다.

❤️카드 정렬하기(Card Sorting Problem)

✅ 문제 정의 (Problem Definition)

  • 정렬된 두 묶음 A와 B를 하나로 합치려면 A+B만큼의 비교가 필요하다.

  • 정렬된 여러 묶음의 숫자 카드가 있을 때, 이들을 두 묶음씩 골라 서로 합쳐 나가는 과정을 반복한다.

    • 이 과정에서 합치는 순서에 따라 비교 횟수가 달라지게 된다.

  • 목표 (Goal): 묶음의 순서를 잘 조정하여, 최소한의 비교 횟수를 구하는 것이다.

✅입출력의 예

세 가지의 묶음을 두 개씩 합쳐서 전체적으로 하나의 묶음으로 만들때 최소한의 비교횟수를 출력하는 것이 이 문제이다. 이 예제에서는 100이 출력되었다.

입력 형식 (Input Format)

  1. 첫째 줄: 숫자 카드 묶음의 개수 N (1 ≤ N ≤ 100,000)

  2. 다음 N줄: 각 줄에 카드 묶음의 크기 K가 주어짐 (1 ≤ K ≤ 1,000,000)

✅입출력의 예제 문제 분석하기

Case 1 : 10장과 20장을 먼저 합치는 경우

  1. 첫 번째 합침: 10 + 20 =30

  2. 두 번째 합침: 합쳐진 묶음 30과 40을 합침. 30 + 40 = 70

  3. 총 비교 횟수: 30 + 70 = 100

Case 2: 10장과 40장을 먼저 합치는 경우

  1. 첫 번째 합침: 10 + 40 = 50

  2. 두번째 합침: 합쳐진 묶음 50과 20을 합친다. 50 + 20 = 70

  3. 총 비교 횟수: 50 + 70 = 120

✅ 분석 결과

  1. 비교 횟수는 선택 순서에 따라 달라진다.

    • Case 1 (10 + 20 먼저 합침): 총 비교 횟수 = 100.

    • Case 2 (10 + 40 먼저 합침): 총 비교 횟수 = 120.

  2. 초기 선택이 중요한 이유:

    • 처음 선택된 묶음은 이후에 계속 포함되어 추가 비교가 발생한다.

    • 따라서, 처음 선택하는 묶음은 카드 개수가 작은 것이 유리하다.

    • 한 번 합쳐진 묶음은 다음 합칠 때 더 많은 비교에 포함되기 때문이다.

    • 매번 가장 작은 두 묶음을 선택하는 방식이 최적의 선택인데 이는 그리디 알고리즘이다.

✅손으로 풀어보기 (Step-by-Step)

  • 현재 카드 묶음 중 가장 작은 두 묶음을 선택해 합친다.

  • 합쳐진 묶음을 다시 카드 묶음 집합에 추가한다.

  • 위 두 과정을 카드 묶음이 하나만 남을 때까지 반복한다.

  • 합쳐진 묶음의 비교 횟수를 모두 더하여 최소 비교 횟수를 구한다.

  1. 우선순위 큐 작동 방식:

    • 카드 묶음을 우선순위 큐에 삽입한다.

    • 우선순위 큐는 항상 가장 작은 값이 먼저 나오도록 정렬 상태를 유지한다.

  2. 구체적인 동작 과정:

    • 초기 상태: [40,20,10]

      • 큐에서 가장 작은 두 묶음 10과 20을 꺼냄.

      • 합침: 10 + 20 = 30

      • 합친 결과 30을 다시 큐에 삽입: [40,30]

      • 순서가 중요한 것은 아니지만 현재 가장 작은 두 묶음을 선택해 합치는 방식이 전체적으로 최적의 결과를 보장하는 그리디 알고리즘의 개념이 구현된 부분이다.

    • 두 번째 반복: [40,30]

      • 큐에서 가장 작은 두 묶음 30과 40을 꺼냄.

      • 합침: 30 + 40 = 70

      • 합친 결과 70을 다시 큐에 삽입: [70]

  3. 최종 상태:

    • 큐에 카드 묶음이 하나만 남으면 종료.

    • 사용된 모든 비교 횟수를 합산: 30 + 70 = 100

카드 정렬하기 #1: 의사코드 (Pseudocode in Card Sorting Problem)

  1. 초기화: N: 카드 묶음의 개수, pq: 우선순위 큐(작은 값이 우선적으로 처리됨).

  2. 데이터 입력: N만큼 반복하며, 각 카드 묶음의 크기를 우선순위 큐에 저장한다.

  3. 알고리즘 동작:

    • 반복 조건: 우선순위 큐의 크기가 1이 될 때까지 진행.

    • 동작 과정:

      1. 우선순위 큐에서 가장 작은 두 개의 카드 묶음을 꺼냄.

      2. 두 카드 묶음을 합치는 데 필요한 비교 횟수를 결과 값에 더함.

      3. 합친 카드 묶음의 크기를 다시 우선순위 큐에 넣음.

  4. 최종 결과: 큐의 크기가 1이 되면 최소 비교 횟수가 계산 완료.

✅주요 특징

  • 우선순위 큐: 각 단계에서 가장 작은 두 값을 쉽게 꺼낼 수 있어 효율적이다.

  • 그리디 전략: 매번 가장 작은 두 카드 묶음을 합치는 국소 최적 선택을 통해 전체 최적 결과를 도출한다.

이 알고리즘은 허프만 코딩(Huffman Coding)과 유사한 방식으로, 주어진 문제에서 최소 비용으로 작업을 수행하기 위해 설계되었다.

카드 정렬하기 #2: 파이썬코드 (Python in Card Sorting Problem)

  1. 우선순위 큐 초기화:

    • from queue import PriorityQueue를 사용하여 Python의 우선순위 큐 모듈을 가져온다.

    • pq = PriorityQueue()를 통해 우선순위 큐 객체를 생성한다.

  2. 입력 처리:

    • N = int(input()): 카드 묶음의 개수를 입력받는다.

    • 반복문 for _ in range(N)::

      • 각 카드 묶음의 크기를 입력받아(date = int(input())) 우선순위 큐에 저장한다.(pq.put(date)).

  3. 초기 변수 설정:

    • data1, data2, sum 변수를 0으로 초기화한다.

    • sum은 최종 최소 비교 횟수를 저장하는 변수이다.

  4. 그리디 알고리즘 실행:

    • while pq.qsize() > 1: 우선순위 큐의 크기가 1보다 클 때까지 반복.

      • 두 카드 묶음 꺼내기: data1 = pq.get(), data2 = pq.get().

      • 두 카드 묶음 합치기:

        • temp = data1 + data2: 두 카드 묶음의 크기를 더한다.

        • sum += temp: 비교 횟수를 합산.

      • 합친 묶음을 다시 큐에 삽입: pq.put(temp).

  5. 결과 저장:

    • sum에 모든 비교 횟수의 합이 저장된다.

✅ 작동 방식 요약

  • 작은 두 카드 묶음을 반복적으로 합치며 비교 횟수를 최소화하는 방식이다.

  • 우선순위 큐를 사용해 매번 가장 작은 두 값을 빠르게 선택한다.

  • 이는 허프만 코딩 문제의 원리와 동일하며, 최소 비용으로 작업을 수행할 수 있는 대표적인 그리디 알고리즘이다.

❤️회의실 배정하기 (Meeting Room Allocation Problem)

💡요약: 이 알고리즘은 종료 시간이 빠른 순서대로 회의를 선택하여 최대한 많은 회의를 배치하는 그리디 알고리즘의 대표적인 사례이다. 이 알고리즘을 이용하면 강의실, 세미나실 대여와 같은 실제 상황에서 효과적으로 활용할 수 있게 된다.

✅ 문제 정의 (Problem Definition)

  1. 목표 (Goal): 하나의 회의실에서 겹치지 않게 최대한 많은 회의를 배정하는 스케줄을 작성한다.

  2. 입력 조건 (Input Conditions)

    • 첫 번째 줄에 회의의 개수 n이 주어진다.

    • 두번째 줄부터는 N+1줄까지 각 회의의 시간과 끝 시간이 주어진다.

    • 이후 각 회의의 시작 시간과 종료 시간이 주어진다.

  3. 출력 조건 (Output Conditions)

    • 겹치지 않고 진행 가능한 최대 회의 수를 출력하게 된다.

✅ 문제 분석 및 해결 방법 (Problem Analysis and Solution Approach)

  1. 종료 시간 기준 정렬 (Sort by End Time)

    • 회의를 가장 많이 개최하려면 종료 시간이 빠른 회의를 먼저 선택해야 한다.

    • 종료 시간이 같을 경우, 시작 시간을 기준으로 다시 정렬한다.

  2. 그리디 알고리즘 전략 (Greedy Algorithm Strategy)

    • 종료 시간이 가장 빠른 회의를 먼저 선택하고, 이후로 겹치지 않는 회의만 추가한다.

  3. 구현 순서 (Implementation Steps)

    1. 종료 시간을 기준으로 회의를 정렬한다.

    2. 첫 번째 회의를 선택한다.

    3. 이후로 순차적으로 겹치지 않는 회의를 추가한다.

입력으로 회의 개수가 먼저 주어진다. 그 다음 줄엔 회의의 시작 시간과 종료 시간이 주어지고, 결과적으로 4개의 회의가 가능함을 예제 출력을 통해 보여주고 있다.

✅ 손으로 풀어보기 (Step-By-Step)

위에서 주어진 입력 값으로 0 시에서 13시까지 배정하는 예제이다.

각 회의의 시작 시간과 끝시간이 컬러 블록으로 표시되어 정렬되어 있다. 정렬의 기준은 "끝시간"이된다. 그 다음, 순서대로 회의를 하나씩 스케줄화 하여 등록하게 된다.

  • 가장 처음에 배치되어있던 배열이 우선순위가 먼저이므로 첫 번째 회의 (1, 4) 선택한다

  • 두번째 세번째는 배정 순위가 겹치기 때문에 배정할 수 없다. (3,5) & (0,6)

  • 겹치는 다음 배열은 모두 무시하고 겹치지 않으면서 종료시간이 빠른 회의를 선택한다. (5, 7), (8, 11), (12, 14)

  • 최종적으로 총 4개의 회의가 배치되었다.
    (Select meetings in order: (1, 4), (5, 7), (8, 11), (12, 14).)

회의실 배정하기: 의사코드 (Pseudocode in Meeting Room Allocation Problem)

✅ 입력 데이터

  • N: 회의의 개수 (총 몇 개의 회의가 있는지).

  • A: 각 회의의 시작 시간과 종료 시간 정보가 저장된 리스트.

✅정렬 과정 A리스트 정렬 수행

  • 회의의 종료 시간 기준으로 회의를 정렬한다.

  • 만약 종료 시간이 같다면 시작 시간 기준으로 정렬한다.

    • 이유: 종료 시간이 빠른 회의를 우선적으로 배정해야 최대한 많은 회의를 배치할 수 있기 때문이다.

✅ 회의 배정

  • 이전에 선택한 회의의 종료 시간을 기준으로 잡고, 그 이후에 시작할 수 있는 회의를 선택한다.

  • 선택된 회의를 진행 가능하다고 판단하고, 종료 시간을 업데이트한다.

✅결과 계산: 반복문이 끝날 때까지 배정된 회의의 개수를 출력한다.

회의실 배정하기: 파이썬 코드 (Python Code in Meeting Room Allocation Problem)

✅입력 데이터 초기화

N = int(input())  # 회의의 개수 (총 N개의 회의)
A = [[0] * 2 for _ in range(N)]  # 각 회의의 [종료 시간, 시작 시간]을 저장할 리스트

  • N: 총 몇 개의 회의가 있는지 사용자로부터 입력받습니다.

  • A: 각 회의의 정보를 저장할 2차원 리스트이다.

    • [종료 시간, 시작 시간] 형식으로 저장한다.

✅ 회의 데이터 입력받기

for i in range(N):
    S, E = map(int, input().split())  # 각 회의의 시작 시간(S)과 종료 시간(E)을 입력받음
    A[i][0] = E  # 종료 시간을 첫 번째 값으로 저장
    A[i][1] = S  # 시작 시간을 두 번째 값으로 저장

  • 입력 형식:

    • 각 회의의 시작 시간과 종료 시간이 공백으로 구분되어 주어진다.

    • 예를 들어, 1 4는 시작 시간이 1, 종료 시간이 4인 회의를 의미한다.

  • A 리스트:

    • 종료 시간을 첫 번째, 시작 시간을 두 번째 값으로 저장한다.

    • 종료 시간이 우선 정렬의 기준이 되기 때문이다.

✅ 회의 정렬

A.sort()

  • 정렬 기준:

    • 기본적으로 Python의 리스트 정렬은 첫 번째 값을 기준으로 정렬한다.

    • 따라서, 종료 시간을 기준으로 오름차순 정렬된다. (오름차순: 작은 것부터 큰 것의 순)

    • 만약 종료 시간이 같다면, 시작 시간을 기준으로 정렬한다.

✅ 회의 배정 과정

count = 0  # 배정된 회의 개수
end = -1   # 현재 진행 중인 회의의 종료 시간 (-1로 초기화)

  • count: 최종적으로 배정된 회의의 개수를 저장하는 변수.

    • 초기에 0으로 설정.

  • end: 현재 선택된 회의의 종료 시간을 저장한ㄷ,.

    • 초기값은 -1로 설정하여 어떤 회의도 배정되지 않았음을 나타낸다.

✅ 반복문을 통해 회의 배정

for i in range(N):
    if A[i][1] >= end:  # 현재 회의의 시작 시간이 이전 회의의 종료 시간 이후라면
        end = A[i][0]   # 현재 회의의 종료 시간으로 업데이트
        count += 1      # 배정된 회의 개수 증가

  • 조건: 현재 회의의 시작 시간이 이전 회의의 종료 시간 이후라면, 현재 회의를 배정할 수 있다.

  • 동작: 현재 회의를 배정한 뒤, 종료 시간을 업데이트한다.

    • count를 1 증가시켜 배정된 회의의 개수를 기록한다.

✅ 결과 출력

print(count)
  • 최종적으로 배정된 최대 회의 개수를 출력한다.

❤️ 최솟값을 만드는 괄호 배치 문제 (Finding Minimum Value with Proper Parentheses)

✅ 문제 정의 (Problem Definition)

  1. 입력 형식: 0~9 사이의 숫자와 +, - 연산자로 이루어진 수식이 주어지게 된다.

    • 예제 입력: 100-40+50+74-30+29-45+43+11

  2. 출력 형식: 수식의 값을 최소로 만드는 결과를 출력해야 한다.

    • 예제 출력: -222

✅ 풀이 과정 (Step-by-Step Solution)

1. 문제 분석

  • 최솟값을 구하려면:

    • 덧셈(+) 부분을 먼저 계산해서 최대한 큰 값을 만든다.

    • 이 값을 - 연산과 함께 한꺼번에 빼준다.

  • 예를 들어)

  • 100 − (40+50+74) − (30+29) − (45+43+11)

  • 계산하면 100 − 164 − 59 − 99 = −222

💡중요포인트:

  • 핵심 아이디어: - 뒤의 값을 모두 더한 후 한꺼번에 빼주는 방식이 가장 작은 값을 만든다.

  • 풀이 전략: 수식을 -로 분리하고, 각 부분의 덧셈을 계산한 뒤 첫 번째 값에서 차감한다.

  • 시간 복잡도: 효율적으로 O(N)의 시간에 계산 가능하다.

최솟값을 만드는 괄호 배치 문제 - 의사코드 (Pseudocode in Finding Minimum Value with Proper Parentheses)

  1. answer 변수: 정답을 저장하는 변수이고 초기값은 0으로 설정한다.

  2. A 리스트: 입력된 수식을 - 기호를 기준으로 나눈다.

    • 예: 100 - 40+50+74 - 30+29 → ['100', '40+50+74', '30+29'].

  3. mySum(string) 함수: 입력받은 문자열에서 + 기호를 기준으로 나누고 split 수행, 각각의 숫자를 더한 값을 반환한다.

    • 예: mySum('40+50+74') → 40 + 50 + 74 = 164

  1. for 반복문:

    • A 리스트의 각 요소를 순회하며, 값을 더하거나 뺀다.

    • 첫 번째 요소는 항상 더하기 연산.

    • 두 번째 요소부터는 모두 빼기 연산.

  2. 최종 출력:

    • 반복문이 종료되면 answer에는 최솟값이 저장되며, 이를 출력하게 된다.

💡이 의사코드에서 중요포인트:

  1. 그리디 접근: 첫 번째 값은 더하고, 나머지 값은 모두 빼주는 방식으로 최소값을 구하는 전형적인 그리디 알고리즘의 형태이다.

  2. 시간 복잡도:

    • 입력된 수식의 길이를 N이라 할 때, split과 mySum 함수 모두 O(N)에 처리된다.

    • 따라서, 전체 알고리즘의 시간 복잡도는 O(N)가 된다.

  3. 장점: 코드가 간결하며, 효율적이다. 수식이 길어져도 빠르게 처리 가능하다.

최솟값을 만드는 괄호 배치 문제 - 파이썬 코드 (Pseudocode in Finding Minimum Value with Proper Parentheses)

  1. A 리스트 생성: 입력된 수식을 -로 나눈다.

  2. mySum 함수: 이 함수는 + 연산을 처리한다. -로 나뉜 그룹들(문자열) 안의 값을 모두 더해 반환하는 함수이다.

  3. 최종 계산: 첫 번째 그룹은 항상 더하기 연산을 수행한다. 나머지 그룹은 모두 빼기 연산을 수행한다.

💡중요포인트

  1. 코드 흐름:

    • mySum 함수는 그룹 내부의 덧셈을 처리한다.

    • for 반복문은 그룹 간 연산(더하기/빼기)을 처리한다.

  2. 동작 원리: 첫 번째 그룹은 무조건 더하고, 나머지 그룹은 모두 빼준다.

  3. 최소값을 만드는 이유: 가장 큰 값을 빼기 위해 - 뒤에 있는 모든 값을 더한 후 한꺼번에 빼준다.

5️⃣매트로이드(Matroid)

✅ 매트로이드란? 그리디 알고리즘으로 최적해(optimal solution)가 보장되는 공간 구조(spatial structure)를 의미한다.

✅ 매트로이드와 그리디 알고리즘의 관계

  1. 매트로이드의 중요성: 매트로이드로 정의된 문제는 항상 그리디 알고리즘으로 최적해를 구할 수 있다.

  2. 반례:

    • 그리디 알고리즘으로 최적해를 구할 수 있다고 해서 모든 문제가 매트로이드가 되는 것은 아니다.

    • 예: 다익스트라 알고리즘은 매트로이드 이론과 직접적으로 관련되지 않지만 최적해를 보장한다.

  3. 포인트: 매트로이드 구조가 성립하면 그리디 알고리즘의 적용이 쉽고, 최적화 문제를 효율적으로 풀 수 있게 된다.

위의 그림을 예로 들면, 매트로이드는 그리디 알고리즘으로 최적해가 보장되는 부분집합이다. 즉, 전체 집합의 일부로, 최적화 문제를 해결하기 위한 성질을 만족한다.

✅ 실무에서의 활용: 매트로이드 이론을 이해하면, 그리디 알고리즘을 적용할 수 있는 문제를 더 잘 구분하고 최적의 결과를 도출할 수 있게 된다.

매트로이드(Matroid) #1: 상속성과 증강성 = 독립성

✅ 독립성 (Independence)

매트로이드의 두 가지 성질인 상속성 (Hereditary Property)과 증강성 (Exchange Property)을 합쳐 독립성이라고 부른다. 즉 부분해들이 독립적으로 최적 조건을 만족하여, 이들이 합쳐져도 전체 최적해를 이루어야 한다는 조건을 뜻한다.

💡 독립성의 핵심

  • 매트로이드 공간에서 모든 부분해는 독립적으로 최적 조건을 만족한. 이를 통해, 매트로이드 공간에서는 그리디 알고리즘을 안전하게 사용할 수 있게된다.

✅ 상속성 (Hereditary Property)

  1. 정의: 해집합의 모든 부분집합은 여전히 해집합에 속해야 한다.

  • 만약 𝐴 ∈ 𝐼 이고 𝐵 ⊆ 𝐴 라면 𝐵 ∈ 𝐼야 한다.

  • 즉, 해집합에 속한 집합 A의 모든 부분집합 B도 해집합에 속해야 한다는 뜻이다.

    • ❓🤔당연한 것 같은데 왜 이 조건이 언급된 것 일까? 앞에서 그리디 알고리즘의 특성에 대해 생각해보자. 전체적인 골이 하나가 있을때 그리디 알고리즘을 적용하기 좋은 상태가 된다. 이에 따라 집합도 정의가 되는데 실제 그래프의 경우는 항상 포물선의 형태가 아닌 여러개의 골짜기가 생기는 경우도있다. 이럴 경우엔 B가 A에 속하지만 해집합이 아니게 되게 된다. 그래서 “상속성”이 당연히 모든 상황에 일어날 것 같지만 항상 당연한 경우는 아니기 때문에 매트로이드가 수행되려면 상속성이 보장되어야한다.

  • ∈ (원소 포함, "belongs to") : 어떤 요소가 특정 집합의 원소임을 나타낸다.

  • ⊆ (부분 집합, "subset of") 한 집합의 모든 원소가 다른 집합에 포함될 때, 부분 집합 관계를 나타낸다.

  • 해집합 (Solution Set) 문제나 방정식을 만족하는 값들의 집합

  1. 그리디 알고리즘과의 연관성:

  • 큰 해인 A가 작은 해인 B를 품고 있는 형태는 그리디 알고리즘에서 언급된 "최적 부분 구조(Optimal Substructure)"와 밀접한 연관이 있다.

    • "최적 부분 구조"란, 전체 해의 최적해가 포함하는 모든 부분도 최적해라는 성질을 의미한다.

  • Key Point: 매트로이드의 성질인 상속성에서 그리디 알고리즘의 최적 부분 구조를 이해하는 것이 핵심이다.

✅ 증강성 (Exchange Property)

  1. 정의: 작은 집합을 확장해도 여전히 해집합에 속해야 한다.

    • 두 집합 A,B ∈ I가 주어지고, ∣A∣ < ∣B∣일 때:

      • B∖A에 속하는 원소 x를 A에 추가해도 A ∪ {x} ∈ I 가 되어야 한다.

    • 즉, 작은 집합 A를 확장해도 여전히 전체 해집합에 속할 수 있어야 한다.

    • ∈ (원소 포함, "belongs to") : 어떤 요소가 특정 집합의 원소임을 나타낸다.

    • ∣A∣: 집합 A의 원소 개수

    • B ∖ A 집합 B에서 A에 속하지 않는 원소들만 포함하는 집합

    • A ∪ {x} A에 x를 추가한 새로운 집합

    • ∪ {x}: 합집합. 집합에 원소 x를 추가.

  2. 그리디 알고리즘과의 연관성:

    • 증강성은 "탐욕 선택 조건(greedy choice property)"과 밀접하게 연관된다.

      • "탐욕 선택 조건"이란, 이전에 선택된 해가 이후에 추가된 해에 영향을 주지 않아야 함을 의미한다.

    • Key Point: 매트로이드의 성질인 증강성(Exchange Property)에서 그리디 알고리즘의 탐욕 선택 조건(Greedy Choice Property)를 이해하는 것이 핵심이다.

매트로이드(Matroid) #2: 그래픽 매트로이드 (Graphic Matroid)

✅ 그래픽 매트로이드란?

  • 그래픽 매트로이드는 간단하게 "숲(Forest)"으로 정의된다.

  • 숲: 사이클이 없는 간선 집합 또는 여러 개의 트리로 이루어진 집합이다.

  • 숲 집합 𝐹: 모든 가능한 사이클이 없는 부분 집합의 집합을 뜻한다.

  • 2^E : 그래프E에서 나올 수 있는 모든 부분 집합을 뜻한다.

  • 𝐹 ⊆ 2𝐸 : 그래프의 모든 간선 중 사이클이 없는 부분 그래프들만 선택된 집합이라는 뜻

  • F가 매트로이드라는 것은, 숲 집합이 독립성 조건 (independence condition)을 만족한다는 것을 뜻한다.

✅ 숲(Graphic Matroid)의 예제

  1. 그래프와 숲:

    • 주어진 그래프 G는 정점과 간선으로 이루어져 있다.

    • 이 그래프에서 간선의 부분집합을 선택하여 숲을 구성하게 된다.

    • 숲은 사이클이 없는 간선 집합으로 이루어진 부분 그래프이다.

    • 여러 개의 트리로 구성되므로 이를 "숲(Forest)"이라 부른다.

  2. 숲의 집합:

    • 그래프에서 간선들을 선택하여 사이클이 없는 트리들로 이루어진 집합이 된다.

    • 이 숲의 집합은 매트로이드의 조건을 만족한다.

✅ 숲이 매트로이드임을 증명하기

  1. 상속성 (Hereditary Property): 숲의 모든 부분집합도 숲이어야 한다.

    • 트리는 사이클이 없는 간선 집합이다.

    • 트리의 간선을 일부 선택한 부분집합도 사이클이 없으므로 숲이다.

    • 결론: 숲의 상속성이 성립하기 때문에 매트로이드이다.

  2. 증강성 (Exchange Property):

    • 정의: 두 숲 A, B에서 ∣A∣ < ∣B∣ 일 때, B∖A 속하는 간선 e를 A에 추가해도 A∪{e}는 숲이어야 한다.

    • 설명: 숲 A와 B가 있다고 가정하자. 작은 숲에 간선을 추가해도 여전히 숲이다.

    • 결론: 숲의 증강성이 성립하기 때문에 매트로이드이다.

6️⃣매트로이드의 확장(Matroid Expansion)

매트로이드의 확장과 포화 (Extension and Maximal Set of Matroid)

💡요약: 확장 (Extension)은 집합 A에 원소 x를 추가해도 독립적이라면, x는 A를 확장한다.포화 (Maximal Set)란 A가 확장되지 않는 상태라면, A는 포화 상태임을 뜻한다.

✅ 매트로이드의 확장 (Extension)

  • 매트로이드 I는 "독립적인 집합"의 모음이다.

  • 집합 A가 이미 독립적이고, x라는 새 원소를 추가해도 여전히 독립적이라면,
    이 원소 x는 A를 확장할 수 있다는 뜻이다.

  • 의미:

    • 그리디 알고리즘에서 해를 하나씩 확장하여 최적해를 구성하는 과정과 동일합니다.

    • 원소를 추가해가며 전체 해집합으로 확장하는 과정을 나타냅니다.

  • 예제:

    • 최소 신장 트리 (Minimum Spanning Tree) 문제에서 간선 e를 현재 트리에 추가할 때 사이클이 없으면, 이는 트리를 확장하는 과정에 해당한다.

    • S={1,2,3}, I={∅,{1},{2},{1,2}}라고 가정하고 A = {1}일 때, 원소 x = 2를 추가하면 A∪{x} = {1,2}이고, {1,2} ∈ I 이므로 x는 A를 확장할 수 있다.

✅ 매트로이드의 포화 (Maximal Set)

  • 집합 A에 새로운 원소 x를 추가함으로써 독립성을 잃는다면, A는 더 이상 확장될 수 없다. 즉, 모든 가능한 원소를 추가해 더 이상 확장할 수 없는 상태이다.

  • 이 상태의 A를 포화 집합이라고 한다.

  • 의미:

    • 그리디 알고리즘의 종료 조건과 유사하다.

    • 최적해를 찾고 모든 해를 포함하면 알고리즘이 종료된다.

  • 예제:

    • 최소 신장 트리에서 모든 정점을 연결하고 더 이상 추가할 간선이 없으면, 이는 포화 상태를 나타낸다.

    • 위 예제에서S = {1,2,3}, I = {∅,{1},{2},{1,2}} 에서 A = {1,2}일 때, 새로운 원소 x = 3를 추가하면 A∪{x} = {1,2,3}이 되고, 결과적으로 {1,2,3} ∉ I 이므로 AAA는 더 이상 확장되지 않는다. 따라서 A={1,2}는 포화 집합이다.

✅ 매트로이드의 확장 정리

  1. 매트로이드의 포화 집합 (Maximal Set of a Matroid)

    • 매트로이드 I⊆2S 의 모든 포화 집합은 항상 같은 크기를 가진다는 것을 의미한다.

    • 포화 집합이란, 더 이상 확장될 수 없는 독립 집합이다.

  2. 숲 집합의 경우 (Forest Set Example)

    • 그래프 이론에서 숲 집합은 사이클이 없는 간선 집합(즉, 트리 또는 트리들의 집합)이다.

    • 숲 집합 F ⊆ 2E 의 포화 집합은 트리(Tree)가 되며, 이는 항상 ∣V∣−1 개의 간선을 포함한다. 정점이 5개라면 ∣V∣−1로 인해 트리는 4개의 간선을 가지게 된다.

  3. 설명: 최소 신장 트리 (MST) 문제를 예로 들면:

    • 서로 다른 방법으로 트리를 구성하더라도, 선택된 간선의 수는 항상 ∣V∣−1로 동일하다. 포화된 집합의 크기는 항상 일정하다.

✅ 가중치 매트로이드와 그리디 알고리즘 (Weighted Matroid & Greedy Algorithms)

💡요약: 그리디 알고리즘의 최적해를 보장하는 매트로이드 구조는 있을까? 있다. 가중치 매트로이드(Weighted Matroid) 이다.

  1. 가중치 매트로이드란?

    • 매트로이드에서 원집합 S의 원소들이 가중치(weight)를 가지는 매트로이드이다.

    • 매트로이드 I ⊆ 2S에서 각 원소에 가중치(양의 값)가 부여된 구조를 말한다.

    • 즉, 원소마다 중요도나 값어치를 나타내는 숫자가 매겨져 있다.

    • 예를들어 그래픽 매트로이드에서 간선의 가중치의 합이 최대가 되는 숲을 찾는 경우 → 최대 신장 트리 (Maximum Spanning Tree) 문제가 된다.

  2. 목표:

    • 가중치 매트로이드에서, 가중치의 합을 최대화하거나 최소화하는 해를 찾는것이 목표이다.

✅ 최대 가중치 합 구하기 (그리디 알고리즘)

  1. 알고리즘:

    • 초기 해 집합 A=∅

    • 원소들을 가중치 w기준으로 내림차순 정렬한다.

    • 각 원소 x ∈ S에 대해:

      • A ∪ {x} 이면, A ← A∪{x}

  2. 설명:

    • 가중치가 가장 큰 원소부터 하나씩 선택한다.

    • 선택된 원소들이 매트로이드의 독립 조건을 만족해야 한다.

    • 결과적으로 최대 가중치를 가지는 해를 구성하게 된다.

7️⃣ 문제 공간 탐색 (Problem Space Exploration)

💡요약: 매트로이드에서 문제 공간 탐색은 주어진 문제의 가능한 모든 독립 집합(independent sets)을 효율적으로 탐색하여 최적의 해를 찾는 과정이다. 매트로이드의 독립성 조건과 그리디 알고리즘의 구조적 특성은 이러한 탐색을 효율적으로 찾게 한다. 문제 공간 탐색 문제를 해결하는 방법은 크게 두 가지 알고리즘 유형으로 나뉜다.

✅ 구축형 알고리즘 (Constructive Algorithm)

  • 공집합에서 시작하여 해를 하나씩 추가하며 최적해를 구축해나가는 방식이다.

  • 기존에 배웠던 알고리즘과 비슷하다. 첫번째 해 선택, 두번째 해 선택, 세번째 해 선택하며 전체적으로 종료 조건을 만족할 때 해집합이 완료되고 종료된다.

  • "건설자적인 개념"으로 접근하는 방식이다.

✅ 구축형 알고리즘 과정(Process of Constructive Algorithms)

  • 공집합 → 최적해 원소 추가 → 온전한 해 완성

  • 매 단계마다 탐색 공간이 줄어들고, 최적해를 향해 나아간다. 각 단계에서 최적의 원소를 선택하게 된다.

✅ 구축형 알고리즘의 활용 예제

  • 최소 신장 트리 (MST): 프림 알고리즘, 크루스칼 알고리즘

  • Shortest Path: 다익스트라 알고리즘

    • 트리의 간선을 하나씩 추가하며 최적해를 구축해나간다.

💡중요포인트: 최적해를 구할 때, 그리디 알고리즘을 활용하여 효율적으로 해를 구성한다.

✅ 개선형 알고리즘 (Iterative Improvement Algorithm)

  • 처음부터 어떤 해에서 시작하는데, 이 해는 조건은 만족하지만 최적해는 아닌 해이다. 이 해를 조금씩 바꿔가며 최적해를 찾아간다.

  • 여행자의 관점으로 해를 조금씩 바꿔가며 최적해로 이동하는 알고리즘이다.

✅ 개선형 알고리즘 과정(Process of Improvement Algorithms)

  • 초기해 → 해를 수정 → 최적해 도달.

  • 초기해는 임의의 값일 수 있으며, 점진적으로 개선하여 최적해에 도달하게 된다.

✅ 개선형 알고리즘 활용 예제

  • 인공지능 (AI)에서 개선형 알고리즘이 많이 사용되고 있다.

  • AI 알고리즘은 최적해 탐색 과정에서 매트로이드 구조를 활용하여 효율성을 높인다.

💡중요포인트: 개선형 알고리즘은 탐색 과정에서 다양한 해를 경험하며 최적해를 탐색합니다.

✅ 매트로이드 구조와 두 유형의 알고리즘의 연관성

  1. 구축형 알고리즘: 매트로이드 구조는 구축형 알고리즘에서 최적해를 보장한다.

    • 예: 프림 알고리즘, 크루스칼 알고리즘.

  2. 개선형 알고리즘: 매트로이드 구조는 개선형 알고리즘에서도 최적해를 보장한다.

    • 이는 탐욕적 접근법과 독립적 조건을 이용해 효율적으로 최적해를 탐색할 수 있음을 의미한다.

    • 개선형 알고리즘의 유형은 아래에 설명할 예정이다.

문제 공간 탐색 (Problem Space Exploration) #1:

매트로이드 구조의 개선형 알고리즘 의사코드(Pseudocode of Improvement Algorithms in Matroid Structure)

  • 초기 상태

    • I: 매트로이드의 독립 집합.

    • A: 초기 해 집합 (온전한 해지만 최적해는 아님).

    • w[]: 각 원소의 가중치 배열.

  • 조건 검사:

    • w(a) < w(x) 기존 원소 a의 가중치가 새 원소 x의 가중치보다 작을 때.

    • A ∪ {x} - {a} ∈ I 원소 a를 제거하고 x를 추가한 새로운 집합이 매트로이드 조건을 만족할 때

  • 동작:

    • A ← A U {x} - {a} 조건을 만족하면 a를 제거하고 x를 추가한 새로운 해를 구성한다.

    • 조건을 더 이상 만족하지 않으면 반복 종료한다.

  • 반환: 최적화된 해 A를 반환한다.

💡중요 포인트 기존 원소 a를 제거하고, 새로운 원소 x를 추가한다. 변경된 해가 여전히 매트로이드 조건을 만족하면 이 변경을 유지한다.

문제 공간 탐색 (Problem Space Exploration of Matroid) #2:개선형 알고리즘에 필요한 개념(Concept you should know in Improvement Algorithms)

💡중요 포인트: 인접성과 지역 최적해는 개선형 알고리즘의 작동 방식과 한계를 이해하는 핵심 개념이다. 개선형 알고리즘이 "인접성"을 통해 탐색을 진행하지만, "지역 최적해"에 머물 수 있는 한계를 가진다는 점이다. 이를 탈출하거나 전체 최적해로 나아가기 위한 추가 전략이 필요하다.

✅ 인접성 (Adjacency)

  • 한 원소를 추가하거나 제거하여 다른 해로 이동 가능할 경우, 두 해가 인접 관계에 있다고 한다.

  • 인접성은 개선형 알고리즘에서 현재 해를 다른 해로 이동하는 기준이 된다.

✅ 지역 최적해 (Local Optimum, 끌개)

  • 개선형 알고리즘에서, 현재 해를 계속 개선해 나가다 보면 더 이상 나아갈 수 없는 지점에 도달하게 되는데, 이 지점이 지역 최적해(Local Optimum)이다.

  • 앞서 배운 그리디 알고리즘의 포물선 예제에서 A에서 출발해 인접한 해로 이동시에 더 나은 품질(더 작은 비용)을 가진 해로 계속 이동한다. 더 이상 나아갈 수 없을 때, 이는 지역 최적해가 된다.

  • 지역의 의미: 다양한 골짜기(최소값)가 존재할 경우,

    • 현재 위치한 골의 최저점이 지역 최적해가 된다.

    • 지역 최적해는 전체 최적해(global optimum)에 도달하지 못할 수 있다.

    • 전체 최적해와 달리 지역 최적해는 다양한 골(최소값)이 존재할 경우, 하나의 골에 머물게 된다.

문제 공간 탐색 (Problem Space Exploration of Matroid) #3: 개선형 알고리즘과 매트로이드 공간 정리 (Improvement Algorithms & Matroid Space Overview)

💡 핵심 개념

  • 매트로이드 공간 (Matroid Space) 에서 개선형 알고리즘은 국소 탐색 (Local Search) 만으로도 전역 최적해 (Global Optimum) 를 찾을 수 있다.

  • 이는 매트로이드 공간이 하나의 봉우리 (Peak) 또는 골 (Valley) 만 가지는 구조이기 때문에 가능한 것이다.

✅ 정리 1: 품질 좋은 해의 존재 (Existence of High-Quality Solution)

매트로이드 공간에서, 어떤 품질 좋은 해 (High-Quality Solution) a가 존재한다면,
a와 인접한 해 (Adjacent Solution) 중에서도 품질 좋은 해가 반드시 존재한다.

  • 의미 (Meaning): 개선형 알고리즘이 해를 변경하면서도 품질을 유지할 수 있는 근거가 된다.

✅ 정리 2: 국소 최적해와 전역 최적해의 관계 (Relationship Between Local and Global Optima)

특정 해 a 주변에 더 나은 품질의 해가 없다면, a는 전역 최적해 (Global Optimum)이다.

  • 의미 (Meaning): 매트로이드 공간에서는 지역 최적해 (Local Optimum) 가 곧 전역 최적해가 된다. 이는 매트로이드 공간이 봉우리 (Peak) 나 골 (Valley) 이 하나만 있는 구조이기 때문이다.

✅ 정리 3: 전역 최적해의 가중치 합 동일성 (Weight Consistency in Global Optima)

매트로이드 공간에서, 만약 두 개의 전역 최적해 (Global Optima) 가 존재한다면,
두 해의 가중치 합 (Sum of Weights) 은 항상 동일하다.

  • 예시 (Example): 프림 알고리즘과 크루스칼 알고리즘은 서로 다른 방식으로 최소 신장 트리를 찾는다. 두 알고리즘이 구한 트리는 다를 수 있지만, 가중치 합 (Sum of Weights) 은 동일하다.

  • 의미 (Meaning): 개선형 알고리즘에서도 최적해의 형태는 다를 수 있지만,
    결과적으로 "최적 비용 (Optimal Cost)" 은 동일하게 보장된다는 뜻이다.

✅ 정리 4: 동일한 가중치를 가진 해의 연결성 (Connectivity Between Equal-Weight Solutions)

매트로이드 공간에서, 동일한 가중치 (Weight) 를 가진 두 해는 인접 관계 (Adjacency Relationship) 를 따라 서로 연결될 수 있다.

  • 의미 (Meaning): 개선형 알고리즘은 인접 관계를 통해 해를 이동하며, 동일한 품질의 해 사이에서도 연결성 (Connectivity) 을 보장한다.

✅ 매트로이드의 특징

  • 봉우리 (Peak) 또는 골 (Valley) 이 하나인 구조:

    • 매트로이드 공간은 하나의 봉우리 또는 골만 가지는 단순한 구조를 가진다.

    • 이로 인해, 개선형 알고리즘이 지역 최적해에서 멈출 필요 없이 바로 전역 최적해를 찾을 수 있게된다.

  • 그리디 알고리즘의 적용 가능성 (Applicability of Greedy Algorithms):

    • 매트로이드 공간은 탐욕적 선택 조건 (Greedy Choice Property) 을 만족하므로,
      개선형 알고리즘으로 최적해를 보장한다.

Computer Algorithms

Part 2 of 19

Through this subjects, I will be learning how to think systematically through algorithms and develop problem-solving skills. Also, I'm hoping to learn how to perform programming quickly and efficiently by applying computer algorithms.

Up next

From Dijkstra to A: A Deep Dive into Graph Algorithms 2

Contents 1️⃣위상 정렬 (Topological Sorting)2️⃣최단 경로 알고리즘 (Shortest Path Algorithm)3️⃣다익스트라 알고리즘 (Dijkstra's Algorithm)4️⃣벨만-포드 알고리즘 (Bellman-Ford Algorithm)5️⃣모든 쌍 최단 경로 (All-Pairs Shortest Path)6️⃣강연결 요소 구하기 (Finding Strongly Connected Components, SCC)7...

More from this blog

My dev journey

125 posts