[Python] Baby-gin-Game / 완전 검색, 탐욕 알고리즘

• 설명
  • 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.
  • 그리고, 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin으로 부른다.
  • 6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.
  • ex)
    667767 : 2개의 triplet -> baby-gin
    054060 : 1개의 run과 한개의 triplet -> baby-gin
    101123 : 1개의 triplet or 1개의 run-> not baby-gin
• 완전 검색 (Exaustive Search)
  • 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
  • Brute-force 혹은 generate-and-test 기법이라고도 불리 운다.
  • 모든 경우의 수를 테스트(수행 속도 느림) -> 최종 해법 도출
  • 일반적으로 경우의 수가 작을 때 유용
    

    # 완전 탐색으로 babygin을 검사하는 방법은 순열(Permutation)을 만들어보는 것이다.
    # 앞쪽과 뒤쪽의 숫자를 각각 세개씩 잘라서 해당 숫자가 run 또는 triplet 인지 검사
    # 순열 만들기 - 개수가 정해져 있는 경우 반복문으로 순열 생성 가능
    # 각 자리에 들어갈 수 있는 경우의 수 모두 고려해보기 : 완전탐색
    
    def check_baby(arr):
        #첫 번째 자리
        for i in range(6):
            # i 가 첫 번째 자리에 들어갈 요소의 인덱스
            for j in range(6):  # 두 번째 자리에 들어갈 요소 경우의 수 넣어보기
                #j 도 0번째 1번째, 2번째 모든 요소가 될 수 있지만
                #단, i와 같으면 안됨
                if i == j:
                    continue
                #겹치지 않는다면,
                for k in range(6):  # k: 세 번째 자리에 들어갈 요소의 인덱스
                    # k 역시 앞쪽에서 선택된 요소는 선택할 수 없음
                    if k == i or k == j :
                        continue
                    #여기서는 i,j,k 가 모두 다름
                    for a in range(6): # a: 네 번째 자리에 들어갈 요소의 인덱스
                        if a == i or a==j or a == k :
                            continue
                        for b in range(6):
                            if b == i or b == j or b == k or b == a: # b: 다섯 번째 자리에 들어갈 요소의 인덱스
                                continue
                            for c in range(6): # c: 여섯 번째 자리에 들어갈 요소의 인덱스
                                if c == i or c == j or c == k or c == a or c == b:
                                    continue
                                # 순열을 만들어 내는걸 확인했으니.....
                                # 순열 중에 baby-gin이 있는지 확인하기
    
                                # 앞 3개
                                # run 검사 각각 1차이
                                result = 0  #앞 부분과 뒷부분에서 run 또는 triplet이 몇개 나왔는지 저장하는 변수
                                if arr[i]+1 == arr[j] and arr[i]+2== arr[k]:
                                    result += 1
                                # triplet 검사는 다 똑같음
                                elif arr[i] == arr[j] and arr[i] == arr[k]:
                                    result += 1
    
                                # 뒤 3개
                                if arr[a] + 1 == arr[b] and arr[a] + 2 == arr[c]:
                                    result += 1
                                elif arr[a] == arr[b] and arr[a] == arr[c]:
                                    result += 1
    
                                if result == 2: # baby-gin
                                    #베이비진임을 확인하면.. 다른 경우의 수는 확인 할 필요가 없음!
                                    return True
        #반복문 다 수행할 동안 return이 안됐으면, baby-gin이 아님!
        return False
    
    arr = [2, 7, 3, 4, 5, 7]
    result = check_baby(arr)
    if result:
        print('baby-gin!')
    else:
        print('not baby-gin')
    # not baby-gin​

• 탐욕(Greedy) 알고리즘
  • 최적해를 구하는 데 사용되는 근시안적인 방법
  • 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종 해답에 도달
  • 각 선택의 시점에서 이루어진 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다
  • 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
  • 해 선택 -> 실행 가능성 검사 -> 해 검사
  • ex) 어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?
    

    # 탐욕 알고리즘: 각 상황에서 최선의 선택을 해 나가면서 해를 찾는 과정
    
    arr = [1, 1, 1, 4, 6, 5]
    N = 6
    # numbers : 각 숫자들의 개수를 포함하는 배열
    numbers = [0] * 10
    # 각 요소의 개수 세기
    for i in range(N):
        numbers[arr[i]] += 1
    
    # 앞쪽부터 run인지 triplet인지 검사, triplet부터 검사
    i = 0
    while i < 10:
        if numbers[i] >= 3: # 같은 숫자가 3개 이상 -> triplet!
            numbers[i] -= 3
        if numbers[i] > 0: # run인지 검사 - > 연속 3개의 숫자가 1개 이상씩 있는가
            if i < 7:
                if numbers[i] == numbers[i+1] and numbers[i] == numbers[i+2]:
                    numbers[i] -= 1
                    numbers[i+1] -= 1
                    numbers[i+2] -= 1
        i += 1
    
    if sum(numbers) == 0:
        print('baby-gin')
    else:
        print('not baby-gin')
    # baby-gin

    • ex) [1,2,3,1,2,3]
      만약, [1,1,2,2,3,3]으로 정렬된다면, 오히려 baby-gin 확인을 실패할 수 있다.
      위의 예처럼, 탐욕 알고리즘적인 접근은 해답을 찾아내지 못하는 경우도 있으니 유의!!!