Skip to content

Latest commit

 

History

History
379 lines (249 loc) · 14.4 KB

200507_탐욕(Greedy)알고리즘.md

File metadata and controls

379 lines (249 loc) · 14.4 KB
Raw

탐욕(Greedy) 알고리즘

  • 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
  • 일반적으로, 머리속에 떠올느느 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
  • 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
  • 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
  • 일단 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘은 단순하며, 또한 제한적인 문제들에 적용된다.
  • 최적화 문제(Optimization)란, 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제이다.
    • 가장 빠른 경로
    • 제일 큰 값..

1. 탐욕 알고리즘의 동작 과정

  • 해 선택
    • 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해집합(Solution Set)에 추가한다.
  • 실행 가능성 검사
    • 새로운 부분해 집합이 실행가능한지를 확인한다. 곧 문제의 제약 조건을 위반하지 않는 지를 검사한다.
  • 해 검사
    • 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1의 해 선택부터 다시 시작한다.

Ex) 2370원을 가장 거스름돈으로 최소로 줄 수 있는 방법을 구하여라.

거스름돈 1000 100 50 10
개수 2 3 1 2
  • 탐욕 기법을 적용한 거스름돈 줄이기
    • 해 선택
      • 여기에서는 멀리 내다볼 것 없이 가장 좋은 해를 선택한다. 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수가 줄어드므로 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가한다.
    • 실행 가능성 검사
      • 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인한다. 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고, 1 로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가한다.
    • 해 검사
      • 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야 하는 액수와 일치하는 셈이다. 더 드려도, 덜 드려도 안되기 때문에 거스름돈을 확인해서 액수에 모자라면 다시 1로 돌아가서 거스름돈에 추가할 동전을 고른다.
  • 최적해를 반드시 구한다는 보장이 없다.

물건 값 : 1200원 받은 돈 : 2000원 거스름돈 : 800원

Case1 Case2
500, 100, 50, 10 500, 400, 100, 50, 10
500원 : 1개
100원 : 3개
50원 : 0개
10원 : 0개
 500원 : 1개
400원 : 0개
100원 : 3개
50원 : 0개
10원 : 0개

2. 배낭 짐싸기 (Knapsack)

  • 도둑은 부자들의 값진 물건들을 훔치기 위해 보관 창고에 침입하였다.
  • 도둑은 훔친 물건을 배낭에 담아 올 계획이다. 배낭은 담을 수 있는 물건의 총 무게(W)가 정해져 있다.
  • 창고에는 여러 개(n개)의 물건들이 있고 각각의 물건에는 무게와 값이 정해져있다.
  • 경비원들에게 발각되기 전에 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건들을 담아야 한다.

배낭 ( 30kg )

물건 무게 값
물건1 25kg 10천만원
물건2 10kg 9천만원
물건3 10kg 5천만원
... ... ...
  • Knapsack 문제 유형
    • 0-1 Knapsack
      • 배낭에 물건을 통째로 담아야 하는 문제
      • 물건을 쪼갤 수 없는 경우
    • Fractional Knapsack
      • 물건을 부분적으로 담는 것이 허용되는 문제.
      • 물건을 쪼갤 수 있는 경우

