[Algorithm 이론] Greedy Algorithm 정리 | (ft. 솔루션 탐색에 실패할 수 있음)


 








Greedy Algorithm(탐욕 알고리즘)에 대해 이해하고, 왜 솔루션 탐색에 실패할 수 있는지 알아보자. 


Greedy Algorithm

Greedy Algorithm (탐욕 알고리즘)

“최적 해를 구하는데 사용되는 근시안적인 방법”

  • 여러 경우 중 하나를 결정해야 할 때마다 매 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달함
  • 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만 (Local optimum), 그것들을 계속 같은 방식으로 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적(global optimum)이라는 보장은 없음
  • (일반적으로) 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됨

Greedy Algorithm의 수행 과정

[step1] 해 선택 (solution selection)

  • 현재 상태에서 부분 문제의 최적 해(Local Optimum)를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가

[step2] 실행 가능성 검사

  • 새로운 부분 해 집합이 실행 가능한지를 확인
  • 즉, 문제의 제약 조건을 위반하지 않는지를 검사함

[step3] 해 검사

  • 새로운 부분 해 집합이 문제의 해가 되는지를 확인
  • 아직 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 시작함

EXAMPLE01: 거스름돈 줄이기

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 충분히 있다고 가정하자. 손님에게 거슬러 줘야하는 돈이 NN 일때, 어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

풀이순서:

[step1] 해 선택

  • 가장 좋은 해를 선택
  • 가장 단위가 큰 동전(Local Optimum)을 하나 골라 거스름돈에 추가함(Solution Set)

[step2] 실행 가능성 검사

  • 거스름돈이 손님에게 내드려야 할 액수를 초과하는지를 확인
  • 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 해 선택으로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가함

[step3] 해 검사

  • 거스름돈이 손님에게 내드려야 하는 액수와 일치하는지 확인
  • 액수가 모자라면 다시 해 선택으로 돌아가서 거스름돈에 추가할 동전을 고름

(ex) 1,370 원을 거슬러 준다면?

N=x×500+y×100+z×50+k×10N=x\times500+y\times100+z\times50+k\times10 일 때,

x+y+z+kx+y+z+k 가 최소가 되길 원함

# [step1] N = 1370   # 거슬러 줄 돈
1370 >= x*500 이므로 x는 최대 2 
남은 돈 = 370

# [step2] 현재 동전 액수가 크다면, 한 단계 작은 단위의 동전을 추가한다 
370 >= y*100 이므로 y는 최대 3 
남은 돈 = 70 

# [step2] 현재 동전 액수가 크다면, 한 단계 작은 단위의 동전을 추가한다 
70 >= z*50 이므로 z는 최대 1
남은 돈 = 20

# [step2] 현재 동전 액수가 크다면, 한 단계 작은 단위의 동전을 추가한다 
20 >= k*10 이므로 k는 최대 2 
남는 돈 = 0 

# [step3] 해 검사 
남은 돈 = 0 이므로 솔루션은 x+y+z+k = 2+3+1+2 = 8

Pseudo Code

N = 1370   # 거슬러 줄 돈
coins = [500, 100, 50, 10]  # 잔돈 종류 
coins.sort(reverse=True)  # 가장 단위가 큰 동전 순서로 정렬 

COUNTS = [0] * 4 

for i, coin in enumerate(coins): 
    COUNTS[i] = N//coin  # 가장 단위가 큰 동전을 골라 줄 수 있는 만큼 반환한다
    N %= coin   # 남은 돈 

print(f"COUNTS = {COUNTS}")
print(f"total = {sum(COUNTS)}")


# output 
COUNTS = [2, 3, 1, 2]
total = 8

위 코드의 명령문 개수 = 4+잔돈개수∗2+2=6+n∗2=2n+64+잔돈개수*2+2 = 6+n*2=2n+6

Big-O 표기법을 통한 Time Complexity 는:

O(2n+6)=O(2n)=O(n)O(2n+6)=O(2n)=O(n)

즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받는다.


EXAMPLE02: baby-gin 게임 다시 풀기

앞서 Exhaustive Search 방식으로 풀었던 baby-gin 게임을 Greedy Algorithm으로 풀어보자.

