재귀 함수로 부분집합 구해보기

 

 

✏️ 목표

숫자를 하나 입력받아 해당 숫자까지의 모든 자연수들로 구성된 부분집합을 만들어 출력해 보자.

(공집합은 출력하지 않는다.)

 

 

 

❓ 부분집합 구하기

간단한 예를 들어, 3이라는 숫자를 입력받았다고 해보자.

3 이하의 자연수는 1, 2, 3이므로 공집합을 제외하고 이 범위에 있는 자연수들로 구성된 부분집합들을 출력해야 한다. (출력 순서 상관 X)

따라서 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이렇게 7개의 부분집합들이 출력되어야 한다.

 

트리를 구성할 때는  처음에는 무(無)에서 시작하여 왼쪽 자식 노드는 숫자를 포함시키고, 오른쪽 자식 노드는 숫자를 포함시키지 않는 방향으로 구성하면 된다. 즉, 해당 숫자의 사용 여부에 따라 갈라지게 되는 것이다.

1️⃣ 체크 리스트 하나를 만들어 그 리스트는 해당 인덱스 + 1에 해당하는 숫자와 같은 원소가 포함되어야 하면 해당 인덱스값으로 1, 포함되지 않아야 하면 0을 기록한다.

 

2️⃣ 트리의 말단 노드(가장 아래의 노드)에 닿으면 1이 기록된 인덱스의 원소들만 출력하고 해당 함수는 종료하면 된다.

재귀함수의 인자로는 인덱스를 넣어 인덱스가 3이 되었을 때 말단 노드에 닿은 것이므로 이때 사용하기로 한 숫자들을 출력하고 함수를 종료한다.

* 인덱스는 트리의 현재 레벨-1 을 따라가도록 설계한다.

 

3️⃣ 트리를 그림으로 그리면 다음과 같다.

 

 

 

 

💻 Python으로 코드 작성해보기

 

# DFS 함수 정의
def DFS(i):
    if i == n:     # 말단 노드를 지나가면
    	for idx in range(n):
            if ch[idx] == 1:     # 체크리스트에서 해당 인덱스에서의 값이 1이면 부분집합에 포함된 원소이므로
                print(idx + 1, end=' ')     # 출력 (공백으로 숫자 구분)
        print()     # 부분집합 출력이 모두 끝나면 다음 부분집합은 다음 줄에 출력하기 위해 적어줌.
    else:     # 말단 노드를 지나지 않은 상태면
    	ch[i] = 1     # 체크리스트의 i번째에 해당하는 부분을 1로 바꾸기
        DFS(i+1)     # 인덱스 하나씩 늘리기
        ch[i] = 0     # 체크리스트의 i번째에 해당하는 부분을 0으로 바꾸기
        DFS(i+1)     # 인덱스 하나씩 늘리기

# 입력받기, 필요한 리스트 세팅해놓기
n = int(input())
ch = [0] * n     # 각 인덱스 + 1의 숫자가 사용되었는지 여부를 체크하는 체크 리스트
DFS(0)     # 인덱스는 0부터 시작

 

<결과>

트리 그림에서의 왼쪽에서의 말단 노드의 값부터 차례로 출력된 것을 볼 수 있다.

 

1 2 3
1 2
1 3
1
2 3
2
3

 

 

코드 진행 순서를 작성해 보면 다음과 같다. 

(함수는 후입선출인 스택 구조로 쌓인다는 것을 잊지 말자!)

 

 

위 분석에서 계속해서 나오는 각각의 DFS(i) 함수는 트리에서 각 노드에 해당하는 것을 볼 수 있다.

 

 

 

 

📌 참고한 강의

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의