조합을 구하는 알고리즘

GitHub - Seungkyu-Han/PS_strategy: 알고리즘 분류하는 워크플레이스

브루트포스와 재귀를 이용하여 n개의 원소 중에서 m개를 고르는 조합을 찾는 알고리즘이다.

def pick(cur, cur_list):
    if cur == n:
        print(*cur_list[1:])
        return

    for i in range(cur_list[-1] + 1, m + 1):
        cur_list.append(i)
        pick(cur + 1, cur_list)
        cur_list.pop(-1)

 

함수를 사용했고 cur가 현재 선택한 원소의 수, cur_list가 현재 선택한 원소의 배열이다.

 

여기서 수를 작은 수부터 차례로 넣었기 때문에 다음에 추가할 수는 cur_list[-1]보다 큰 수부터 보면 된다.

(현재 함수에서 추가할 수는 cur_list[-1]보다 1 큰 수 부터 m까지만 보면 된다는 말)

 

반복문을 이용하여 수를 넣어주고, 그 배열을 바탕으로 함수를 호출하고, 배열에 들어간 수를 다시 빼주고를 반복한다.

브루투포스로 분류하기는 했지만 백트래킹 알고리즘이기도 하다. (코드를 조금만 수정하면 백준 15650의 답이다.)

 

해당함수를 바탕으로 작성한 전체 코드이다.

함수가 현재 배열에 있는 가장 마지막 값을 기준으로 작동하기 때문에 배열에 0을 넣어주고 시작한다.

출력시에는 1번 인덱스부터 출력할 수 있도록 한다.

# m개 중에서 n개를 고르는 모든 조합을 찾는 알고리즘, 완전탐색

import sys

print('n과 m을 입력 : ', end='')
n, m = map(int, sys.stdin.readline().split())


def pick(cur, cur_list):
    if cur == n:
        print(*cur_list[1:])
        return

    for i in range(cur_list[-1] + 1, m + 1):
        cur_list.append(i)
        pick(cur + 1, cur_list)
        cur_list.pop(-1)


pick(0, [0])