[알고리즘] 백트래킹 - 경우의 수 문제

원하는 조합과 순열 만드는 방법

1. for문으로 구현하는 방법과

2. 재귀함수로 구현하는 방법! 

 

원하는 숫자의 조합이나 순열을 만들고, 

객체를 선택하는 방법이다!

 

경우의수 문제는 

• 중복순열
• 순열
• 조합

 

중복순열

• n개 중 하나를 m번 선택하기 
• 중복 O, 순서 O

for 문으로 구현

m = 4
n = 5

# 1번 for 문 구현 -> 4중 반복문으로 구현되어야함 

num_arr = list(range(1, n+1))
for i in range(n):
    for j in range(n):
        for x in range(n):
            for y in range(n):
                print(num_arr[i], num_arr[j], num_arr[x], num_arr[y])

 

재귀함수로 구현

# 2번 재귀함수로 구현
answer = []
def print_ans():
    for elem in answer:
        print(elem, end=" ")
    print()

def r_permut(curr_num):
    if curr_num > m:
        print_ans()
        return
    
    for i in range(1, n+1):
        answer.append(i)
        r_permut(curr_num+1)
        answer.pop()

r_permut(1)

 

순열

• n개 중에 m개 골라 나열하기
• 중복 x, 순서 o

for문으로 구현

n = 5
m = 4

num_arr = list(range(1, n+1))
for i in range(n):
    for j in range(n):
        for x in range(n):
            for y in range(n):
                if i == j or i == x or i == y or j == x or j == y or x == y:
                    continue
                print(num_arr[i], num_arr[j], num_arr[x], num_arr[y])

재귀함수로 구현

n = 5
m = 4
answer = []
visited = [0] * (n+1)

def print_ans():
    for elem in answer:
        print(elem, end=" ")
    print()

def permutation(curr_num):
    if curr_num > m:
        print_ans()
        return

    for i in range(1, n+1):
        if visited[i] == 1:
            continue
        answer.append(i)
        visited[i] = 1
        permutation(curr_num+1)
        visited[i] = 0
        answer.pop()
    

permutation(1)

 

 

 

조합

• N개 중 M개를 고르기
• 중복 X, 순서 X

for문으로 구현

n = 5
m = 4
num_arr = list(range(1, n+1))

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            for l in range(k+1, n):
                print(num_arr[i], num_arr[j], num_arr[k], num_arr[l])

 

재귀함수로 구현

n, m = 3, 2 
answer = []

def print_ans():
    for elem in answer:
        print(elem, end=" ")
    print()

def choose(curr_num, cnt):
    if curr_num == n+1:
        if cnt == m:
            print_ans()
            #return return이 여기 있으면 cnt가 m일 때만 종료됨
        return #cnt != m일 때에도 curr_num == n+1이면 종료되어야함 
    
    answer.append(0)
    choose(curr_num+1, cnt)
    answer.pop()

    answer.append(1)
    choose(curr_num+1, cnt+1)
    answer.pop()

    return

choose(1, 0)

 

 

재귀함수는 역시 종료 조건이 중요한데

종료조건에서 return의 위치에 따라 오류가 날 수도 있다는 것을 알았음.

 

재귀함수로 조합 구현 - 2가지 방식

n, m = map(int, input().split())
c_list = []

def print_ans():
    for i in range(n):
        if c_list[i] == 1:
            print(i+1, end=" ")
    print()


def choose1(curr_num, cnt): # 뽑을 애들의 자리를 1로 표시하는 함수
    if cnt > m:
        return
    if curr_num > n:
        if cnt == m:
            print_ans()
        return
    
    c_list.append(1)
    choose(curr_num+1, cnt+1)
    c_list.pop()

    c_list.append(0)
    choose(curr_num+1, cnt)
    c_list.pop()

def choose2(curr_num, cnt): # 선택할 현재 넘버를 리스트에 append 해주는 방식
    if curr_num > n:
        if cnt == m:
            print(c_list)
        return
    
    # 1일 때 리스트에 curr_num append 하면 나중에 그냥 리스트 출력하면 답 나옴
    c_list.append(curr_num)
    choose(curr_num+1, cnt+1)
    c_list.pop()

    choose(curr_num+1, cnt)
    
choose(1, 0)