2.1 0-1 Knapsack

  • 0-1 Knapsack에 대한 완전 검색 방법

    • 완전 검색으로 물건들의 집합S 에 대한7 모든 부분집합을 구한다.

    • 부분집합의 총무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택할 수 있다.

    • 물건의 개수가 증가하면 시간 복ㅈ바도가 지수적으로 증가한다.

      • 크기 n인 부분집합의 수 2^n

  • 0-1 Knapsack에 대한 탐욕적 방법1

    • 무게 값
      물건1 25kg 15만원
      물건2 10kg 9만원
      물건3 10kg 5만원

    • 값이 비싼 물건부터 채운다.

    • W = 30kg

    • 탐욕적 방법의 결과

      • (물건1), 25kg, 10만원

    • 최적해

      • (물건2, 물건3), 20kg, 14만원

    • 최적이 아니다.

  • 0-1 Knapsack에 대한 탐욕적 방법2

    • 무게 값
      물건1 25kg 15만원
      물건2 10kg 9만원
      물건3 10kg 5만원

    • 무게가 가벼운 물건부터 채운다.

    • W = 30kg

    • 탐욕적 방법의 결과

      • (물건2 + 물건3), 14만원

    • 최적해

      • (물건1), 15만원

    • 역시 최적해를 구할 수 없다.

  • 0-1 Knapsack에 대한 탐욕적 방법3

    • 무게 값 값/kg
      물건1 5kg 50만원 10만원/kg
      물건2 10kg 60만원 6만원/kg
      물건3 20kg 140만원 7만원/kg

    • 무게 당 (예>kg당) 값이 높은 순서로 물건을 채운다.

    • W = 30kg

    • 탐욕적 방법

      • (물건1, 물건3), 190만원

    • 최적해

      • (물건2, 물건3), 200만원

    • 역시, 탐욕적 방법으로 최적해를 구하기 어렵다.

이 문제는 Greedy 방법으로는 풀리지않으니, 완전검색 (Brute-Force) 로 풀어보고 개선하도록 해야한다.

2.2 Fractional Knapsack 문제

무게 값 값/kg
물건1 5kg 50만원 10만원/kg
물건2 10kg 60만원 6만원/kg
물건3 20kg 140만원 7만원/kg
  • 물건의 일부를 잘라서 담을 수 있다.
  • 탐욕적인 방법
    • (물건1 + 물건3 + 물건2의 절반), 30kg, 220만원

3. 회의실 배정하기

  • 김대리는 소프트웨어 개발팀들의 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다.
  • 회의는 시작 시간과 종료 시간이 있으며, 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다.
  • 가능한 많은 회의가 열리기 위해서는 회의들을 어떻게 배정해야 할까?
  • 입력 예)
    • 회의 개수
    • (시작시간, 종료시간)
10
(1, 4), (1, 6), (6, 10), (5, 7), (3, 8), (5, 9), (3, 5), (8, 11), (2, 13), (12, 14)
  • 활동 선택 문제
    • 시작시간과 종료시간이 있는 n개의 활동들의 집합 A 1 <= i <= n 에서 서로 겹치지 않는 최대갯수의 활동들의 집합 S를 구하는 문제
    • 양립 가능한 활동들의 크기가 최대가 되는 S 의 부분집합을 선택하는 문제
i 0 1 2 3 4 5 6 7 8 9 10 11
시작 1 3 1 5 3 5 6 8 2 12 무한
종료 0 4 5 6 7 8 9 10 11 13 14
  • 탐욕 기법의 적용
    • 공집합이 아닌 하위문제(sub-problem) Si,j 가 있고 Si,j 에 속한 활동 am 은 종료시간이 가장 빠른 활동이다.
    • 그렇다면
      • 하위문제에서 종료시간이 가장 빠른 활동을 선택한다.
# 탐욕 기법을 적용한 반복 알고리즘
# A : 활동들의 집합
# S : 선택된 활동(회의) 들의 집합
# Si : 시작시간
# fi : 종료시간,
# 1 <= i <= n

Sort A by finish time
S = {A1} # 제일 빨리 끝나는 회의 가져오기
j = 1
for i in range(2, n):
    if si >= fj:
        S = S | {Ai}
        j = i
        
# 종료 시간이 빠른 순서로 활동들을 정렬한다.
# 첫 번째 활동(A1) 을 선택한다.
# 선택한 활동(A1)의 종료시간보다 빠른 시작 시간을 가지는 활동을 모두 제외한다.
# 남은 활동들에 대해 앞의 과정을 반복한다.

image-20200507102606972

# 재귀 알고리즘
# A : 정렬된 활동 들의 집합
# S : 선택된
# 

def Recursive_Selection(i, j):
    m = i + 1
    while m < j and sm < fi: # 종료 시간이 가장 빠른 활동 선택
        m = m+1
    
    if m < j:
        return {am} | Recursive_Selection(m, j)
    else:
        return {} # 곶입합

