[코테C++] Greedy

JeongChaeJin·2022년 9월 9일
CodingTest
0

CodingTestC++

목록 보기
6/6

Overview

  • 가장 좋아보이는 해답을 선택하는 알고리즘

기본적 Greedy Algorithm

최단 작업 우선 스케줄링

  • shortest- job- first scheduling
  • Example : 평균 대기 시간 최소로 만드는 대기열 순서
#include <vector>
#include <algorithm>
#include <numeric>

template<typename T>
auto compute_wating_times(std::vector<T>& service_items)
{
	std::vector<T>W(service_times.size());
    W[0] = 0;
    
    for (auto i = ; i < service_times.size(); i++)
    	W[i] = W[i - 1] + service_times[i - 1];
        
	return W
}
  • W[i] : i 번째의 Wating Time
    • 책 참고

분할 가능 배낭 문제

  • fractional knapsack problem
  • 0-1 knapsack problem은 NP-완전 문제로 다항 시간 솔루션 사용 불가 그런데, 분할 가능 배낭문제는 그리디 방식으로 해결 가능하다.
  • 문제 정의의 작은 차이가 문제 해결 방법에 큰 변화를 가져올 수 있다는 점을 확인하자.

0-1 배낭 문제

  • O = {O1, O2, ... On}
    • i 번째 O의 무게 Wi라고 정의
    • 최대 무게 T 배낭에 넣은 물건들의 무게 합이 T를 넘기면 안된다.
    • 가격 Vi 최대 무게를 넘지 않으면서 최대 가격을 내야된다 !
  • NP-완전 문제이므로 모든 조합을 조사해서 무게 T를 넘지 않는 가장 높은 가격을 찾아내야 한다.

분할 가능 배낭 문제

  • 주어진 물건을 원하는 형태로 얼마든지 분할할 수 있고 각 물건의 일부분만 배낭에 담을 수 있다고 가정
    • 곡물, 기름등을 원하는 양만큼 덜어서 배낭에 담는다고 생각
  • 단위 무게 당 가격을 기준으로 정렬하고 그리디 방식에 따라 단위 무게당 가격이 높은 순서로 물건을 선택
    • 단위 무게 당 가격이 비싼 물건들 위주로 선택된다.
#include <iostream>
#include <algorithm>
#include <vector>

struct Object
{
	int id;
    int weight;
    double value;
    double value_per_unit_weight;
    
    Object (int i, int w, double v) : id(i), weight(w), value(v),
    	value_per_unit_wiehgt(v / w) {}
        
	inline bool operator< (const Object& obj) const
    {
		return this->value_per_unit_weight < obj.value_per_unit_weight;
	}
    
    friend std::sotream& operator<<(std::ostream& os, const Object& obj);
};

auto fill_knapsack(std::vector<Object>& objects, int knapsack_capacity)
{
	std::vector<Object> knapsack_contents;
    knapsack_contents:reserve(objects.size());
    
    // 내림차순으로 단위 무게당 가격 기준으로 정렬
    std::sort(objects.begin(), objects.end());
    std::reverse(objects.begin(), objects.end());
    
    // 가장 가치있는 물건 먼저 배낭에 추가
    auto current_object = objects.begin();
    int current_total_weight = 0;
    while (current_total_weight < knapsack_capacity && current_object != objects.end())
    {
    	knapsack_contents.push_back(*current_object);
        
        current_total_weight += current_object->weight;
        current_object++;
	}
    
    // 마지막 추가 물건에 의해 배낭 최대 허용 무게가 초과된 경우
    int weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity;
    Object& last_object = knapsack_contents.back();
    if (weight_of_last_obj_to_remove > 0)
    {
    	last_object.weight -= weight_of_last_obj_to_remove;
        last_object.value -= last_object.value_per_unit_weight * weight_of_last_obj_to_remove;
	}
    
    return knapsack_contents;
}
  • 단위 무게당 가격 기준 내림차순 정렬 후
  • 배낭 최대 용량 까지 물건을 채워 넣는다.
  • 배낭 최대 무게 초과 시 마짐가에 넣은 물건 일부를 덜어내어 배낭 최대 무게에 맞도록 설정
