Python : 완전 탐색(= Brute-Force) Review

이전에 완전 탐색을 baby-gin을 통해 다룬 적이 있다. 대신 그때는 순열과 재귀를 제대로 배우지 않았기 때문에, 그리디 탐색을 이용해서만 해결했고, 이번에는 완전 탐색을 이용해서도 풀어볼 예정이다. 이외 다른 유형의 문제 2문제도 다뤄보려고 한다.

---

Brute-Force 알고리즘 ( = 완전탐색)

: 모든 가능한 경우를 시도해서 정답을 찾아내는 알고리즘

 

간단한 예시로는 좌물쇠 비밀번호가 있다. 0부터 9까지 3자리 숫자를 맞춰야 좌물쇠가 열리는데, 이때 반복문을 사용하여 모든 경우를 나열할 수 있고, 재귀를 이용한 중복순열을 통해서도 가능하다.

for i in range(10):
    for j in range(10):
        for k in range(10):
            print(i, j, k)

'''
0 0 0
0 0 1
0 0 2

...

9 9 8
9 9 9
'''

path = []
def permutation(n):
    if n == 3:
        print(path)
        return
    for i in range(10):
        path.append(i)
        permutation(n+1)
        path.pop()
permutation(0)
'''
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]

...

[9, 9, 8]
[9, 9, 9]
'''

로 순열 및 경우의 수를 나타낼 수 있다.

 

---

 

완전탐색을 이용한 문제 : 주사위의 눈금 합

 

 

문제 해석을 먼저 하자면 주사위 3개, 눈금 1~6까지, 중복이 가능한 경우임을 찾으면 된다. 중복이 가능하므로 used 배열은 필요 없을 것이고, level은 주사위 갯수인 3개, branch는 주사위 눈금 6개이다. 그럼 코드로 나타내보자.

path = []
def dice(n):
    if n == 3:
        print(path)
        return
    for i in range(1,7):
        path.append(i)
        dice(n+1)
        path.pop()

dice(0)

 

여기까지는 모두 작성 가능할 것이다. 이후 문제에서 원하는 3개의 눈금 합이 10인 것을 확인하면 되며, 주사위는 반드시 3개를 던지기 때문에 기저 조건에 path에 들어있는 주사위의 눈금 합이 10인 경우만 print 하면 해결할 수 있을 것이다.

여기서 n == 3 and sum(path) == 10: 을 하게되면, 첫 n == 3일때 조건문이 실행되지 않으면 n은 무수히 커질것이고 return 조건을 만족하지 못해 무한 호출에 빠짐에 유의하자.

path = []
def dice(n):
    if n == 3:
        if sum(path) == 10:
            print(path)
        return
    for i in range(1,7):
        path.append(i)
        dice(n+1)
        path.pop()

dice(0)

 

위의 방식처럼 조건문을 추가해서 하는 방식이 있고, 다른 방법은 매개변수와 인자로 넘겨주는 방법도 있다. 먼저 모든 경우의 눈금 합을 출력하려면 dice 매개변수에 sum을 정의한다. 즉 def dice(n,  sum) 이고, 첫 함수 호출은 dice(0, 0) 이후 재귀 호출을 할 때는 sum에 주사위 눈금을 더해줘야 하므로 dice(n+1, sum + i)를 작성하면 될 것이다.

path = []
def dice(n, sum):
    if n == 3:
        print(path, '=', sum)
        return
    for i in range(1,7):
        path.append(i)
        dice(n+1, sum + i)
        path.pop()

dice(0, 0)

 

이렇게되면 중복순열의 모든 경우의 수 눈금합을 구할 수 있다. 하지만 문제의 목적은 3개의 주사위 합이 10인 것을 고르는 것이므로 조건문을 추가한다면 아래와 같다.

path = []
def dice(n, sum):
    if n == 3:
        if sum == 10:
            print(path, '=', sum)
        return
    for i in range(1,7):
        path.append(i)
        dice(n+1, sum + i)
        path.pop()

dice(0, 0)

 

