Chapter09. 억지 기법과 탐욕적 전략

09-1 문제 해결 과정

알고리즘 개발 과정

 

문제의 이해

문제를 정확히 이해, 조금이라도 애매한 부분들을 없애야 함

올바른 알고리즘 → '대부분의 입력'이 아닌 '모든 유효한 입력'에 대해 정확한 해답을 구할 수 있어야 함

 

설계 방향 결정

알고리즘을 어떤 방향으로 설계할지 결정

사용할 컴퓨터의 방식에 따라 순서적(sequential) 알고리즘으로 개발할 수도 있지만, 병렬처리(parallel) 방식을 선택할 수도 있음

대부분의 문제는 정확한 해답, 최적해를 요구하지만, 근사해를 구해도 되는 경우도 많음 → 어떤 해를 구할 것인지 결정해야 함

 

근사해를 고려해야 하는 상황

• 정확한 해 자체를 구할 수 없는 문제
  ex) 제곱근 문제
• 계산량이 너무 많아져서 현실적인 시간에 해결할 수 없는 문제
• 정확한 해를 구하기 위한 알고리즘의 중간 단계에서 근사해가 사용되는 경우
  ex) 분기한정 기법

 

알고리즘 설계

알고리즘 설계 기법

• 억지(brute-force) 기법: 문제의 정의를 가장 직접 사용하는 방법, 원하는 답을 구할 때까지 모든 가능한 경우 테스트
• 탐욕적(greedy) 기법: 어떤 결정을 해야 할 때마다 '그 순간에 최적'이라고 생각되는 것을 선택하는 방법
• 분할 정복(divide-and-conquer): 주어진 문제를 여러 개의 더 작은 문제로 반복적으로 분할하여 해결 가능한 충분히 작은 문제로 만든 다음 해결하는 전략
• 동적 계획법(dynamic programming): 분할 정복과 마찬가지로 작은 문제로 나누지만 분할 정복과 달리 작은 문제를 해결한 결과를 '저장'하여 다음에 더 큰 문제를 해결할 때 사용 
• 공간으로 시간을 버는 전략: 추가적인 공간을 사용하여 처리시간을 줄이는 전략
• 백트래킹과 분기한정 기법: 상태공간트리에서 해를 단계적으로 찾아가는 과정에서 현재의 해가 최종해가 될 수 없다고 판단되면 더는 탐색하지 않고 되돌아가서 다른 후보해를 탐색하는 방법
  효율을 높이기 위해 분기 한정 기법을 추가로 사용할 수도 있음

 

알고리즘의 정확성

작성된 알고리즘이 주어진 문제의 모든 유효한 입력에 대해 유한한 시간 안에 정확한 해를 구한다는 것을 보임

• 실험적 분석: 다양한 입력을 이용해 알고리즘을 테스트하여 타당성을 보이는 방법
  모든 가능한 입력 사례들을 포함하기 어려움, 충분한 테스트가 어느 정도인지 알 수 없음
  알고리즘이 틀렸다는 것은 하나의 입력 사례만으로도 충분
•  증명적인 분석: 수학적으로 타당성을 증명하는 방법
  수학적 귀납법 등이 자주 사용됨, 알고리즘에 따라 증명이 매우 어려울 수도 있음

 

알고리즘 분석

알고리즘이 정확히 동작한다면 알고리즘이 얼마나 효율적인가를 고려

시간 효율성과 공간 효율성으로 나눌 수 있는데, 보통 시간 효율성이 더 중요하게 생각됨

 

알고리즘 구현

알고리즘의 설계가 끝나고 정확성이 입증되었으면 알고리즘을 특정 프로그래밍 언어로 구현

실행 효율을 높이기 위해서는 컴파일(compile) 기반 언어 사용

빠른 구현과 알고리즘의 동작 확인 등을 위해서는 인터프리터(interpreter) 기반 언어 사용

 

---

09-2 억지 기법

억지 기법(brute-force): 문제의 정의를 바탕으로 한 가장 직접적인 해결 방법. 단순한 or 순진한(naive) 전략이라고도 불림

보통 문제에서 특별한 시간 조건이나 공간 조건이 주어져 있지 않았을 때 사용할 수 있음

별로 효율적이지는 않음

 

억지 기법의 의미

• 해결하지 못하는 것보다는 단순하게라도 해결하는 것이 좋음
• 쉬운 문제를 어렵게 풀 필요X
• 매우 광범위한 문제에 적용할 수 있는 알고리즘 설계 기법
• 입력의 크기가 작은 경우 충분히 빠를 수 있음
• 더 효율적인 알고리즘의 설계와 분석을 위한 이론적인 기반이 됨

 

문자열 매칭 문제 (억지 기법을 이용한 문제 해결)

길이가 n인 입력 문자열 T와 길이가 m인 패턴 문자열 P가 주어졌을 때, T에서 가장 먼저 나타나는 P의 위치를 찾는 문제

 

억지 기법 알고리즘 설계

텍스트의 첫 번째 문자 위치에 패턴을 놓고 한 문자씩 비교
서로 다른 문자가 나오면 패턴을 다음 위치로 옮겨 다시 앞의 과정을 성공한 매칭이 나타날 때까지 반복