풀이순서:

  1. 6개의 숫자는 6자리의 정수(int) 값으로 입력됨
  2. 정수를 이루는 숫자에 대한 COUNTS 리스트(list)를 생성하고, 리스트의 각 원소를 체크하여 run과 triplete 및 Baby-gin 여부를 판단함
  3. 이후 Greedy Algorithm을 적용함
    • COUNTS 리스트(list)에서 run과 triplete 중에 가능한 것을 조사함
    • 조사에 사용한 데이터는 삭제함
    • 남은 데이터를 다시 run과 triplete 중에 가능한지를 조사함
    • 최종적으로 Baby-gin 여부를 판단

(ex1) 입력으로 444345 을 받았을 경우 
# COUNTS 리스트 생성 
       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
COUNTS |   |   |   | 1 | 4 | 1 |   |   |   |   |   

# run과 triplete 중에 가능한 것을 조사 후  (step1. 해 선택) 
""" 345가 연속되므로 run 이다 """ 

# 조사에 사용한 데이터는 삭제 & 남은 데이터 (step2. 실행 가능성 검사) 
""" 345 삭제 """ 
       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
COUNTS |   |   |   |   | 3 |   |   |   |   |   |   

# run과 triplete 중에 가능한 것을 조사 후 
""" 444가 연속되므로 triplete 이다 """ 

# 최종적으로 Baby-gin 여부 판단 (step3. 해 검사)
""" run, triplete 으로 입력 값은 Baby-gin!"

(ex2) 입력으로 444456 을 받았을 경우 
# COUNTS 리스트 생성 
       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
COUNTS |   |   |   |   | 4 | 1 | 1 |   |   |   |  

# run과 triplete 중에 가능한 것을 조사 후
""" 444가 연속되므로 triplete 이다 """ 

# 조사에 사용한 데이터는 삭제 & 남은 데이터
""" 444 삭제 """ 
       | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
COUNTS |   |   |   |   | 1 | 1 | 1 |   |   |   |   

# run과 triplete 중에 가능한 것을 조사 후
""" 456가 연속되므로 run 이다 """ 

# 최종적으로 Baby-gin 여부 판단 
""" triplete, run 으로 입력 값은 Baby-gin!"

Pseudo Code

input = 644544

# === COUNTS 리스트 생성 === # 
COUNTS = [0] * 10  # 6자리 수로부터 각 자리 수를 추출하여 개수를 누적할 리스트(list)

for i in range(6):
    COUNTS[input % 10] += 1  # 일의 자리 숫자를 추출하여(input%10) 개수 카운트 
    input //= 10  # (몫을 반환) 일의 자리 수를 뺀 나머지 

print(f"COUNTS: {COUNTS}")

# === Run / Triplete 조사 === # 
tri = run = 0  # init. 

for i in range(len(COUNTS)):  
    if COUNTS[i] >= 3:  # triplete 여부 조사 
        COUNTS[i] -= 3  # 조사에 사용한 데이터 삭제 
        print(r"Triplete!")
        print(f"COUNTS: {COUNTS}")

        tri += 1 
        
    if COUNTS[i] >= 1 and COUNTS[i+1] >= 1 and COUNTS[i+2] >= 1: # run 여부 조사
        COUNTS[i]-= 1  # 조사에 사용한 데이터 삭제 
        COUNTS[i+1]-= 1
        COUNTS[i+2]-= 1
        print(r"Run!")
        print(f"COUNTS: {COUNTS}")

        run += 1
        
        
# === 최종적으로 Baby-gin 여부 판단 === #
if tri+run == 2: 
    print(r"Baby-gin!")
else: 
    print(r"Lose")


# output 
COUNTS: [0, 0, 0, 0, 4, 1, 1, 0, 0, 0]
Triplete!
COUNTS: [0, 0, 0, 0, 1, 1, 1, 0, 0, 0]
Run!
COUNTS: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Baby-gin!

해답을 찾아내지 못할 때

“Greedy Algorithm 접근의 경우, 해답을 찾아내지 못할 수도 있다”

  • 딥러닝에서 Gradient Descent(GD) 알고리즘이 대표적인 탐욕 알고리즘이다
  • 매순간 local minimum을 향하도록 파라미터를 업데이트 하는데
  • 그것이 전체적인 global minimum 이라는 보장은 없다

위의 Baby-gin 문제에서 input=123123 일 때 정답을 찾지 못한다. 분명 123/123 으로 run 이 두번 나와서 baby-gin 임에도 불구하고 찾지 못한다. 왜일까?

input = 123123

