[Algorithm] 탐욕 알고리즘

Об этом предложении

부분집합 · 조합 · Greedy 이번에는 완전탐색에서 자주 사용하는 부분집합, 조합 과 현재 상황에서 가장 좋은 선택을 하는 Greedy 알고리즘 을 정리한다. 1. 부분집합 주어진 집합에서 일부 원소를 선택하여 만든 집합이다. 아무것도 선택하지 않은 공집합 도 포함한다. 원소가 N 개라면 부분집합의 개수는 2^N 개이다. 예를 들어 {A, B, C} 의 부분집합은 다음과 같다. {} {A} {B} {C} {A, B} {A, C} {B, C} {A, B, C} 재귀를 이용한 부분집합 각 원소마다 선택하거나 선택하지 않는 2가지 경우 를 만든다. Branch = 2 Level = 원소의 개수 arr = ['O', 'X'] path = [] def run(level): if level == 3: print(path) return for i in range(2): path.append(arr[i]) run(level + 1) path.pop() run(0) O 는 선택, X 는 선택하지 않는 경우이다. Binary Counting 부분집합은 이진수를 이용해서도 표현할 수 있다. 000 001 010 011 100 101 110 111 0 : 선택하지 않음 1 : 선택 예를 들어 101 이라면 {A, C} 가 선택된 것이다. arr = ['A', 'B', 'C'] n = len(arr) def get_sub(target): for i in range(n): if target & 0x1: print(arr[i], end=' ') target >>= 1 target & 0x1 로 마지막 비트가 1 인지 확인하고, target >>= 1 로 다음 비트를 확인한다. 2. 조합 서로 다른 N 개의 원소 중 R 개를 순서 없이 선택한다. 순열과 다르게 선택한 순서는 고려하지 않는다. 예를 들어 A, B, C 중 2개를 선택하면 AB AC BC 가 된다. AB 와 BA 는 같은 경우이다. 순열 : 순서가 중요하다. 조합 : 순서가 중요하지 않다. 조합 구현 조합에서는 이미 확인한 원소를 다시 확인하지 않기 위해 start 를 사용한다. arr = ['A', 'B', 'C', 'D', 'E'] path = [] def recur(cnt, start): if cnt == 3: print(*path) return for i in range(start, len(arr)): path.append(arr[i]) recur(cnt + 1, i + 1) path.pop() recur(0, 0) 핵심은 다음 재귀에서 i + 1 부터 확인하는 것이다. A 선택 → B, C, D, E 확인 B 선택 → C, D, E 확인 C 선택 → D, E 확인 이렇게 하면 AB 를 선택한 뒤 BA 를 다시 만드는 중복을 막을 수 있다. 3. 탐욕 알고리즘 Greedy 현재 상황에서 가장 좋아 보이는 선택 을 반복하는 알고리즘이다. 모든 경우를 확인하는 완전탐색과 달리 하나의 기준을 정해서 선택한다. 현재의 최선이 전체의 최선이 되는 문제에서 사용할 수 있다. 동전 문제 동전이 다음과 같이 있다고 하자. 500원 100원 50원 10원 1730원 을 최소 개수의 동전으로 거슬러 준다면 큰 동전부터 사용한다. 500원 × 3 = 1500원 100원 × 2 = 200원 10원 × 3 = 30원 총 8개 coin_list = [500, 100, 50, 10] target = 1730 cnt = 0 for coin in coin_list: possible_cnt = target // coin cnt += possible_cnt target -= coin * possible_cnt print(cnt) target // coin 으로 현재 동전을 최대 몇 개 사용할 수 있는지 구한다. Greedy가 항상 정답은 아니다 동전이 다음과 같이 있다고 하자. 70원 50원 10원 100원 을 만들어야 할 때 큰 동전부터 선택하면 70 + 10 + 10 + 10 = 4개 가 필요하다. 하지만 실제 최소 동전은 50 + 50 = 2개 이다. 따라서 Greedy는 단순히 가장 큰 값이나 가장 작은 값을 선택하는 것이 아니라, 문제에 맞는 선택 기준이 성립하는지 확인하는 것이 중요하다. 4. Greedy 대표 문제 Knapsack 정해진 무게 안에서 최대 가치를 만드는 문제이다. 예를 들어 최대 30kg 까지 담을 수 있고 다음 물건들이 있다고 하자. 물건 무게 가치 물건1 5kg 50만원 물건2 10kg 60만원 물건3 20kg 140만원 일반적인 0-1 Knapsack 에서는 물건을 통째로 넣거나 넣지 않아야 한다. 따라서 단순히 가치가 높은 물건이나 kg 당 가치가 높은 물건부터 선택한다고 해서 항상 정답이 되는 것은 아니다. Fractional Knapsack Fractional Knapsack은 물건을 필요한 만큼 잘라서 넣을 수 있는 문제 이다. 이 경우에는 가치 / 무게 즉, 단위 무게당 가치가 높은 물건부터 선택하는 Greedy 방식 을 사용할 수 있다. 0-1 Knapsack → 물건을 나눌 수 없음 Fractional Knapsack → 물건을 나눌 수 있음 활동 선택 문제 여러 개의 회의가 있을 때 서로 겹치지 않으면서 최대한 많은 회의를 선택하는 문제이다. 이 문제에서는 종료 시간이 가장 빠른 회의부터 선택한다. 진행 과정은 다음과 같다. 1. 종료 시간이 빠른 순서로 정렬한다. 2. 가장 빨리 끝나는 회의를 선택한다. 3. 선택한 회의가 끝난 뒤 시작할 수 있는 회의를 찾는다. 4. 그중 다시 가장 빨리 끝나는 회의를 선택한다. 5. 반복한다. 정리 부분집합 → 각 원소를 선택 / 선택하지 않음 → 경우의 수는 2^N Binary Counting → 0과 1로 부분집합 표현 조합 → 순서 없이 선택 → start를 이용해서 중복 방지 Greedy → 현재 가장 좋아 보이는 선택을 반복 → 선택 기준이 전체 최적해로 이어지는지 확인 0-1 Knapsack → 물건을 나눌 수 없음 Fractional Knapsack → 물건을 나눌 수 있음 → 단위 무게당 가치가 높은 순서로 선택 활동 선택 문제 → 종료 시간이 가장 빠른 활동부터 선택