[SWEA]파이썬 SW문제해결 기본 - LIST 1 : Greedy Algorithm

---

파이썬 SW문제해결 기본 - LIST 1

04 Greedy Algorithm

---

이미지를 클릭하시면 SW Expert Academy의 해당 강좌로 이동합니다

04. Greedy Algorithm(탐욕적 알고리즘)

    ① 탐욕 알고리즘이란?

        ▣ 탐욕 알고리즘(Greedy Algorithm)

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

            - 각 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

            - 지역적으로는 최적이지만, 그것의 최종 해답이 최적이라는 보장은 없음

        ▣ 탐욕 알고리즘 수행 과정

            1) 해 선택 : 현재 상태에서 부분 문제의 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가한다.

            2) 실행 가능성 검사 : 새로운 부분 해 집합이 실행 가능한지 확인한다.(문제 제약 조건 위반 검사)

            3) 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 시작한다.

 

    ② 탐욕 알고리즘의 예

        ▣ 거스름돈 줄이기

            - 어떻게 하면 손님에게 거스름돈으로 주는 '지폐'와 '동전'의 개수를 최소화할까?

            1) 해 선택 : 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가한다.

            2) 실행 가능성 검사 : 거스름돈의 초과 여부를 확인한다. 
                    초과하지 않는다면? => 계속 진행한다.
                    초과한다면?  => 마지막에 추가한 동전을 거스름돈에서 빼고, 해 선택으로 돌아가 작은 단위의 동전을 추가한다.

            3) 해 검사 : 지폐와 동전의 총액과 거스름돈이 일치하는지 확인한다. 액수에 모자라면 1번부터 다시 반복한다.

EX) 12000원 거슬러 주기
#X-Y는 X번째 반복 Y단계를 의미한다.
    1-1) 해 선택 : 5만원권을 골라 거스름돈에 추가한다. (현재 거스름돈 : 50000원)
    1-2) 실행 가능성 검사 : 12000원 < 50000원. 5만원을 다시 빼고 1번으로 돌아간다. (현재 거스름돈 : 0원)

    2-1) 해 선택 : 1만원권을 골라 거스름돈에 추가한다. (현재 거스름돈 : 10000원)
    2-2) 실행 가능성 검사 : 12000원 ≥ 10000원. 3번으로 진행한다. (현재 거스름돈 : 10000원)
    2-3) 해 검사 : 12000원 ≠ 10000원이므로 다시 1번부터 반복한다. (현재 거스름돈 : 10000원)

    3-1) 해 선택 : 1만원권을 골라 거스름돈에 추가한다. (현재 거스름돈 : 20000원)
    3-2) 실행 가능성 검사 : 12000원 < 20000원. 만원을 다시 빼고 1번으로 돌아간다. (현재 거스름돈 : 10000원)

    4-1) 해 선택 :  5천원권을 골라 거스름돈에 추가한다. (현재 거스름돈 : 15000원)
    4-2) 실행 가능성 검사 : 12000원 < 15000원. 5천 원을 다시 빼고 1번으로 돌아간다. (현재 거스름돈 : 10000원)

    5-1) 해 선택 : 1천원권을 골라 거스름돈에 추가한다. (현재 거스름돈 : 11000원)
    5-2) 실행 가능성 검사 : 12000원 ≥ 11000원. 3번으로 진행한다. (현재 거스름돈 : 11000원)
    5-3) 해 검사 : 12000원 ≠ 11000원이므로 다시 1번부터 반복한다. (현재 거스름돈 : 11000원)

    6-1) 해 선택 : 1천원권을 골라 거스름돈에 추가한다. (현재 거스름돈 : 12000원)
    6-2) 실행 가능성 검사 : 12000원 ≥ 12000원. 3번으로 진행한다. (현재 거스름돈 : 12000원)
    6-3) 해 검사 : 12000원 = 12000원이므로 반복을 중단한다. (현재 거스름돈 : 12000원)

 

    ② Baby-gin 다시 풀기

        ▣ 완전 검색이 아닌 Baby-gin 방법으로 풀기

            - 6개의 숫자는 6자리 정수 값으로 입력된다.

            - "COUNTS" 리스트의 각 원소를 체크하여 run과 triplete을 체크하고 최종적으로 Baby-gin 여부를 판단한다.

            - 조금 더 구체적으로... 

                        1) COUNTS라는 이름의 리스트 선언한다. (크기 : 10)

                        2) 6자리 각 숫자의 개수를 세어 COUNTS 리스트에 추가한다. "123333"을 받았다면 COUNTS[3]=4

                        3) COUNTS 리스트에서 run과 triplete 중 가능한 것을 조사한다.

                        4) run 또는 triplete으로 판단된 데이터는 COUNTS에서 제외한다. 

                        5) 남은 데이터에서 run 또는 triplete이 가능한지 조사한다.

                        6) 최종적으로 Baby-gin 여부를 판단한다.

 

        ▣ 탐욕 알고리즘 접근을 통해 해답을 찾아내지 못하는 경우

           - 위와 같은 방법이 아닌 다음과 같은 방법으로 탐욕 알고리즘 접근을 한다고 가정해보자.

           - "입력받은 숫자를 정렬한 후 앞뒤 3자리씩 끊어서 run 및 triplete을 확인"

           EX1) [6, 4, 4, 5, 4, 4]
           입력 숫자를 정렬한  [4, 4, 4, 4, 5, 6]을 앞뒤 3자리씩 나눠 확인하면 쉽게 Baby-gin을 확인할 수 있다.

그러나...
           EX2) [1, 2, 3, 1, 2, 3]
           정렬하면 [1, 1, 2, 2, 3, 3]으로 오히려 baby-gin 확인에 실패한다.

           - 위 예시와 같이 Greedy Algorithm은 해답을 찾아내지 못하는 경우도 있다. 

 

탐욕적 알고리즘은 개인적으로 많이 쓰는 방식이다. 문제를 처음 접할 때 앞서 배운 완전 탐색(Exhaustive Search)보다 수행 속도가 빠르면서도 개발하기 간단하기 때문이다. 나는 보통 탐욕적 방식으로 문제에 대한 감을 잡은 뒤에 다시 최적화를 목표로 코드를 수정하며 코딩을 한다.