합병 정렬 알고리즘이란? 합병 정렬은 입력을 2개의 부분 문제로 분할해 나간다. 이 동작을 더 이상 나눌 수 없을 때 까지 재귀적으로 하게 된다. 더 이상 나눌 수 없게 된 문제를 정렬해서 올바른 자리에 위치시킨다. 그림으로 설명하면 이런 과정을 거치면서 동작하는 정렬 알고리즘을 합병 정렬 알고리즘이라고 한다. 전체 코드 #include #define SIZE 8 // 배열 사이즈 선언 using namespace std; // 숫자를 새로운 공간에 할당하는 merge함수 void merge(int array[], int start, int new_Index, int end) { int new_Array[SIZE]; // 새로운 배열 선언 int sta = start, mid = new_Index + 1..

집합 커버(Set Cover) 문제란 n개의 원소를 가진 집합 U = {0,1,2,…n-1} 가 있다고 한다. U의 부분집합들을 원소로 하는 집합 F(Power Set)가 주어지면, F 를 최소한으로 선택하여 집합 U를 커버하면 해결되는 문제이다. 좀 더 쉽게 설명하면 U = {1,2,3,4} 일 때 F = {{1}, {2}, {3}, {4}, {1, 4}, {1, 2, 4}, {1, 3, 4}} 이다. 그러면 여기서 {1}, {2}, {3}, [4} 를 선택하면 집합 U를 커버할 수가 있다. 또 {3}, {1, 2, 4} 이런 형태로도 집합 U를 커버할 수가 있다. 이 문제는 Greedy Algorithm 으로는 해결할 수 없는 문제이다. 이 문제를 해결하는 알고리즘을 적용시켜보기 위하여 아래의 예제를..

정점 커버(Vertex Cover) 문제란? 그래프가 주어지면 그래프의 간선의 양 끝 정점 중 적어도 하나의 정점을 포함하는 정점들의 집합들 중에서 최소 크기의 집합을 찾는 문제이다. 조금 더 쉽게 설명하면 그래프가 주어졌을때 가장 많은 edge와 연결된 vertex를 선택하게 된다. 그리고 선택한 vertex는 기록하고, 그 정점과 연결된 모든 간선을 지워나가면서 모든 그래프의 정점과 간선이 사라지도록 동작한다. 그리고 그때 선택된 정점의 개수는 최소가 되어야 한다. 예를 들어서 설명하면 위와 같은 그래프가 주어졌을 때 이 그래프의 정점을 커버하는 집합은 {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1} 이 존재한다. 여기서 {2}, {3} 은 그래프 G의 모든 정점을 커버할 수 없..