[알고리즘🧩] 완전 검색 / 탐욕 알고리즘

« 2026/04 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Tags more

Archives

Today

Total

관리 메뉴

Dionysus

[알고리즘🧩] 완전 검색 / 탐욕 알고리즘 본문

CS 및 알고리즘 공부/알고리즘

[알고리즘🧩] 완전 검색 / 탐욕 알고리즘

Gogumiing 2024. 9. 3. 11:04

💬 부분 집합

💬 조합 (combination)

💬 Greedy(탐욕)

💬 연습문제

💬 부분 집합

부분 집합은 '공집합을 포함해, 집합에 포함된 원소들을 가지는 집합'이다. 이것을 코드로 구현한다면 어떻게 할 수 있을까?

✅ 완전탐색

재귀 호출을 이용한 완전탐색으로 부분 집합을 구할 수 있다. (학습용으로 추천하는 방법!)

예를 들어, {MIN, CO, TIM} 에 대해 완전탐색으로 부분집합을 구해보자.

이것을 코드로 구현해보면 아래와 같다.

# 완전탐색으로 부분 집합을 만들어보자.

arr = ['O', 'X']
path = []
name = ['MIN', 'CO', 'TIM']

def print_name():
    print('{', end = ' ')
    for i in range(3):
        if path[i] == 'O':
            print(name[i], end = ' ')
    print('}')


def run(lev):
    if lev == 3:
        print_name()
        return
    
    for i in range(2):
        path.append(arr[i])
        run(lev + 1)
        path.pop()


run(0)


"""
{ MIN CO TIM }
{ MIN CO }
{ MIN TIM }
{ MIN }
{ CO TIM }
{ CO }
{ TIM }
{ }

"""

✅ 바이너리 카운팅(Binary Counting)

2진수와 비트연산을 이용하여 부분 집합을 구할 수 있다. (실전용으로 추천!)

만들 수 있는 집합의 총 개수는 2^n개이며, 이는 1 << n 공식(bit shifting)을 사용하여 빠르게 구할 수 있다.

print(pow(2, 3))      # 8
print(1 << 3)         # 8

바이너리 카운팅을 코드로 구현해보자.

# 바이너리 카운팅(Binary Counting)

arr = ['A', 'B', 'C']
n = len(arr)

def get_sub(target):
    for i in range(n):
        # 비트 하나하나를 확인하여 1이라면 출력한다.
        if target & 0x1:
            print(arr[i], end = ' ')
        target >>= 1


for target in range(0, 1 << n):            # range(0, 8)
    print('{', end = ' ')
    get_sub(target)
    print('}')
    
    

"""
{ }
{ A }
{ B }
{ A B }
{ C }
{ A C }
{ B C }
{ A B C }

"""

✅ 단순 반복문으로 구현

name = ['MIN', 'CO', 'TIM']
subsets =[[]] 


def makeSubset():
    for n in name:
        size = len(subsets)
        for s in range(size):
            subsets.append(subsets[s] + [n])


makeSubset()
print(subsets)

"""
출력: [[], ['MIN'], ['CO'], ['MIN', 'CO'], ['TIM'], ['MIN', 'TIM'], ['CO', 'TIM'], ['MIN', 'CO', 'TIM']]
"""

💬 조합 (combination)

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 한다. (cf. 순열: 순서가 존재함)

for문으로 구현
N명 중 k명을 뽑는 조합은 k중 for문으로 구현이 가능하다. (너무 깊어질 수 있어 실전 사용은 비추천!)

arr = ['A', 'B', 'C', 'D', 'E']

for i in range(len(arr)):
    start1 = i + 1
    for j in range(start1, len(arr)):
        start2 = j + 1
        for k in range(start2, len(arr)):
            print(arr[i], arr[j], arr[k])
            
            
"""
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E

"""

재귀 호출로 구현

arr = ['A', 'B', 'C', 'D', 'E']
path = []
n = 3


def run(lev, start):
    if lev == n:
        print(path)
        return
    
    for i in range(start, len(arr)):
        path.append(arr[i])
        run(lev + 1, i + 1)             # 재귀 호출
        path.pop()


run(0, 0)


"""
['A', 'B', 'C']
['A', 'B', 'D']
['A', 'B', 'E']
['A', 'C', 'D']
['A', 'C', 'E']
['A', 'D', 'E']
['B', 'C', 'D']
['B', 'C', 'E']
['B', 'D', 'E']
['C', 'D', 'E']

"""