"HELLO WORLD" 에서 "LO" 찾는 경우

(패턴 첫 문자) 'L' ≠ 'H' (텍스트 첫 문자) → 전체 패턴을 다음 위치로 이동

2에서 패턴의 문자 'L' 과 텍스트 문자 'L' 일치 → 패턴의 두 번째 문자 'O'와 텍스트 비교  

다르기 때문에 다음 위치로 이동 → 3에서 패턴의 모든 문자 일치, 패턴 위치 3 반환

 

문자열 매칭(억지 기법)

def string_matching(T, P):      # T: 입력 문자열(텍스트), P: 탐색 패턴
    n = len(T)      # n: 텍스트의 길이
    m = len(P)      # m: 패턴의 길이

    for i in range(n-m+1):
        j = 0
        while j < m and P[j]==T[i+j]:
            j =j + 1
        if j == m:
            return i    # 매칭 성공
    return -1       # 매칭 실패

string_matching('HELLO WORLD', 'LO') → 3 반환

string_matching('HELLO WORLD', 'HI') → -1 반환

 

복잡도 분석

입력의 크기와 패턴의 길이가 알고리즘의 처리시간에 영향

입력 크기는 텍스트의 크기 n과 패턴의 길이 m으로 두 가지

 

입력의 크기, 구성에 에 따라 비교 연산(P[j]==T[i+j])이 몇 번 실행되는가

• 최선의 경우: T의 맨 앞 문자열이 패턴 P와 일치할 때 → m번의 비교만으로 문자열 매칭 종료 ⇒ O(m)
• 최악의 경우: 찾는 패턴이 없어 패턴을 텍스트의 처음(0)부터 끝(n-m)까지 움직여야 함 → n-m+1번 시작 위치 달라짐
  + 각 위치에서도 패턴의 모든 문자를 비교하는 경우
  ex) T: "AAAAAAAA?", P: "AAB"
  모든 위치(n-m+1)에서 패턴의 모든 문자(m) 비교 → m(n-m+1)번 비교 
  ⇒ n >> m 이면 최악의 복잡도: O(nm)

평균적인 경우 O(n)에 가까운 성능을 보임

 

배낭 채우기(Knapsack Problem)

0-1 배낭 채우기 문제(0-1 knapsack problem)

무게가 각각 w i 이고 가치가 val i 인 n개의 물건이 있습니다. 이것을 넣을 배낭의 용량(최대 무게)은 W인데, 이를 초과해서 넣을 수는 없습니다. 물건들의 가치의 합이 최대가 되도록 배낭을 채웠을 때, 배낭의 최대가치를 구해보세요. 단, 하나의 물건을 잘라서 일부만 넣을 수는 없습니다.

 

w(배낭 용량): 50

물건별 (무게, 가치): A (10, 60), B (20, 100), C (30,120)

 

가능한 모든 경우

넣는 물건	A	B	C	A, B	B, C	A, C	A, B, C
무게 합	10	20	30	30	50	40	60
가치 합	60	100	120	160	220	180	280

 

 

억지기법 알고리즘 설계

가장 직접적인 전략: 완전 탐색

n개의 물건의 집합에 대한 모든 부분집합을 만들고, 무게 합이 배낭 용량을 넘지 않으면서 가치가 최대인 것을 찾음

 

원소의 개수가 n인 집합의 부분집합 수: 2^n

 

각 숫자에 대한 이진수의 각 비트 정보를 이용

0-1 배낭 채우기(억지 기법)

def Knapsack01_BF(wgt, val, W):
    n = len(wgt)        # 전체 물건의 수
    bestVal = 0         # 배낭의 최대 가치

    for i in range(2**n):
        s = [0]*n
        for d in range(n):
            s[d] = i%2
            i = i//2

        sumVal = 0
        sumWgt = 0
        for d in range(n):
            if s[d] == 1:
                sumWgt += wgt[d]
                sumVal += val[d]
            
        if sumWgt <= W:
            if sumVal > bestVal:
                bestVal = sumVal

    return bestVal      # 최대 가치 반환

weight = [10, 20, 30, 25, 35]    # 물건별 무게

value = [60, 100, 120, 70, 85]    # 물건별 가치

Knapsack01_BF(weight, value, 80)    # 290을 반환함 (인덱스 1, 2, 3인 물건을 넣음)

 

복잡도 분석

⇒ O(2^n)

항상 최적의 해를 구해주지만, 복잡도가 너무 높아 n이 조금만 커져도 사용하기 어려움

 

---

09-3 탐욕적 기법

탐욕적 기법(greedy method)도 매우 단순하고 직관적인 전략 사용

그러나, 모든 경우를 고려해 보고 가장 좋은 답을 찾는 것이 아닌 '그 순간에 최적'이라고 생각하는 답을 선택

"근시안적" 알고리즘

 

탐욕적 기법이 사용될 수 있는 경우

• 탐욕적 기법으로도 최적해를 구할 수 있는 경우
• 시간이나 공간적인 제약으로 최적해가 현실적으로 불가능한 경우