가장 중요한 부분은 재귀 호출을 할 때 sum + i 를 사용한다는 것만 기억하면 어려움 없이 문제를 풀이 할 수 있을 것이다. 하지만 우린 속도의 민족.. 과연 위의 식이 좋은 식일까? 를 고민하면 아닐 것이다.

그 이유는 세개의 주사위 합이 10이상인 경우는 많지 않지만, 위의 코드는 6,6,6 까지도 생성하고 조건문 if sum == 10: 임을 판단까지 하기 때문에(실제로는 모든 경우의 수를 확인하지만 출력만 숨기는 것) 시간 복잡도 면에서 아쉬운 감이 있을 것이다. 물론 너무 간단한 예시라 별 차이 없다고 생각 할 수 있지만, 주사위가 아닌 숫자의 범위가 1~100이라면? 시간 복잡도는 급속도로 올라갈 것이다. 

 

위의 문제를 예시로 주사위를 아직 2개밖에 안던졌는데, 10 이상이 나온다면 다음 주사위를 던질 필요가 있을까? 던질 필요가 없다는 것은 재귀호출 역시 할 필요 없다는 뜻이다. 그러면 매번 sum + i 가 갱신 될 때마다 확인해서 10이상이면 더이상 깊어질 필요가 없다는 것은 코드로 전달하면 될 것이다.

이 부분이 바로 '가지치기' = '백트래킹' 이다.

방금 말한 내용을 그대로 코드로 만들어보자.

 

일반적인 코드로 고치면 얼마나 차이나는지 모를 것이다. 그렇다면 count를 통해 앞서 작성한 전체를 확인하는 코드는 몇번 재귀하는지 확인해보자. 

path = []
cnt = 0
result = 0
def dice(n, sum):
    global cnt
    global result

    if n == 3:
        cnt += 1
        if sum == 10:
            result += 1
            print(path, '=', sum)
        return
    for i in range(1,7):
        path.append(i)
        dice(n+1, sum + i)
        path.pop()

dice(0, 0)
print(cnt,'회')      #  216 회
print(result, '개')  #  27 개

 

n == 3: 조건문이 216회 실행됨을 알 수 있고, 결과 갯수는 27개이다. 그렇다면 가지치기 조건문을 걸어준 코드는 얼마나 차이가 날까?

path = []
cnt = 0
result = 0
def dice(n, sum):
    global cnt
    global result

    if sum > 10:
        return
    if n == 3:
        cnt += 1
        if sum == 10:
            result += 1
            print(path, '=', sum)
        return
    for i in range(1,7):
        path.append(i)
        dice(n+1, sum + i)
        path.pop()

dice(0, 0)
print(cnt,'회')      # 108 회
print(result, '개')  # 27 개

 

n == 3: 조건문이 108회 호출 되는 것을 확인 할 수 있다. 결과는 당연히 같을 것이므로 27개임을 볼 수 있다. 드라마틱하게 줄지 않았다고 생각할 수 있지만, level이 최소 2번, 최대 3번을 비교한 것이기 때문에 눈으로 보기 어려운 예시이다. 그럼 조금 더 큰 수를 해보자.

아래의 코드는 트럼프 카드 1부터 13까지의 합 중에, 6개가 합이 40이 되는 경우를 가정한 코드이다. 위의 코드에서 숫자만 바꾼 것이다.

path = []
cnt = 0
result = 0
def card(n, sum):
    global cnt
    global result

    if n == 6:
        cnt += 1
        if sum == 40:
            result += 1
            print(path, '=', sum)
        return
    for i in range(1,14):
        path.append(i)
        card(n+1, sum + i)
        path.pop()

card(0, 0)
print(cnt,'회')      # 4826809 회
print(result, '개')  # 200382 개

 

path = []
cnt = 0
result = 0
def card(n, sum):
    global cnt
    global result

    if sum > 40:
        return
    if n == 6:
        cnt += 1
        if sum == 40:
            result += 1
            print(path, '=', sum)
        return
    for i in range(1,14):
        path.append(i)
        card(n+1, sum + i)
        path.pop()

card(0, 0)
print(cnt,'회')      # 2107365 회
print(result, '개')  # 200382 개

 

4,826,809회 에서 2,107,365회로 줄어든 것을 볼 수 있다. 만약 합이 10인 경우만 찾는 것이라면? 

