# 재귀함수로 부분집합 만들기

About this offer

1. 코드 name = "ABC" def abc(level, path): # 종료 조건 if level == 3: print(*path) return # 현재 문자를 선택하지 않는 경우 abc(level + 1, path) # 현재 문자를 선택하는 경우 abc(level + 1, path + [name[level]]) abc(0, []) 실행 결과는 다음과 같다. (빈 줄) C B B C A A C A B A B C ABC 의 각 문자를 선택하거나 선택하지 않는 모든 경우 를 구하는 코드이다. 2. name은 무엇인가? name = "ABC" name 은 부분집합을 만들 원본 문자열이다. 문자열도 리스트처럼 인덱스를 이용해서 각 문자에 접근할 수 있다. name[0] # "A" name[1] # "B" name[2] # "C" 따라서 level 값을 이용하면 현재 선택할 문자를 가져올 수 있다. level = 0 → name[0] → A level = 1 → name[1] → B level = 2 → name[2] → C 즉, 이 코드에서 level 은 단순히 재귀의 깊이만 의미하는 것이 아니라 현재 어떤 문자를 선택할 차례인지 나타내는 역할 도 한다. 3. level과 path의 의미 함수를 보면 두 개의 매개변수가 있다. def abc(level, path): level 현재 어떤 문자를 선택할지 결정하는 단계이다. level 0 → A 선택 level 1 → B 선택 level 2 → C 선택 level 3 → 모든 선택이 끝났으므로 출력 path 지금까지 선택한 문자들을 저장한다. 예를 들어 abc(2, ["A"]) 라면 현재 상태는 A는 선택되어 있음 B는 선택하지 않았음 현재 C를 선택할 차례 라고 볼 수 있다. 4. 종료 조건 if level == 3: print(*path) return ABC 는 총 3개의 문자이므로 level 이 3이 되었다는 것은 A 선택 완료 B 선택 완료 C 선택 완료 즉, 모든 문자에 대해 선택할지 말지를 결정했다는 뜻이다. 따라서 현재까지 선택된 path 를 출력하고 현재 함수 호출을 종료한다. 여기서 중요한 점은 return 을 만났다고 해서 전체 프로그램이 끝나는 것이 아니라는 것이다. 현재 실행 중인 abc() 호출만 종료되고, 이 함수를 호출했던 이전 abc() 로 돌아간다. 5. 두 개의 재귀 호출 이 코드에서 가장 중요한 부분이다. abc(level + 1, path) abc(level + 1, path + [name[level]]) 각 문자마다 두 가지 선택을 하는 것이다. 첫 번째 재귀 abc(level + 1, path) 현재 문자를 선택하지 않는다. path 를 그대로 다음 단계에 전달한다. 두 번째 재귀 abc(level + 1, path + [name[level]]) 현재 문자를 선택한다. 현재 문자인 name[level] 을 path 에 추가해서 다음 단계로 전달한다. 즉, 첫 번째 재귀 → 선택 X 두 번째 재귀 → 선택 O 라고 생각하면 된다. 6. path + [name[level]] 의 의미 예를 들어 현재 상태가 다음과 같다고 하자. level = 0 path = [] 그러면 name[level] 은 name[0] 이므로 "A" 가 된다. 하지만 다음처럼 작성할 수는 없다. [] + "A" [] 는 리스트이고 "A" 는 문자열이라 자료형이 다르기 때문이다. 따라서 "A" 를 리스트로 감싼다. [name[level]] 결과는 ["A"] 가 된다. 따라서 path + [name[level]] 은 [] + ["A"] 가 되고 결과는 ["A"] 가 된다. 예를 들어 이미 A가 들어있고 B를 추가한다면 ["A"] + ["B"] 결과는 ["A", "B"] 가 된다. 7. 처음 함수가 호출되는 과정 처음에는 abc(0, []) 를 호출한다. 현재 상태는 level = 0 path = [] 이다. level=0 이므로 현재 선택할 문자는 name[0] = "A" 이다. 코드에서는 선택하지 않는 경우가 먼저 작성되어 있으므로 abc(level + 1, path) 가 먼저 실행된다. 따라서 abc(1, []) 가 호출된다. 이것은 A를 선택하지 않았다. 이제 B를 선택할 차례다. 라는 뜻이다. 8. abc(1, [])부터 실행 과정 현재 abc(1, []) 이다. level=1 이므로 B를 선택할 차례이다. 먼저 B를 선택하지 않는다. abc(2, []) 이제 C를 선택할 차례이다. 여기에서도 C를 선택하지 않는 재귀가 먼저 실행된다. abc(3, []) level == 3 이 되었으므로 print(*path) 가 실행된다. 현재 path=[] 이므로 빈 줄이 출력된다. (빈 줄) 그리고 return 을 만나 이전 함수인 abc(2, []) 로 돌아간다. 9. C를 선택하는 경우 abc(2, []) 에서 첫 번째 재귀 호출이 끝났으므로 두 번째 재귀 호출을 실행한다. abc(level + 1, path + [name[level]]) 현재 level=2 이므로 name[2] = "C" 이다. 따라서 abc(3, ["C"]) 가 호출된다. level == 3 이므로 출력한다. C 현재까지 출력 결과는 (빈 줄) C 이다. 10. 다시 돌아와 B를 선택 C를 선택하는 경우까지 모두 끝나면 이전 함수인 abc(1, []) 로 돌아온다. 이 함수에서 B를 선택하지 않는 경우는 모두 확인했다. 따라서 이제 B를 선택한다. abc(2, ["B"]) 여기에서 다시 C에 대해 두 가지 경우를 확인한다. C를 선택하지 않으면 abc(3, ["B"]) 따라서 B 가 출력된다. C를 선택하면 abc(3, ["B", "C"]) 따라서 B C 가 출력된다. 현재까지 결과는 (빈 줄) C B B C 이다. 여기까지가 A를 선택하지 않았을 때 나올 수 있는 모든 경우 이다. 11. 이제 A를 선택 A를 선택하지 않는 모든 경우가 끝났으므로 가장 처음 호출했던 abc(0, []) 로 돌아간다. 처음 함수의 구조는 다음과 같았다. # A 선택 X abc(level + 1, path) # A 선택 O abc(level + 1, path + [name[level]]) 첫 번째 재귀가 전부 끝났으므로 이제 두 번째 재귀를 실행한다. abc(1, ["A"]) 즉, A를 선택한 상태에서 다시 B와 C를 선택할지 결정한다. B를 선택하지 않고 C도 선택하지 않으면 A B를 선택하지 않고 C를 선택하면 A C B를 선택하고 C를 선택하지 않으면 A B B와 C를 모두 선택하면 A B C 가 출력된다. 12. 전체 재귀 트리 전체 과정을 트리 형태로 나타내면 다음과 같다. abc(0, []) A 선택 / \ A ❌ A ⭕ abc(1, []) abc(1,[A]) B 선택 B 선택 / \ / \ B ❌ B ⭕ B ❌ B ⭕ abc(2,[]) abc(2,[B]) abc(2,[A]) abc(2,[A,B]) C 선택 C 선택 C 선택 C 선택 / \ / \ / \ / \ C❌ C⭕ C❌ C⭕ C❌ C⭕ C❌ C⭕ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ [] [C] [B] [B,C] [A] [A,C] [A,B] [A,B,C] 출력: 빈칸 C B B C A A C A B A B C 여기서 왼쪽 가지 → 현재 문자 선택 X 오른쪽 가지 → 현재 문자 선택 O 라고 생각하면 이해하기 쉽다. 13. 왜 출력 순서가 이렇게 될까? 최종 출력은 (빈 줄) C B B C A A C A B A B C 순서이다. 그 이유는 코드에서 선택하지 않는 재귀 호출이 먼저 작성되어 있기 때문 이다. abc(level + 1, path) # 선택 X abc(level + 1, path + [name[level]]) # 선택 O 파이썬은 첫 번째 재귀 호출을 먼저 실행한다. 그리고 그 재귀 호출 내부에서도 다시 첫 번째 재귀 호출을 실행한다. 따라서 처음에는 계속 선택하지 않는 방향으로 내려간다. A 선택 X ↓ B 선택 X ↓ C 선택 X ↓ [] 그 후 이전 단계로 돌아와 C를 선택한다. A X B X C O → [C] 다시 이전 단계로 돌아와 B를 선택하고 같은 과정을 반복한다. 전체 실행 순서를 간단하게 나타내면 다음과 같다. A ❌ B ❌ C ❌ → [] A ❌ B ❌ C ⭕ → [C] A ❌ B ⭕ C ❌ → [B] A ❌ B ⭕ C ⭕ → [B, C] A ⭕ B ❌ C ❌ → [A] A ⭕ B ❌ C ⭕ → [A, C] A ⭕ B ⭕ C ❌ → [A, B] A ⭕ B ⭕ C ⭕ → [A, B, C] 따라서 출력 결과가 (빈 줄) C B B C A A C A B A B C 순서가 된다. 14. 재귀에서 중요한 흐름 재귀 함수는 단순히 아래로만 내려가는 것이 아니다. 예를 들어 abc(1, []) ↓ abc(2, []) ↓ abc(3, []) 까지 내려가면 level == 3 이 되어 return 한다. 그러면 프로그램 전체가 끝나는 것이 아니라 abc(3, []) ↓ return abc(2, []) ← 다시 여기로 돌아옴 처럼 이전 함수로 돌아온다. 그리고 이전 함수에 아직 실행하지 않은 코드가 있다면 이어서 실행한다. 따라서 재귀의 흐름은 1. 함수를 호출하면서 아래로 내려간다. 2. 종료 조건을 만난다. 3. return한다. 4. 이전 함수로 돌아온다. 5. 남아 있는 코드를 실행한다. 6. 다시 재귀 호출을 한다. 라고 이해할 수 있다. 15. 부분집합의 개수가 8개인 이유 ABC 에는 총 3개의 문자가 있다. 각 문자마다 선택은 두 가지이다. A → 선택 / 선택 X B → 선택 / 선택 X C → 선택 / 선택 X 따라서 경우의 수는 2 × 2 × 2 = 8 즉, 23 = 8 개의 부분집합이 만들어진다. 일반적으로 원소가 N 개라면 부분집합의 개수는 2^N 개이다. 핵심 정리 abc(level + 1, path) → 현재 문자를 선택하지 않는다. abc(level + 1, path + [name[level]]) → 현재 문자를 선택한다. 그리고 if level == 3: print(*path) return 은 모든 문자에 대한 선택이 끝났을 때 현재까지 선택한 결과를 출력하고 이전 재귀 호출로 돌아가는 역할을 한다. 결국 이 코드는 각 문자마다 선택한다 / 선택하지 않는다 두 가지 경우로 나누어 재귀적으로 탐색하면서 모든 부분집합을 만드는 코드이다. 기억할 한 줄 재귀로 부분집합을 만들 때는 각 원소마다 선택 X / 선택 O 두 갈래로 나누고, 종료 조건에 도달하면 지금까지 선택한 결과를 확인한다.