Python : 완전 탐색과 그리디 알고리즘 (Baby-gin)

배열을 배우면서 느꼈지만, 문제들이 노가다와 창의력을 요하는 문제들이 나오곤 한다. 일일이 다 확인해서 코드를 짤 수도 있고, 신박한 방법으로 짧게 코드를 구현할 수도 있을 것이다. 아직 직감이 와서 문제를 푸는 단계는 아니기 때문에 최대한 정석으로 풀곤하는데, 정석으로 풀면서도 시뮬레이션하며 경우의 수를 따질 때가 많았다. 그러면 어떻게 문제에 접근하는지 알아보자.

 

잠깐. 아래 내용을 설명하기 위해 예시에 대한 문제를 먼저 설명하고 가는 것이 좋을 것 같다.

 

Baby-gin Game

 

원래는 일반 트럼프 카드로 게임을 진행하는데, 쉬운 알고리즘 문제로 바꾸자면 중복이 가능한 0부터 9까지의 숫자 카드 중 임의의 6장의 패를 가지고 있을 때, 숫자가 연속된 3개(run)거나, 같은 숫자 3개(triple)로만 구성 되었을 때 Baby-gin 이라고 할 수 있다. 마치 루미큐브의 첫 등록을 보는 듯한 느낌, 예를들어 임의의 6개를 뽑았을 때,

1, 1, 1, 2, 3, 4 = triple + run = Baby-gin

1, 4, 2, 2, 3, 2 = only triple = not Baby-gin

이다.

그렇다면 위의 방식으로 baby-gin 여부를 판단하는 알고리즘을 어떻게 만들면 될까?

완전 탐색(Exausive Search)

: 문제의 답으로 생각 되는 모든 경우의 수를 확인하는 기법이다. 즉, 모든 경우의 수를 테스트 한 다음 최종 해법을 도출하는 방식이다.

• Brute-force 혹은 generate-and-test 기법이라고도 불린다.
• 일반적으로 경우의 수가 적을 때 사용한다.
• 모든 경우를 테스트 하기 때문에 수행 시간은 길지만, 틀릴 확률/답을 찾지 못할 확률은 낮은 편이다.
• 문제를 풀 때, 완전  탐색을 통해 해답을 도출한 뒤에, 성능 개선을 하는 것이 바람직하다.

Baby-gin 을 통한 예시

[1] 고려할 수 있는 모든 경우의 수 생성

임의의 숫자 6개를 받았을 경우 모든 숫자를 나열한다. (이때 중복도 포함)

예를들어 [1, 3, 5, 9, 9, 9]를 받았다면 모든 경우를 나열해본다. (순열)

같은 수인 9 9 9는 나열해도 중복임을 인지하자

*순열 (Permutation)

• 서로 다른 것들 중 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 선택하는 순열은 nPr로 표현할 수 있다. (중등 수학할 때 경우의 수 파트에서 지겹게 본거같다)
• nPr = n * (n - 1) * (n - 2) * ... * (n - r + 1)
• n과 r이 같다면[모든 수가 다를 경우]  nPn = n! (Factorial, 팩토리얼)로 표현하기도 한다.

lst = [1, 2, 3]

for i in range(1, 4):           # 잘못된 구현 예시

    for j in range(1, 4):

        for k in range(1, 4):

            print(i, j, k)      # 해당 출력은 리스트 요소들의 중복을 포함해버린다 ex)1 1 1

----------------------------------------------------------------------------------------------------------------

for i in range(1, 4):           # 제대로된 구현 예시

    for j in range(1, 4):

        if j != i:                    # 1번째, 2번째 데이터가 다르다는 조건을 걸어준다

            for k in range(1,4):

                if k != i and k != j: # 1, 2, 3 번째 데이터가 다르다는 조건을 걸어준다

                    print(i, j, k)

# 1 2 3

# 1 3 2

# 2 1 3

# 2 3 1

# 3 1 2

# 3 2 1

                   

 

[2] 모든 해답 테스트 하기

앞서 설명한 것처럼 baby-gin 은 연속된 숫자 run 혹은 같은 숫자 세개 triple인지 확인하고 이 중 두개가 해당한다면 baby-gin임을 확인 할 수 있다.

예시를 들었던 [1, 3, 5, 9, 9, 9] 에서는 triple은 존재하나 이외 run 혹은 triple은 존재하지 않기 때문에 baby-gin은 아님을 알 수 있다. 결과적으로 나올 수 있는 경우의 수를 모두 살펴보았으나, baby-gin은 되는 것이 없다는 결론에 도달 할 수 있다.

triple만 해당되는 모습

---

Greedy(탐욕) 알고리즘

: 최적해를 구하는데 지금 당장 좋아보이는 방법을 선택하는 탐욕적인 방법론이다. 그럼 좋은 것이 아닐까? 아쉽게도 아닐 경우가 많다. 알고리즘을 풀다보면 직감적으로 이러면 되지 않을까? 라며 접근을 한다면 그것이 바로 탐욕 알고리즘. 하지만 이후 주어진 문제를 단기적으로 쳐낸다고 생각하다가 전체 코드를 실행 시켰을 때 오류가 날 확률이 높다. baby-gin을 가장 먼저 접했을 때, 생각이 든 방법은 6개를 sort한 다음, 앞3개 뒤 3개를 나누어 판단하는 알고리즘을 만들었다. 이는 run과 triple이 섞일 수 있다는 것을 간과했다. 반례는 [1, 2, 2, 2, 2, 3] 가 있다. 이 경우 앞을 자르면 안된다.

 