path = []
cnt = 0
result = 0
def card(n, sum):
    global cnt
    global result

    if sum > 10:
        return
    if n == 6:
        cnt += 1
        if sum == 10:
            result += 1
            print(path, '=', sum)
        return
    for i in range(1,14):
        path.append(i)
        card(n+1, sum + i)
        path.pop()

card(0, 0)
print(cnt,'회')      # 210 회
print(result, '개')  # 126 개

 

드라마틱하게 줄어있는 것을 볼 수 있다.

---

완전탐색을 이용한 문제 : 연속된 문자 경우의 수

 

위의 내용을 토대로 바로 연습해보자 카드의 종류는 총 A, J, Q, K 로 4가지, 5번을 고르며 중복이 가능하다. 그리고 같은 문자가 연속 3개 있는 경우를 구하는 것이다. 그렇다면 중복순열을 통해 카드가 나열되는 모든 경우에서 AAA or JJJ or QQQ or KKK가 있는지 확인하면 될 것이다. 다만 이 문제는 정수를 사용하는 것이 아니고 문자열을 사용하니 적절한 표현 방식을 사용해줘야 한다.

 

코드로 확인해보자.

path = []
word_lst = ['A', 'J', 'Q', 'K']
cnt = 0
def card(n):
    global cnt
    if n == 5:
        result = ''
        for j in range(5):
            result += path[j]
        cnt += 1
        print(result)
        return
    for i in word_lst:
        path.append(i)
        card(n + 1)
        path.pop()

card(0)
print(cnt, '개')     # 1024 개

 

위의 식으로 나타내면 카드로 나타낼 수 있는 5번 고른 중복 순열 모두를 나타냈다. 4개데이터의 중복순열이므로 4* 4* 4* 4 * 4 로 총 1024개이며 이 중에서 연속된 문자가 들어가있는 경우를 확인하면 된다.

path = []
word_lst = ['A', 'J', 'Q', 'K']
cnt = 0
def card(n):
    global cnt
    if n == 5:
        result = ''
        for j in range(5):
            result += path[j]
        if result.find('AAA') != -1 or result.find('JJJ') != -1\
                or result.find('QQQ') != -1 or result.find('KKK') != -1:
            cnt += 1
            print(result)
        return
    for i in word_lst:
        path.append(i)
        card(n + 1)
        path.pop()

card(0)
print(cnt, '개')     # 160 개

 

문자에 만족하는 값을 찾기 위해 문자열의 find 함수를 사용했다. 총 160개임을 확인할 수 있었다. 가지치기를 억지로 하자면 가능 하겠지만, 도움이 될 정도는 아닌 것 같아 가지치기는 하지 않아도 될 것 같다.

---

완전탐색을 이용한 문제 : Baby-gin

 

앞서 말했듯 이전에 그리디 탐색으로 풀었던 문제다. 하지만 이를 완전 탐색으로 정확하게 한번 더 풀어보자. 

 

중복이 가능한 0부터 9까지의 숫자 카드 중 임의의 6장의 패를 가지고 있을 때, 숫자가 연속된 3개(run)거나, 같은 숫자 3개(triple)로만 구성 되었을 때 Baby-gin 이라고 할 수 있다.

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

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

 

임의의 6장의 패를 가지고 있을 때, 해당 하는 패로 만들 수 있는 모든 순열을 확인하고 그 안에 baby-gin이 있는지 확인하면 된다.

 

먼저 임의의 6장의 패로 만들 수 있는 순열을 만들어보자.

path = []
used = [False for _ in range(10)]
def baby_gin(n):
    if n == 6:
        print(path)
        return
    for i in range(6):
        if used[i] == False:
            used[i] = True
            path.append(lst[i])
            baby_gin(n+1)
            path.pop()
            used[i] = False

lst = list(map(int, input()))
baby_gin(0)

 

총 6장을 나열하므로 level은 6임을 알 수 있다. 하지만 0부터 9까지 있는데 왜 branch가 6일까? 이유는 이미 카드 6개를 임의로 받고 시작하기 때문에 직접 데이터에 접근하는 것이 아니라 lst의 데이터에 인덱스로서 접근할 것이기 때문이다. 이렇게 될 경우 출력되는 path가 중복되는 경우가 있긴 하지만, 그렇다고 range(10)을 하게되면 데이터 개수를 초과(out of range)하기 때문에 오류가 발생하게 된다.

 