💬 Greedy (탐욕)

결정이 필요할 때, 현재 기준으로 가장 좋아 보이는 선택지를 결정하여 답을 도출하는 알고리즘으로, 대표적인 문제 해결 기법 중 하나이다. (다만 그리디 알고리즘은 예외 없이 모든 경우가 맞는 규칙인지 아닌지 증명이 어려우므로, 익숙한 유형이 아니라면 적용하는 것이 어렵다.)

📌 대표적인 문제 해결 기법

- 완전 탐색(Brute - Force)
답이 될 수 있는 모든 경우를 시도해보는 알고리즘

- Greedy(탐욕)
결정이 필요할 때, 가장 좋아보이는 선택지로 결정하는 알고리즘

- DP(Dynamic Programming, 동적 계획법)
과거의 데이터를 이용하여 현재의 데이터를 만들어 내는 문제 해결 기법

- 분할 정복
큰 문제를 작은 문제로 나누어 해결하는 문제 해결 기법

✅ 그리디(Greedy)의 핵심 조건

탐욕적 선택 조건(Greedy Choice Property): 각 단계의 선택이 이후 선택에 영향을 주지 않음
최적 부분 구조(Optimal Substructure): 각 단계의 최선의 선택이, 전체 문제의 최선의 해가 됨
증명 방법
1. 각 단계에서 최적해를 찾아야 함
2. 단계의 결과들을 합하는 방법을 찾아야 함
3. (각 단계의 합) == (전체 문제의 합)이라는 것을 증명해야 함

✅ (예제) 동전 교환 문제

{10, 50, 100, 500}의 총 4종류의 동전이 있을 때, 손님의 돈을 최소한의 동전 수로 교환해주려고 한다. 만약 1,730원을 거슬러주기 위해 사용할 수 있는 최소 동전의 개수는 몇 개인가?

그리디 알고리즘 → 큰 동전부터 최대한 거슬러 주는 방법을 선택
500원 x 3개 + 100원 x 2개 + 10원 x 3개 → 최소 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)    # 8

✔ 그리디(Greedy) 알고리즘에서 발생할 수 있는 예외 상황
만약 주어진 동전이 {10, 50, 70}일 때, 100원을 거슬러 주어야 하는 경우, 그리디(Greedy)로 접근하면 액수가 큰 동전을 먼저 선택하므로 총 4개의 동전을 답하게 된다. 그러나 실제로는 50원 동전 2개만 사용하면 되므로 예외 상황이 발생하게 된다.

💡 그리디(Greedy)가 성립하는 경우 vs 성립하지 않는 경우
- 성립하는 경우: {10, 50, 100, 500} 처럼 모든 동전이 배수 관계인 경우
- 성립하지 않는 경우: {10, 50, 70} 처럼 모든 동전이 배수 관계가 아닌 경우

완전 탐색 → 0원이 될 때까지 모든 경우를 다 시도해보고, 최소 Level이 되는 경우를 찾음

✅ (예제) 화장실 문제

기숙사에 화장실이 하나 있고 A ~ D 학생이 이곳을 사용한다고 할 때, 대기 시간의 누적합의 최소를 구하라.

(대기 시간의 누적합은 모든 학생 각각의 대기 시간을 합한 것을 의미한다.)

A: 15분
B: 30분
C: 50분
D: 10분

▶ 가장 짧은 시간을 사용하는 학생이 먼저 사용하는 방법 → 최소 시간 반환

▶ 가장 긴 시간을 사용하는 학생이 먼저 사용하는 방법 → 최대 시간 반환

✔ 위와 같이 하나가 작업하고 있을 때, 다른 것에 영향을 주는 것(e.g. 대기, 비용 지불 등)과 같은 문제는 그리디(Greedy)로 해결이 가능하다.

✅ (예제) 0-1 Knapsack → 그리디(Greedy) 적용 불가

도둑이 물건을 훔친다고 할 때, 물건의 개수(N)과 물건별 무게(W), 그리고 가격(P)이 주어질 때 어떤 물건을 담아야 도둑이 최대 이득을 볼 수 있을지 구하라. (도둑은 최대 30kg의 짐을 가져갈 수 있다.)

▷ 정답은 물건2와 물건3을 선택하는 것인데, 이것은 그리디(Greedy)로 찾기 어렵다.