Baby-gin 을 통한 예시

[1] 해 선택

현재 상태에서의 문제에 대한 최적 해를 구한뒤 이를 해 집합(Solution Set)에 추가한다.

6개의 데이터를 counts 배열로 만들어 먼저 run을 만족하는지 조사  후에 triple 혹은 run을 한번 더 검사한다

run을 먼저 조사하고 triple or run을 조사해보니 문제 없이 Baby-gin임을 알 수 있다.

 

[2] 실행 가능성 검사

새로운 부분해 집합이 실행 가능한지 확인하며 문제의 제약 조건을 위반하지 않는지 검사한다.

다른 경우에서 앞선 문제 없이 진행가능한지 확인한다.

[1]에서 세워둔 방식대로라면 앞서 run을 먼저 조사해버리면 Baby-gin 인 데이터에 반례가 생겨버린다

 

[3] 해 검사

새로운 부분해 집합이 문제의 해가 되는지 확인한다. 만약 전체의 해가 완성되지 않았다면(예외가 있다면) [1]으로 돌아가 다시 해 선택부터 다시 시작한다.

이번엔 반대로 triple을 먼저 조사 후에 run 또는 triple을 확인한다.

앞서 반례로 제시되었던 경우도 제대로 포함된 것을 확인 할 수 있다.

 

이제 코드로 작성해보자

num = 123123                # Baby Gin 확인할 6자리 수

cnt_lst = [0] * 12          # 6자리 수로부터 각 자리를 카운트 하기 위한 빈 배열 생성(12개를 생성하는 이유는 하단에)

for i in range(6):          # 해당 과정은 주어진 정수를 나누어 뿌려주기 위한 과정이며 오른쪽부터 뿌린다.

    cnt_lst[num % 10] += 1  # 인덱스에 맞춰 카운트를 높여준다

    num //= 10              # 10으로 나누어 자리수를 바꾸어준다

k = 0                       # 반복문 while을 돌리기 위한 변수 설정

tri = run = 0               # 초기 triple과 run 횟수를 0으로 설정

# triple을 확인하기 위한 반복문 작성

while k < 10:               # k가 10보다 작다면 계속 도는 반복문 조건 설정

    if cnt_lst[k] == 6:     # 6개일 경우 tri += 2  <-3의 배수로 나누어 몫을 tri += 할당해도된다

        cnt_lst[k] -= 6    

        tri += 2

    if cnt_lst[k] >= 3:     # 3개일 경우 tri +=1

        cnt_lst[k] -= 3

        tri += 1

    k += 1                  # 구성된 데이터를 모두 돌면 탈출하기 위한 조건 k에 +1

# run을 확인하기 위한 반복문 작성

k = 0 # k를 초기화 해줘야 위의 반복문과 겹치지 않는다.

while k < 10:

    if cnt_lst[k] == 2 and cnt_lst[k+1] == 2 and cnt_lst[k+2] == 2: # run의 조건을 확인 123123일 경우

        cnt_lst[k] -= 2

        cnt_lst[k+1] -= 2   # 아까 cnt_lst의 0 요소를 12개 추가해준 이유가 여기서 나오게된다

        cnt_lst[k+2] -= 2   # 추가해주지 않는다면 out of range

        run += 2            # 연속된 데이터가 2개씩 있을 경우 run += 2

    if cnt_lst[k] == 1 and cnt_lst[k+1] == 1 and cnt_lst[k+2] == 1: # run의 조건을 확인

        cnt_lst[k] -= 1

        cnt_lst[k+1] -= 1

        cnt_lst[k+2] -= 1

        run += 1            # 연속된 데이터가 있을 경우 run += 1

    k += 1

if run + tri == 2: # Baby-gin을 확인

    print("Baby Gin")

else:

    print("Lose")

 

정확한 설명을 보여주기 위해서 효율적이진 않지만 모든 반복을 하도록 만들었다. 주의해야할 점은 cnt_lst를 10개가 아닌 12개를 만들어주어야 한다는점, 물론 무조건 10개가 아니어도 되지만 범위지정 제대로 하지 않는다면 out of range를 보고있는 나를 마주할 수 있을 것이다.

---

이렇게 완전 탐색과 그리디 알고리즘에 대해 알아보았는데, 나는 그리디 탐색...형인 것 같다. 문제를 쭉 읽고 이렇게 하면 되지 않을까? 라며 자신있게 시작하지만 항상 되돌아 온다.. 다만 쉬운 문제를 오래 걸린 적도 있고 어려운 문제를 쉽게 푼적도 있긴하다. 

내 목표는 내가 원하는 형태의 알고리즘을 구현하는 것이다. 답을 틀리더라도 이후 내가 원하는 방향으로 잘 짜여진다면, 적어도 방향만 잡으면 도달할 수 있다는게 아닐까?

오늘도 화이팅하자.