#2 Python / 조합 알고리즘(브루트포스)

🧐 브루트 포스(완전탐색)이란?

간단한 알고리즘 방식 중 하나로 가능한 모든 경우의 수를 모두 탐색해서 정답을 찾아내는 방식을 말합니다.
(브루트 포스는 무식한 힘이라는 뜻으로 완전탐색을 비유하는 단어인 것 같네요.)

🧐 조합 알고리즘

완전탐색의 방법을 사용해서 프로그래밍을 하다 보면 가능한 모든 경우의 수를 구해야 하기에 '조합이나 순열을 이용해서 구현을 해야겠다!'라는 생각이 종종 드는 것 같습니다.
단순히 가능한 조합의 경우의 수를 계산하는 코드를 짜는 건 쉽지만, 가능한 경우의 수를 모두 출력하는 코드를 짜는 건 생각외로 쉽지 않은 것 같아요.

👉 itertools 모듈 이용하기

itertools라는 python 모듈을 사용하면 조합이나 순열을 출력해주는 함수를 이용할 수 있습니다.

import itertools

a=[1,2,3,4]

print(list(itertools.combinations(a,2)))

이렇게 하면 다음과 같은 결과를 얻게 됩니다.

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

⁙ combinations함수가 바로 tuple형태를 반환하는 것이 아니고 해당 자료형의 객체를 반환한 다는 것을 알고 있으면 좋을 것 같습니다.

👉 재귀를 이용하여 구현하기

개인적인 생각으로 재귀를 이용할 때는 재귀적인 알고리즘을 잘 생각해내는 게 중요한 것 같습니다.
다른말로 반복적인 패턴을 생각해내는 게 중요한 것 같습니다.

def combination(arr,r):

    wanted=[]
    
    if r==1:
        for i in arr:
            wanted.append([i])

    else:
        for i in range(len(arr)-r+1):
            for j in combination(arr[i+1:], r-1):
                wanted.append([arr[i]]+j)

    return wanted

여기서 사용된 반복적인 패턴은 nCr = n-1Cr-1 + n-1Cr 입니다. 이렇게 해서 결국에 r의 수를 줄여나가다 보면 r=1이 되게 되고 거기서부터 값을 넣게 되는 것입니다.
n도 줄어서 결국 n<r이 되는 상황이 발생한다고 생각할 수도 있는데, 이건 else 단락에서 i가 list의 맨 뒤에서부터 r번째를 넘지 않도록 for 구문의 range를 len(arr)-r+1로 제한했기 때문에 n=r까지인 상황까지만 가게 됩니다.

처음에는 재귀함수가 프로그래밍 되는 과정을 생각하는 게 어려웠는데, 계속 생각하다보니 어떤 식으로 돌아가는 지 조금이나마 이해가 되는 것 같습니다. 감사합니다~!