int main()
{
	std::vector<Object> objects;
    objects.reserve(7);
    
    std::vector<int> weights {1, 2, 5, 9, 2, 3, 4};
    std::vector<double> values {10, 7, 15, 10, 12, 11, 5};
    
    for (auto i = 0; i < 7; i ++)
    {
		objects.push_back(Object(i + 1, weights[i], values[i]));
	}
    
    int knapsack_capacity = 7; // 최대 허용 무게
    auto solution = fill_knapsack(objects, knapsack_capacity);
  • 분할 가능 배낭 문제는 물건의 일부만을 배낭에 담을 수 있다는 점이 0-1 배낭 문제와 다르다.

그리디 알고리즘의 요구 조건

  • 앞에서는 그리디 접근 방식의 최적 솔루션을 제공하는 문제의 예였다.
  • 모든 문제에 그리디 방식을 적용할 수 있는 것은 아니다.
  • 그리디의 최적 솔루션은 최적 부분 구조, 그리디 선택 두 속성을 모두 갖고 있어야 얻을 수 있다.
  • 최적 부분 구조(Optional subsctructure) : 주어진 문제 P에 대한 최적 솔루션이 P의 부분 문제들의 최적 솔루션으로 구성될 경우, 문제 P가 최적 부분 구조를 갖는다고 말한다.
  • 그리디 선택 (greedy choice) : 주어진 문제 P에 대한 지역적 최적 솔루션을 반복적으로 선택해 전체 최적 솔루션을 구할 수 있을 경우, 문제 P가 그리디 선택 속성을 갖는다고 말한다.

최소 신장 트리 문제

  • MST, Minimum Spanning Tree 문제
  • 정점(Vertex)의 집합 V와 가중치를 갖는 Edge의 집합 E로 구성된 그래프 G = <V, E>가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 Tree를 구하시오.
    • 상수도관 네트워크, 도로 네트워크 설계
  • 최소 신장 트리 T를 구하는 그리디 알고리즘
      1. 그래프 G의 모든 Edge를 최소 Heap H에 추가
      1. H로부터 Edge e를 하나 꺼낸다. e는 모든 에지 중 가장 가중치가 작은 Edge
      1. e의 양 끝 정점이 이미 T에 있을 경우 e로 인해 T에서 사이클이 발생할 수 있다. 이런 경우 e를 버리고 2단계로 이동한다.
      1. 최소 신장 트리 T에 e를 추가하고 2단계로 이동한다.
    • 2 ~ 4를 반복하면서 가장 작은 가중치의 Edge를 찾고, 사이클 발생하지 않으면 해당 에지와 양 끝 정점을 최종 솔루션에 추가한다.
    • 이를 크루스칼 최소 신장 트리 알고리즘이라고 부른다.
  • 최소 신장 트리는 최적부분구조와 그리디 선택 속성을 갖는지 확인해보면 제대로 작동하는 알고리즘인지 알 수 있다.
    • 최적 부분 구조
      • 최소 신장 트리가 더 작은 최소 신장 트리의 집합으로 구성되지 않는다고 가정
        1. 그래프 G의 정점으로 구성된 최소 신장 트리 T가 있다고 가정한다. T에서 Edge e를 하나 선택하여 제거한다. e를 제거하면 T가 더 작은 트리인 T1 T2로 나눠진다.
        1. MST 문제가 최적 부분 구조 속성을 갖지 않는다고 가정했으므로 T1보다 작은 가중치를 갖는 신장 트리 T1'이 존재해야된다. 이 신장 트리 T1'과 T2를 e 엣지로 연결한 새로운 시장 트리를 T'이라고 해보자.
        1. T'의 전체 가중치가 T의 전체 가중치보다 작으므로 처음에 T가 최소 신장 트리라고 가정했던 가설이 틀리게 된다. 그러므로 MST 문제는 최적 부분 구조 속성을 만족해야된다.
    • 그리디 선택
      • 정점과 연결된 에지 중 최소 가중치 에지는 반드시 최소 신장 트리 T에 속해야 된다.
        1. 정점 v에 연결되어 있는 에지 중 최소 가중치를 갖는 에지를 (u, v)라고 가정한다.
        1. 만약 (u, v)가 T에 속하지 않는다면 T는 v와 연결되어 있는 다른 에지를 포함해야한다. 이 에지를 (x, v)라고 가정한다. (u, v)가 최소 가중치 에지이므로 (x, v)의 가중치는 (u, v)의 가중치보다 커야한다.
        1. T에서 (x, v)를 제거하고 (u, v)를 추가할 경우 전체 가중치가 더 작은 트리를 얻을 수 있다. 이는 T가 최소 신장 트리라는 가정에 위배된다. 그러므로 MST 문제는 그리디 선택 속성을 만족해야한다.

디스조인트-셋 자료 구조

  • Disjoint-Set or Union-Find 자료 구조는 트리 형태 원소로 구성된 Forest이다.
  • 각각의 원소는 숫자 ID에 의해 표현되며 Rank와 부모에 대한 포인터를 가진다.
  • make-set(x) 연산 지원
    • x를 ID로 갖는 원소를 디스조인트-셋 자료 구조에 추가한다.
    • 새로 추가한 운소의 랭크는 0, 부모 포인터는 자기 자신을 가리키도록 설정한다.
  • find(x) 연산 지원
    • 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동해 트리의 루트를 반환한다.
    • 루트 원소의 부노는 자신이다. make-set(x) 연산 시 각 원소는 트리의 루트이며 find() 연산 시 자기 자신이 반환된다.
    • union(x, y) 연산 지원
      • 두 개의 원소 x, y에 대해 union() 연산을 수행하면 먼저 x, y의 루트를 찾는다.
      • 두 루트가 같으면 x, y는 같은 트리에 속해있음을 의미한다. 이 경우 아무런 작업도 하지 않는다.
      • 만약, 두 루트가 다르면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정한다.
      • union(x, y) 연산을 거듭할 수록 더 많은 트리가 병합 되어 전체 트리 개수는 줄어들고, 각 트리의 크기는 점점 거대해진다.
  • 크루스칼 알고리즘 구현 방법
    • 그래프 정점 개수가 N이라면, 먼저 N개 원소를 갖는 디스조인트-셋 자료 구조를 초기화하고, 크루스칼 알고리즘 2단계 - 3단계에서 최소 힙을 이용해 가장 가중치가 작은 에지를 선택하고, 사이클 여부를 검사한다. 이 때 union(x, y) 연산을 활용할 수 있다. 즉, 에지의 양 끝 두 정점에 대해 union(x, y)를 수행하여 실제로 두 트리가 병합하면 해당 Edge를 MST에 추가한다. 만약 x, y 루트가 같으면 두 정점을 잇는 에지에 의해 사이클이 발생한다는 의미다. 그런 경우 아무 작업 없이 그대로 종료하고 해당 에지를 MST에 추가하지 않는다.
      1. 모든 정점을 이용해 디스조인트-셋 자료 구조를 초기화한다.
      1. 가중치가 가장 작은 에지를 MST에 추가한다.
      • union(2, 4)을 수행하고, (2, 4) 엣지를 MST에 추가한다.
      1. 크루스칼 알고리즘 대로 MST에 엣지를 추가하다보면, (1, 5) Edge를 검토할 차례가 나타난다. (그림참조) 1, 5가 같은 트리에 존재하는데, 해당 에지를 연결하면 사이클이 발생하므로 MST에 추가할 수 없다.

크루스칼 MST 알고리즘 구현

  • Disjoint-set 자료 구조를 사용하지 않는 크루스칼 알고리즘 시간 복잡도는 O(ElogE)이다.
    • E: Edge 개수
  • Disjoint-set 자료 구조 사용 시 O(Ea(V))로 줄어든다.
    • a는 여기서 아커만 함수의 역함수이다. 아커만 함수의 역함수는 로그 함수보다 훨씬 느리게 증가한다. 그러므로 정점 개수가 적은 그래프에서는 두 구현의 성능 차이가 작지만, 정점이 많은 그래프에서는 큰 성능 차이가 발생할 수 있다.

그래프 컬러링

  • 주어진 그래프 G에서 서로 인접한 정점끼리 같은 색을 가지지 않도록 모든 정점에 색상을 지정해야 한다. 는 것으로 정의가 된다.
  • 그래프 컬러링에서는 에지의 가중치는 사용하지 않는다.
  • 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기, 시험 시간표 작성 등을 모델링 한 후 컬러링 문제 형태로 해결
  • 그래프 컬러링에 필요한 최소 개수의 색상 수를 찾는 것은 NP-완전 문제이므로 문제를 조금 변경하여 시간 복잡도를 크게 변경할 수 있다.

구현

  • 그래프 컬러링의 평가는 얼마나 적은 수의 색상을 사용했는가에 의해 결정된다.
  • 가능한 적은 수의 색상을 사용하는 최적의 그래프 컬러링 방법 찾기는 NP-완전 문제이지만 그리디 방식이 유용한 근사치를 제공하곤 한다.
    • 컴파일하는 프로그램의 변수에 CPU 레지스터 할당 시 그래프 컬러링이 사용된다.
profile
JeongChaeJin
OnePunchLotto
이전 포스트

[코테C++] 분할 정복 2

0개의 댓글