[Algorithm]Divide and Conquer & greedy: 분할 정복과 탐욕법에 대해 알아보자!

 

 

 

Divide and Conquer

분할 정복은 알고리즘의 전형적인 예 중 하나다. 보통 분할 정복 알고리즘은 아래 3가지 단계를 거친다.1. 분할하기(divide: 주어진 문제를 같은 형식의 하위 문제로 쪼갠다.2. 정복하기(conquer): 재귀적으로 하위 문제를 해결한다.3. 합치기(combine): 정답을 적절히 조합한다.

 

고전적인 분할 정복의 예로 병합 정렬(merge sort)이 있다. 병합 정렬은 배열을 두 반쪽으로 나누고, 재귀적으로 두 반쪽을 정렬하고 나서 정렬된 두 반쪽을 병합(merge)한다.

 

 

출처: geeksforgeeks

 

 

---

 

 

 

https://youtu.be/2Rr2tW9zvRg

 

 

이 영상의 Abdul Bari 선생님이 Divide And Conquer에 대해 설명해주는 영상이다.위에서 이야기했듯이 문제 P를 임의적으로 K개로 쪼개 각 쪼갠 문제를 Solving 과정을 거친다. 최종적으로, 쪼갠 문제들을 하나로 합친다.

 

 

 

 

수도 코드로 다시 정리해주셨다. 친절한 설명이다. 문제(p)를 쪼개서 

 

 

DAC(Divide And Conquer) 알고리즘에 문제(p)를 대입한다.문제가 작게 쪼개진 상태면(small(p)) 문제를 해결한다(Solving(p)).

 

문제가 큰 상태면,

문제(p)를 p1, p2... k 번째까지 쪼갠다.

DAC예 각각 대입한다 (DAC(p1), DAC(p2)... )

그리고 각 DAC를 합쳐준다.

 

아래 예시 코드는 각 배열의 요소들의 합을 반환한다.

function sum(arr) {
	let total = 0;
    for (let i of arr) {
    	total += i;
    }
    return total;
}	

console.log(sum([1, 2, 3, 4, 5]));

 

그렇다면, 위 코드를 분할 정복 스타일로 한다면, 어떻게 해야 할까?

아래와 같이 할 수 있다. 

 

function sum(arr) {
	if (arr.length === 0) return 0;
    return arr[0] + sum(arr.slice(1));
}	

console.log(sum([1, 2, 3, 4, 5]));

// 1 + sum([2, 3, 4, 5]);
// 2 + sum([3, 4, 5]);

// 0 + 5
// 5 + 4
// 9 + 3
// 12 + 2
// 14 + 1

 

Divide And Conquer에 관련한 주제는 아래와 같다.

1. Binary Search2. Finding maximum and minimum3. merge sort4. Quick Sort5. Strassem's matrix multiplication

 

 

---

 

Greedy Algorithms

그리디 알고리즘은 한 조각씩 솔루션을 구축하는 전형적인 예로써, 항상 즉각적이고 분명한 보상을 제공하는 다음 조각을 선택한다. 그래서 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾아, 이를 토대로 최종 문제의 해답(globally optimal solution)으로 이어지는 방식이다. 하지만, 항상 최적의 결과를 보장하지 못한다. 따라서, 아래 2가지 조건을 성립해야 최적의 해를 보장한다.

 

• 탐욕적 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는다.
• 최적 부분 구조: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법을 구성

 

예로 분할 가능 배낭 문제(Fractional Knapsack Problem)에 대해 생각해보자. 지역 최적화 전략은 최대 값 vs 무게 비율(중량비)을 가지고 있는 아이템을 선택하는 것이다. 이 전략은 아이템을 분할을 가능하도록 하기 때문에 글로벌 최적화 해결책으로 이끈다. 

 

 

출처: geeksforgeeks

 

쉽게 이야기하면, 탐욕 알고리즘은 결정의 순간마다 당장 앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종 해당에 도달하는 방법이다. 탐욕 알고리즘은 단계적으로 나누어 보면,

 

1. 선택 절차: 현재 상태에서 최적의 해답을 선택

2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가기

 

한 가지 예를 보자면,

편의점 캐셔인 내가 4,040원을 받아야 하는 상황에서 5,000원을 받는 상황을 상상해보자.

손님은 거스름돈을 최소한으로 받길 원한다. 어떻게 거슬러 줘야 할까?

 

1. 선택 절차: 최적의 해답으로 500원을 먼저 선택한다.

2. 적절성 검사: 1번 과정을 통해 선택된 동전의 합이 거슬러줘야 하는 금액을 초과하는지를 파악하고, 초과한다면 마지막에 선택한 동전을 삭제하고, 다시 1번 과정으로 돌아가 다른 동전을 선택한다.

3. 해답 검사: 선택된 동전의 합이 거슬러 줘야 하는 금액과 일치 여부 검사. 미통과시, 1번 과정으로 돌아간다.

 

결국, 500원 1개, 100원 4개, 50원 1개, 10원 1개를 거스름돈을 건네줄 것이다.

 

 

 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이다. 

그래서, 그래프나 정렬, 다익스트라 알고리즘까지 넓은 영역에서 사용된다.

 

Greedy Algorithms에 관련한 주제는 아래와 같다.

1. Activity Selection Problem

2. Hoffman Coding

3. Job Sequencing Problem

4. Fractional Knapsack Problem

5. Prim's Minimum Spanning Tree

 

 

 

 

 

출처: 

Yogesh Shinde  | https://youtu.be/mYhINCT6Wtc

GeeksforGeeks | https://bit.ly/2TNUEgY

GeeksforGeeks | https://bit.ly/3uYMFu8

GeeksforGeeks | https://bit.ly/2Rrwl7C

Abdul Bari | https://bit.ly/3z9o49y