탐욕적 기법은 결정 순간에 간으한 해 중에 지역적으로 최적인 것을 선택, 이후의 단계에서 다시 변경될 수 없음

 

거스름돈 동전 최소화

거스름돈 동전 최소화 문제

액면가가 서로 다른 m 가지의 동전 {C1, C2, ... Cm} 이 있습니다. 거스름돈으로 V원을 동전으로만 돌려주어야 한다면 최소 몇 개의 동전이 필요한지를 구하세요. 단, 모든 동전은 무한히 사용할 수 있고, 액수가 큰 것부터 내림차순으로 정렬되어 있습니다.

 

남은 거스름돈에 대해 액면가가 가장 높은 동전부터 탐욕적으로 최대한 사용하면서 거스름돈을 맞추면 동전 개수를 최소로 만들 수 있음 → 탐욕적 전략의 예

 

최적해를 구할까?

60원짜리를 추가로 만들었다고 가정

거스름돈 620원을 만들기 위해 500원 1개, 60원 2개 ⇒ 3개의 동전으로 만들 수 있음

탐욕적으로 액면가가 높은 것부터 사용하는 경우, 500원 1개, 100원 1개, 10원 2개 ⇒ 4개의 동전, 최적해가 아님

 

동전 체계가 다음과 같은 조건을 가질 경우, 탐욕적 전략이 최적해를 보장할 수 있음

동전의 액면가 중에서 어떤 두개를 고르더라도 큰 액면가를 작은 액면가로 나누어 떨어지는 동전 체계

 

작은 액면가를 여러 개 모으면 반드시 큰 액면가를 만들기 때문

 

우리나라의 동전은 위의 조건을 만족하기 때문에 탐욕적 알고리즘이 항상 최적해를 보장

 

분할 가능한 배낭 채우기

문제에 대한 두 가지 '탐욕' 방법

• 탐욕 1: 무게와 상관없이 가장 비싼 물건부터 넣어보는 방법
• 탐욕 2: 단위 무게당 가격이 가장 높은 물건부터 넣어보는 방법

 

0-1 배낭 문제는 탐욕적 기법으로 최적해를 구하지 못함

최적해가 아닌 상황을 간단히 제시할 수 있음

세 개의 물건 A=(12kg, 120만원), B=(10kg, 80만원), C=(8kg, 60만원), 배낭의 용량이 18kg인 경우

최적해는 B와 C를 넣는 경우, 최대 가치는 140만원

• 탐욕 1: 가장 비싼 물건 A 선택 → B, C를 넣을 수 없어 배낭가치: 120만원, 최적해 140만원보다 작음
• 탐욕 2: 단위 무게당 가장 비싼 물건: A → 탐욕 1과 같이 최적해가 아님 

문제를 약간 변형하면 최적해를 구할 수 있음

 

분할 가능한 배낭 채우기 문제

물건들의 일부분만을 배낭에 넣을 수 있음 → 분할 가능한 배낭 채우기(Fractical Knapsack) 문제

 

분할 가능한 배낭 채우기 문제 (Fractical Knapsack problem)

각각 무게가 wgt i 이고 가치가 val i 인 n개의 물건들이 있고, 이것을 배낭에 넣으려고 합니다.
배낭에는 용량(최대 무게) W까지만 넣을 수 있습니다.
물건들의 가치의 합이 최대가 되도록 배낭을 채우고, 이때 매낭의 최대가치를 구해보세요.
단, 물건들은 나누어 일부분만을 넣을 수도 있습니다. 

미세한 가루로 된 세 가지 물건, A=(12kg, 120억 원), B=(10kg, 80억 원), C=(8kg, 60억 원), 배냥 용량: 18kg

단위 무게당 가격이 높은 물건부터 넣는 방법 사용

A : kg 당 10억 / B : kg 당 8억 / C : kg 당 7.5억

A로 12kg 채운 후, 다음으로 단위 무게당 가격이 높은 B로 6kg를 채움 → 최대가치: 168억

 

0-1 배낭 채우기와 달리 항상 배낭을 최대 용량으로 채울 수 있음

 

분할 가능한 배낭 채우기(탐욕적 기법)

def KnapSackFrac(wgt, val, W):
    bestVal = 0         # 최대가치
    for i in range(len(wgt)):   # 단가가 높은 물건부터 처리
        if W <= 0:      # 용량이 다 찼으면 채우기 종료
            break
        if W >= wgt[i]:
            W -= wgt[i]
            bestVal += val[i]
        else:
            fraction = W / wgt[i]
            bestVal += val[i] * fraction
            break

    return bestVal  # 최대 가치 반환

# 테스트 프로그램
weight = [12, 10, 8]    # (정렬됨)
value = [120, 80, 60]   # (정렬됨)
W = 18          # 배낭의 제한 용량
print("Fractional Knapsack(18):", KnapSackFrac(weight, value, W))

실행 결과

넣을 수 있는 모든 공간을 항상 무게당 가격이 가장 높은 것부터 채우기 때문에 항상 최적해를 보장

알고리즘의 복잡도는 O(n)