▷ 따라서 0-1 Knapsack 문제는 완전탐색 또는 DP(Dynamic Programming, 동적 계획법)으로 접근해야 한다.

✅ (예제) Fractional Knapsack 문제

0-1 Knapsack와 달리, 물건을 원하는 만큼 자를 수 있는 문제이다. kg당 가격이 가장 높은 물건을 최대한 담으면 되므로 , 이때는 그리디(Greedy)가 성립한다.

# Fractional Knapsack 소스코드

n = 3
target = 30                                     # Knapsack kg 제한
things = [(5, 50), (10, 60), (20, 140)]         # (kg, price)

# (price / kg) 기준으로 내림차순
things.sort(key = lambda x:(x[1]/x[0]), reverse = True)

sum = 0
for kg, price in things:
    per_price = price / kg

    # 만약 가방에 남은 용량이 얼마되지 않는다면,
    # 물건을 잘라 가방에 넣고 끝냄
    if target < kg:
        sum += target * per_price
        break

    sum += price
    target -= kg

print(int(sum))             # 220

✅ (예제) 활동 선택(Activity-selection problem) 문제

아래와 같이 총 10개의 회의 요청이 존재할 때, 하나의 회의실을 사용한다고 하면 어떤 기준으로 선택해야 최대한 많은 횟수의 회의를 진행할 수 있을까?

{(5, 9), (6, 10), (8, 11), (1, 4), (3, 5), (1, 6), (5, 7), (3, 8), (2, 13), (12, 14)}

▷ 그리디(greedy)로 해결하는 경우: 종료 시간이 가장 빠른 회의를 먼저 선택하면 됨

💬 연습문제

1. [부분 집합] 민철이는 {A, B, C, D, E}의 친구가 있다. 이 중 최소 2명 이상의 친구를 선정하여 함께 카페를 가려고 한다면, 총 몇 가지의 경우가 가능할까?

friends = {'A', 'B', 'C', 'D', 'E'}
n = len(friends)

def get_sub(target):
    cnt = 0                 # 1의 개수를 셀 수 있음
    for i in range(n):
        if target & 0x1:
            cnt += 1
        target >>= 1
    return cnt


result = 0
for target in range(2, 1 << n):
    if get_sub(target) >= 2:            # bit 2개 이상 1이라면,
        result += 1
print(result)

💡 'target & 0x1' 로 표현한 이유는 무엇일까?

위와 같이 16진수로 표현한 이유는 아래와 같다.
1. 비트 연산임을 명시하기 위해서
2. 조금 더 큰 비트라면 2진수는 가독성이 떨어지기 때문에

2. [부분집합] 아래 10개 정수 집합에 대한 모든 부분 집합 중 원소의 합이 0이 되는 부분집합을 모두 출력하시오.

{-1, 3, -9, 6, 7, -6, 1, 5, 4, -2}

3. [순열] {A, B, C, D, E} 5명 중 3명을 뽑을 수 있는 모든 경우 출력하라.

4. [조합] 주사위 눈금 N개를 던져서 나올 수 있는 모든 조합을 출력하라. (N = 3)

dice = [1, 2, 3, 4, 5, 6]
N = 3
path = []

def run(lev, start):
    if lev == N:
        print(path)
        return
    
    for i in range(start, len(dice)):
        path.append(dice[i])
        run(lev + 1, i + 1)
        path.pop()


run(0, 0)

"""
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
[2, 5, 6]
[3, 4, 5]
[3, 4, 6]
[3, 5, 6]
[4, 5, 6]

"""

'CS 및 알고리즘 공부 > 알고리즘' 카테고리의 다른 글

[알고리즘🧩] 분할정복 / 이진검색 (0)	2024.09.04
[알고리즘🧩] 이진 탐색 (Binary Search) (0)	2024.08.14
[알고리즘🧩] 큐 (Queue) (0)	2024.08.13

'CS 및 알고리즘 공부/알고리즘' Related Articles

Dionysus

[알고리즘🧩] 완전 검색 / 탐욕 알고리즘 본문

[알고리즘🧩] 완전 검색 / 탐욕 알고리즘

💬 부분 집합

💬 조합 (combination)

💬 Greedy (탐욕)

💬 연습문제

'CS 및 알고리즘 공부 > 알고리즘' 카테고리의 다른 글

티스토리툴바