1. 탐색(Search)

탐색은 많은 데이터들 가운데 원하는 데이터를 찾아가는 과정이다.

2. DFS

DFS는 깊이 우선 탐색이라 불리며 그래프에서 깊은 부분을 우선적으로 탐색하여 출력하는 알고리즘이다. 마지막 노드까지 내려가면 더 이상 깊이 탐색할 것이 없기에 마지막 노드를 출력하거나 체크한 후에 부모 노드로 다시 올라가고(Backtracking) 다른 자식 노드로 뻗어간다. 그래프는 아래와 같이 노드(Node)와 노드들 사이를 이어주는 간선(Edge)으로 이루어져있다. 그래프는 트리의 형식일 수도 있고 무작위 연결된(양방향 연결 혹은 방향 연결) 형식이 수도 있다.
DFS는 함수가 호출되는 순간부터 순서대로 stack에 다음과 같은 형식으로 쌓인다

def DFS(n):
    if n == 5:
        return
    n += 1
    DFS(n)# <- 
    print(n, end=' ')
DFS(0)
출력:
5 4 3 2 1

1. 먼저 0이 n으로 입력되면 1을 더한 후 재귀로 DFS(1)을 호출한다. 이때 stack에는 [DFS(0)]가 쌓이고 '<-'까지만 진행된다.
2. 다시 n에 1을 더하고 DFS(2)를 호출하면 stack에는 [DFS(0), DFS(1)]이 쌓이고 '<-'까지만 실행이 되고 다시 재귀가 일어난다.
3. 이런 순서로 stack에는 [DFS(0), DFS(1), DFS(2), DFS(3), DFS(4)]가 쌓이고 마지막으로 n이 5가 된 순간 if 조건문에 의해 함수는 종료된다.
4. stack은 후입선출이므로 DFS(4)가 다시 작동을 하는데 '<-'까지만 작동을 했으므로 그 다음 실행문인 print()문을 통해 수가 출력되고 함수가 끝이난다.
5. stack가 빌 때까지 stack에 쌓인 호출문들이 다음 실행문인 print()문을 실행한다.
   이때 보면 0부터 시작하여 1씩 더해가면서 트리를 탐색한다고 보았을 때 가장 나중의 5가 먼저 출력이 되는 것을 볼 수 있듯이, 재귀 함수가 마지막까지 진행되었을 때 break문을 실행하여 stack에 쌓인 재귀 함수들을 종료시켜나간다.
   알고리즘 문제의 형식마다 적용해야 하는 방법은 천차만별이지만 대표적으로 4가지를 염두해두고 DFS를 사용하는데, 순열, 중복순열, 조합, 부분집합을 구하는 방식으로 문제를 풀어나간다. 이번 챕터는 조합이며 각각의 방식에 따라 어떻게 DFS가 이용되는지 알아보자.

3. 부분집합

두 집합 A, B에서 A의 모든 원소가 집합 B에 포함될 때, A를 B의 부분집합이라고 한다. 예로 원소 3개를 가지는 집합 n(n = [2, 4, 6])이 있을 때 n의 부분집합은 공집합, [2], [4], [6], [2, 4], [2, 6], [4, 6], [2, 4, 6]으로 공집합을 포함하여 모두 8가지가 n의 부분집합이라고 할 수 있다. 이런 부분집합을 DFS로 탐색할 때는 먼저, 원소를 가지고 부분집합을 만들 때 원소를 부분집합에 포함 시킬 것인지 아닌지를 기준으로 원소들을 탐색해나간다. 그래서 첫 번째 원소부터 시작하여 포함을 선택하거나 배제를 선탁하거나 양자택일로 두 갈래의 깊이 우선 탐색이 진행되면서 모든 원소를 순회하는 형식이다.

4.1 문제

n = [2, 4, 6, 8]
문제1 : n개의 숫자카드가 주어지면 DFS를 이용하여 부분집합을 출력하고 부분집합이 몇 개 생성되는지도 출력하시오.
문제2 : n개의 숫자카드가 주어지면 DFS를 이용하여 부분집합의 합을 출력하고 부분집합이 몇 개 생성되는지도 출력하시오.