4. 파이썬 3일차 - 5202_화물 도크

  • 문제의 이해
    • 0시부터 다음날 0시 이전까지 A도크의 사용신청을 확인해 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록하면, 최대 몇 대의 화물차가 이용할 수 있는지 알아내 출력하는 프로그램을 만드시오.
    • 신청서에는 작업 시작시간과 완료시간이 매시 정각을 기준으로 표시되어 있고, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다.
    • 예를 들어 앞 작업의 종료 시간이 5시면 다음 작업의 시작 시간은 5시부터 가능하다.
T=int(input())
for tc in range(1, T+1):
    N = int(input())
    lst = [[0]*2 for _ in range(N)]
    for i in range(N):
        lst[i] = list(map(int, input().split()))

    lst.sort(key=lambda x: x[1]) # 종료시간을 기준으로 Sorting
    end = lst[0][0]
    cnt = 1
    for i in range(1, N):
        if end <= lst[i][0]:
            end = lst[i][1]
            cnt += 1

    print('#{} {}'.format(tc, cnt))

5. 탐욕 알고리즘의 필수 요소

  • 탐욕적 선택 속성 (greedy choice property)

    • 탐욕적 선택은 최적해로 갈수 있음을 보여라
      • 즉 탐욕적 선택은 항상 안전하다.

  • 최적 부분 구조(optimal substructure property)

    • 최적화 문제를 정형화하라
      • 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.

  • [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명하라.

6. 탐욕 기법(Greedy)과 동적 계획법(DP)의 비교

탐욕기법 동적 계획법
매 단계에서 가장 좋게 보이는것을 빠르게 선택한다.
지역최적 선택(local optimal choice)		 매 단계의 선택은 해결한 하위 문제의 해를 기반으로 한다.
하위 문제를 풀기 전에 (탐욕) 선택이 먼저 이루어진다. 하위 문제가 우선 해결된다.
Top-Down 방식 Bottom-up 방식
일반적으로, 빠르고 간결하다. 좀 더 느리고, 복잡하다.

대표적인 탐욕 기법의 알고리즘들

알고리즘 목적 설명
Prim N개의 노드에 대한 최소신장트리(MST)를 찾는다. 서브 트리를 확장하면서 MST를 찾는다. 그래프
Kruskal N개의 노드에 대한 최소신장트리(MST)를 찾는다. 싸이클이 없는 서브 그래프를 확장하면서 MST를 찾는다. 그래프
Dijkstra 주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다. 주어진 정ㅈ머에서 가장 가까운 정점을 찾고, 그 다음을 정점을 반복해서 찾는다. 그래프
Huffman
tree & code		 문서의 압축을 위해 문자들의 빈도수에 따라 코드값을 부여한다. 출현 빈도가 낮은 문자부터 선택해서 이진 트리를 완성하고 코드값을 부여한다. 문자열

7. 탐욕 기법을 통한 baby-gin 문제 해결

  • 탐욕 기법을 통한 baby-gin 문제 해결
  • 완전검색 아닌 방법으로 풀어보자.
    • 6개의 숫자는 6자리의 정수 값으로 입력된다.
    • counts 배열의 각 원소를 체크하여 run 과 triplet 및 baby-gin 여부를 판단한다.

image-20200507105534302

# [SWEA] 5203_베이비진 게임

T = int(input())
for tc in range(1, T+1):
    cards = list(map(int, input().split()))

    player1 = [0] * 10
    player2 = [0] * 10
    flag = False
    for idx, val in enumerate(cards):
        if idx % 2:
            player2[val] += 1
            for i in range(10):
                if i+2 < 10:
                    if player2[i] == 3 or ( player2[i] >= 1 and player2[i+1] >= 1 and player2[i+2] >= 1 ):
                        print('#{} 2'.format(tc))
                        flag = True
                        break
        else:
            player1[val] += 1
            for i in range(10):
                if i+2 < 10:
                    if player1[i] == 3 or ( player1[i] >= 1 and player1[i+1] >= 1 and player1[i+2] >= 1 ):
                        print('#{} 1'.format(tc))
                        flag = True
                        break
        if flag:
            break
    else:
        print('#{} 0'.format(tc))