모든 순열을 구했다면 이 순열중에 baby-gin 이 있는지 확인하면 된다.

baby-gin이 되기위한 조건은 아래와 같다.

run, triplet

run의 경우 나열된 수의 인덱스를 확인하여 0, 1, 2 번 인덱스가 순차적으로 1 증가하는지 혹은 3, 4, 5 번 인덱스가 순차적으로 1 증가하는지 확인하면 된다.

triplet의 경우 나열된 수의 인덱스 0, 1, 2 번 인덱스가 같은 수인지, 혹은 3, 4, 5 번 인덱스가 같은 수인지 확인하면 된다. 

cnt = 0
if path[0] + 1 == path[1] and path[0] + 2 == path[2]:
    cnt += 1
if path[3] + 1 == path[4] and path[3] + 2 == path[5]:
    cnt += 1
if path[0] == path[1] == path[2]:
    cnt += 1
if path[3] == path[4] == path[5]:
    cnt += 1
print(cnt)

 

baby-gin에 적합한 수인지 count 하는 cnt 변수를 초기화하고, run의 요소가 있는지, triplet의 요소가 있는지 확인한다. 이때 baby-gin 이라면 해당되는 출력값들 중 2가 단 하나라도 있다면 baby-gin임을 확인할 수 있을 것이다.

 

그렇다면 이 조건문의 위치는 어디일까?? 기저조건이 6일때 멈추기 때문에 그 때, baby-gin 임을 확인할 것이다. 즉, 기저조건에 넣어주면 된다.

path = []
used = [False for _ in range(10)]
def baby_gin(n):
    if n == 6:
        cnt = 0
        if path[0] + 1 == path[1] and path[0] + 2 == path[2]:
            cnt += 1
        if path[3] + 1 == path[4] and path[3] + 2 == path[5]:
            cnt += 1
        if path[0] == path[1] == path[2]:
            cnt += 1
        if path[3] == path[4] == path[5]:
            cnt += 1
        print(cnt)
        return
    for i in range(6):
        if used[i] == False:
            used[i] = True
            path.append(lst[i])
            baby_gin(n+1)
            path.pop()
            used[i] = False

lst = list(map(int, input()))
baby_gin(0)

 

여기서 끝이 아니다. 받은 lst가 baby-gin이 아니라면 'false', 맞다면 'true'를 반환하는 문제라면 baby-gin이 맞는지 확인하는 result 변수를 추가 할당해서 판단할 수 있다.

 

path = []
used = [False for _ in range(10)]
result = 'false'
def baby_gin(n):
    global result
    if n == 6:
        cnt = 0
        if path[0] + 1 == path[1] and path[0] + 2 == path[2]:
            cnt += 1
        if path[3] + 1 == path[4] and path[3] + 2 == path[5]:
            cnt += 1
        if path[0] == path[1] == path[2]:
            cnt += 1
        if path[3] == path[4] == path[5]:
            cnt += 1
        if cnt == 2:
            result = 'true'
        return
    for i in range(6):
        if used[i] == False:
            used[i] = True
            path.append(lst[i])
            baby_gin(n+1)
            path.pop()
            used[i] = False

lst = list(map(int, input()))
baby_gin(0)
print(result)
'''
input
123456
139673

output
true
false
'''

 

만약 baby_gin 함수를 돌며 baby-gin 임이 확인된다면 result가 'true'를 할당받아 결과를 확인할 수 있고, 만약 함수를 다 돌고도 확인되지 않았다면 그대로 'false'를 출력할 것이다.

---

완전 탐색에 관한 문제를 풀어보면서 review를 했는데, 이렇게하니 어느정도 가지치기와 완전 탐색에 대해 알게 된 것이다. 하지만 나중엔 시간 복잡도 싸움에서 좀 더 타이트한 조건을 사용하여 시간을 줄여야하니 긴장의 끈을 놓지 말자.