4.2 풀이

위 그림과 같이 원소를 인덱스 번호 순으로 순회하면서 해당 인덱스의 원소를 포함할지 배제할지를 선택해 간다면 총 16가지의 부분집합이 나온다. 이렇게 마지막 level까지 내려가서 문제에서 제시하는 조건에 맞춰 출력이나 합, 곱 등의 연산을 진행하면 된다. DFS를 이용하여 부분집합을 구할 시 주의할 점이 있는데, 2갈래씩 뻗어가기에 연산 횟수가 빅오 표기법에 따라 O(2**n) 지수 함수로 연산이 된다. 그러므로 원소의 수가 24가 넘어간다면(연산횟수는 1600만을 넘는다) 시간 초과에 걸릴 수 있다. 물론 해결법으로 다이나믹 프로그래밍(DP:Dynamic Programming, 동적 계획법)을 통해 해결할 수 있지만, 현재 단계에서 원소의 수를 염두해두는 것으로 마무리하겠다.
1. 재귀함수를 호출하는 부분을 2부분으로, '포함' or '배제'를 할 수 있는 재귀함수를 2개 생성한다.
2.1 재귀함수 DFS는 깊이만 들어가고 더할지 말지는 전위순회로 변수에 담을 수 있도록 한다. 포함한다면 리스트에 append, 포함하지 않는다면 앞에 append했던 것을 pop시키도록 한다.
2.2. 재귀함수 DFS 매개변수를 level과 집합의 합을 계속 업데이트 할 변수를 각각 생성한다.
3. 마지막 level까지 DFS가 순회했다면 부분집합을 출력한다.(출력할 변수 생성)

풀이1

def DFS(lv):
    global count
    if lv == len(n):
        for i in answer:
            print(i, end=' ')
        count += 1
        print()
    else:
        answer.append(n[lv])# '포함'을 먼저 선택한 후 DFS를 순회
        DFS(lv + 1)# DFS는 깊이만 순회한다. 순회에 따라서 순서대로 '포함'을 먼저 선택한 후 '배제'를 선택하는 식이다.
        answer.pop() #<- backtracking 지점이다. 순서가 먼저 '포함'을 선택한 후, '배제'할 때에는 pop하여 제외시킨 후 다시 DFS를 호출
        DFS(lv + 1)
if __name__ == '__main__':
    n = [2, 4, 6, 8]
    count = 0
    answer = []
    DFS(0)
    print(count)
출력:
2 4 6 8 
2 4 6 
2 4 8 
2 4 
2 6 8 
2 6 
2 8 
2 
4 6 8 
4 6 
4 8 
4 
6 8 
6 
8 
  <- 공집합
count: 16

풀이2

이번에는 매개변수를 하나 추가하여 매개변수 자체가 부분집합의 합이된다.
def DFS(lv, sumN):
    global count
    if lv == len(n):
        count += 1
        print(f'{count}번째 합:', sumN)
    else:
        DFS(lv + 1, sumN + n[lv])# 부분집합에 현재의 집합 원소를 더하는 것을 선택.
        DFS(lv + 1, sumN)# 부분집합에서 현재의 집합 원소를 '배제'하는 것을 선택.
if __name__ == '__main__':
    n = [2, 4, 6, 8]
    count = 0
    answer = []
    DFS(0, 0)
    print('count:', count)
출력:
1번째 합: 20
2번째 합: 12
3번째 합: 14
4번째 합: 6
5번째 합: 16
6번째 합: 8
7번째 합: 10
8번째 합: 2
9번째 합: 18
10번째 합: 10
11번째 합: 12
12번째 합: 4
13번째 합: 14
14번째 합: 6
15번째 합: 8
16번째 합: 0
count: 16

매개변수를 문제의 조건에 맞춰 변형할 수 있도록 한다.