# === COUNTS 리스트 생성 === # 
COUNTS = [0] * 10  # 6자리 수로부터 각 자리 수를 추출하여 개수를 누적할 리스트(list)

for i in range(6):
    COUNTS[input % 10] += 1  # 일의 자리 숫자를 추출하여(input%10) 개수 카운트 
    input //= 10  # (몫을 반환) 일의 자리 수를 뺀 나머지 

print(f"COUNTS: {COUNTS}")

# === Run / Triplete 조사 === # 
tri = run = 0  # init. 

for i in range(len(COUNTS)):  
    if COUNTS[i] >= 3:  # triplete 여부 조사 
        print(r"Triplete!")
        
        COUNTS[i] -= 3  # 조사에 사용한 데이터 삭제 
        print(f"COUNTS: {COUNTS}")

        tri += 1 
        
    if COUNTS[i] >= 1 and COUNTS[i+1] >= 1 and COUNTS[i+2] >= 1: # run 여부 조사
        print(r"Run!")

        COUNTS[i]-= 1  # 조사에 사용한 데이터 삭제 
        COUNTS[i+1]-= 1
        COUNTS[i+2]-= 1
        print(f"COUNTS: {COUNTS}")

        run += 1
        
        
# === 최종적으로 Baby-gin 여부 판단 === #
if tri+run == 2: 
    print(r"Baby-gin!")
else: 
    print(r"Lose")


# output 
COUNTS: [0, 2, 2, 2, 0, 0, 0, 0, 0, 0]
Run!
COUNTS: [0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
Lose
  • 살펴보면 i=1i=1 에 부터 RunRun 을 판단하고 루프(loop)가 i=2i=2 로 넘어가면서 다음 최적해를 찾는데 실패했다.
  • 이렇듯 COUNTS 리스트에 Greedy Algorithm 을 적용하면 솔루션 탐색에 실패할 수 있다.
  • 이를 개선하려면 어떻게 해야할 까? (다른 알고리즘 써야지ㅎㅎ)

Summary

  • Greedy Algorithm의 정의 - 매 순간순간 local optimum 을 찾는 방법
  • (example) 거스름돈 줄이기 문제 / Baby-gin 문제
  • (특징) 솔수션 탐색에 실패할 수 있음 (i.e., 매순간 local optimum 을 찾았다고 global optimum 이 되는 것은 아니다)

Reference

[1] https://swexpertacademy.com/main/main.do

위치: 대한민국 서울특별시

댓글

댓글 쓰기

이 블로그의 인기 게시물

[DL for CV] Down-Sampling (Encoding)

이미지
  Down-sampling (Encoding)  [DL for CV] Down-Sampling (Encoding) ( source ) Downsampling 은 신호처리(signal processing)에서 사용되는 용어로 sample의 개수를 줄이는 처리 과정을 말한다 . 딥러닝에서는 인코딩(Encoding)과정에서 feature의 개수를 줄이는 처리과정 이라 볼 수 있다. feature 개수를 줄이면 이를 다룰 파라미터도 줄어들기 때문에 차원이 축소되는 효과 를 얻을 수 있다. 이는 곳 overfitting을 방지 하는 효과로 이어진다. 딥러닝 모델 아키텍처에서 사용되는 몇 가지 대표적인 Downsampling 방식을 정리한다. Pooling - 대표값 구하기 커널 영역(kernel scope)에 포함된 data 중에서 대표 값 하나를 샘플링하는 처리 방식 이다. 대표 값을 얻는 방식은 따르는 규칙에 따라 다르다; Max Pooling, Average Pooling, Global Average Pooling, and etc. 보통 Average pooling 보다는 Max pooling을 더 많이 사용한다. Average pooling의 경우 산술평균의 특성 을 가지기 때문에 필연적으로 발생하는 문제 가 있다 . 즉, 신호의 분산이 클 경우 대표 값과 실제 두드러지는 값과의 차이가 커진다 . 반면, Max pooling 연산이 좀더 간단하고 두드러지는 신호를 잘 전달할 수 있기 때문에 더 자주 사용된다. 때문에 논문과 교재에서 별도의 언급이 없이 Pooling layer를 언급한다면 Max pooling 이라 생각하면 된다. (장점) Pooling은 학습 가능한 파라미터 (learnable parameters)가 없기 때문에 kernel size를 키워도 차원의 저주를 피할 수 있는 방법중 하나다. t...
Read more »