[Algorithm] 탐욕 알고리즘

김동건·2026년 9월 30일

부분집합 · 조합 · 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

부분집합은 이진수를 이용해서도 표현할 수 있다.

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
→ 물건을 나눌 수 있음
→ 단위 무게당 가치가 높은 순서로 선택

활동 선택 문제
→ 종료 시간이 가장 빠른 활동부터 선택