1. 재귀
프로그래밍에서 재귀란 한 함수가 자신을 호출해 반복적으로 실행되는 것을 뜻합니다.
이러한 함수를 재귀 함수라고 합니다.
예를 들어 다음과 같은 함수가 있다고 해봅시다.
import time
def func():
print("바트가 호머가 들고 있는 그림을 보고 있어요.")
print("호머가 들고 있는 그림 속에는...")
time.sleep(1)
func()
func()
# 바트가 호머가 들고 있는 그림을 보고 있어요.
# 호머가 들고 있는 그림 속에는...
# 바트가 호머가 들고 있는 그림을 보고 있어요.
# 호머가 들고 있는 그림 속에는...
# 바트가 호머가 들고 있는 그림을 보고 있어요.
# 호머가 들고 있는 그림 속에는...
# 바트가 호머가 들고 있는 그림을 보고 있어요.
# 호머가 들고 있는 그림 속에는...
# ...func라는 함수가 실행되면 일정한 로직을 수행하고 스스로 자기 자신을 호출합니다.
호출된 func는 또 다시 로직을 수행하고 자기 자신을 호출합니다.
이렇게 함수 내부에서 자기 자신을 호출하는 함수를 재귀 함수라고 합니다.
그리고 재귀 함수는 종료 조건(Base case)이 없다면 무한히 반복됩니다.
아래는 종료 조건을 사용하여 만든, 1부터 n까지의 수를 모두 더하는 재귀 함수입니다.
def func(n):
if n == 1: # 종료 조건
return 1
return n + func(n-1)
print(func(5))
# 15
또 재귀 함수는 반복문과 다르게 함수가 호출될 때마다 호출 스택이 쌓여 메모리에 영향을 줍니다.
파이썬에는 재귀 함수가 무한 반복하여 스택 오버플로우가 발생하지 않도록 일정 횟수 이상 깊어지면 RecursionError를 발생시켜줍니다.
재귀 깊이 제한은 1000으로 초기값이 설정되어 있습니다.
def func(n):
print(n)
return func(n+1)
func(1)
# 1
# 2
# ...
# 997
# RecursionError: maximum recursion depth exceeded while calling a Python object문제 풀이를 위해 재귀 깊이 제한을 늘리려면 sys 모듈의 setrecursionlimit 함수를 사용합니다.
from sys import setrecursionlimit
setrecursionlimit(5000)
def func(n):
print(n)
return func(n+1)
func(1)
# 1
# 2
# ...
# 4997
# RecursionError: maximum recursion depth exceeded while calling a Python object
재귀 함수는 스택 오버플로우가 발생할 수도 있는 여지도 있고, 반복문 보다 느리다는 단점이 있습니다.
하지만 코드를 간결하고 직관적으로 짤 수 있다는 장점을 가지고 있습니다.
아래는 for문과 while문을 사용하여 만든 1부터 n까지의 수를 모두 더하는 함수입니다. 재귀 함수의 코드가 더 간결합니다.
# 재귀 함수
def func(n):
if n == 1: # 종료 조건
return 1
return n + func(n-1)
print(func(5))
# 15
# for문
def func(n):
res = 0
for i in range(n+1):
res += i
return res
print(func(5))
# 15
# while문
def func(n):
res = 0
i = 1
while i <= n:
res += i
i += 1
return res
print(func(5))
# 15
이제 재귀를 사용하여 문제를 풀어봅시다.
가. 피보나치 수 5
https://www.acmicpc.net/problem/10870
피보나치 수열은 1, 1로 시작하여 그 다음 수는 이전 수 두 개를 합쳐서 만드는 수열입니다.(0번째는 0)
def fibo(n):
return fibo(n-1) + fibo(n-2)
print(fibo(10))
# RecursionError: maximum recursion depth exceeded직관적으로 n을 받아 n-1 과 n-2 를 다시 넘겨주는 재귀 함수를 만들었습니다.
하지만 아직 종료 조건이 없기 때문에 무한 반복해 에러가 발생합니다.
def fibo(n):
if n < 2: # 종료 조건
return n
return fibo(n-1) + fibo(n-2)
print(fibo(10))
# 550번째과 1번째에 0과 1을 반환하도록 종료 조건을 추가하면 원하는 값이 나옵니다.
나. 팩토리얼 3
https://www.acmicpc.net/problem/27434
(이 문제는 python3 대신 pypy3로 제출하라고 되어있습니다. pypy3는 python3 보다 속도는 빠르지만 메모리를 더 사용합니다.)
팩토리얼은 1부터 n까지의 수를 모두 곱한 수입니다. n! 이라고 씁니다.
0! 은 1입니다.
피보나치 수열과 비슷하게 n을 받아 n-1을 넘겨주는 재귀 함수를 만들어봅시다.
def facto(n):
return n * facto(n-1)
print(facto(10))
# RecursionError: maximum recursion depth exceeded역시 종료 조건이 없어서 RecursionError가 발생합니다.
n이 0과 1이면 1을 반환하도록 종료 조건을 추가합니다.
def facto(n):
if n < 2:
return 1
return n * facto(n-1)
print(facto(10))
# 3628800문제에서 n의 최대값이 10만이라고 했으니 10만을 넣어 테스트해봅시다.
def facto(n):
if n < 2:
return 1
return n * facto(n-1)
print(facto(100000))
# RecursionError: maximum recursion depth exceeded10만은 설정되어 있는 깊이 제한보다 깊기 때문에 RecursionError가 발생합니다.
따라서 깊이 제한을 늘려주어야 합니다.
from sys import setrecursionlimit
setrecursionlimit(1000000)위 코드를 상단에 추가해 제출하면 통과합니다.
깊이 제한을 무조건 늘리는 것이 좋은 것은 아닙니다.
문제의 제한 범위를 살펴보며 적절하게 깊이 제한을 늘리는 것이 또 다른 에러를 발생시키지 않는 방법입니다.
다. 재귀함수가 뭔가요?
https://www.acmicpc.net/problem/17478
위 그림과 같은 상황을 코드로 구현해보는 문제입니다.
다만 위 그림과 다른 점은, 무한 반복이 아니라는 점입니다.
먼저 반복되는 부분을 출력하는 함수를 만들어보겠습니다.
def solve():
print('"재귀함수가 뭔가요?"')
print('"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
print('마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
print('그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
print('라고 답변하였지.')
solve()
# "재귀함수가 뭔가요?"
# "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
# 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
# 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
# 라고 답변하였지.이제 종료 조건을 추가하여 정해진만큼만 반복하도록 하고, 적절한 위치에서 호출하도록 코드를 작성합니다.
N = 2
def solve(n):
print('"재귀함수가 뭔가요?"')
if n == N:
print(f'"재귀함수는 자기 자신을 호출하는 함수라네"')
else:
print('"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
print('마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
print('그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
solve(n+1)
print('라고 답변하였지.')
solve(0)
# "재귀함수가 뭔가요?"
# "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
# 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
# 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
# "재귀함수가 뭔가요?"
# "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
# 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
# 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
# "재귀함수가 뭔가요?"
# "재귀함수는 자기 자신을 호출하는 함수라네"
# 라고 답변하였지.
# 라고 답변하였지.
# 라고 답변하였지.마지막으로 첫 문장을 추가하고, 빈 칸처리를 위해 매개변수 n을 사용해봅시다.
N = 2
def solve(n):
line = "____" * n
print(f'{line}"재귀함수가 뭔가요?"')
if n == N:
print(f'{line}"재귀함수는 자기 자신을 호출하는 함수라네"')
else:
print(f'{line}"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
print(f'{line}마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
print(f'{line}그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
solve(n+1)
print(f'{line}라고 답변하였지.')
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
solve(0)
# 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
# "재귀함수가 뭔가요?"
# "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
# 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
# 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
# ____"재귀함수가 뭔가요?"
# ____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
# ____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
# ____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
# ________"재귀함수가 뭔가요?"
# ________"재귀함수는 자기 자신을 호출하는 함수라네"
# ________라고 답변하였지.
# ____라고 답변하였지.
# 라고 답변하였지.라. 바이러스
https://www.acmicpc.net/problem/2606
이전에 배운 그래프 탐색 문제입니다.
깊이우선탐색(DFS)을 재귀 함수로 구현하면 쉽게 구현이 가능합니다.
graph = {
1: [2, 5],
2: [1, 3, 5],
3: [2],
4: [7],
5: [1, 2, 6],
6: [5],
7: [4]
}
visited = set()
cnt = 0
def dfs(n):
if n in visited:
return
visited.add(n)
print(n)
global cnt
cnt += 1
for m in graph[n]:
dfs(m)
dfs(1)
# 1
# 2
# 3
# 5
# 6
print(cnt)
# 5재귀적으로 함수가 호출되므로 더이상 탐색이 불가능할 때까지 깊이 우선 탐색을 실행합니다.
마. 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729
하노이의 탑을 옮기는 과정을 나타내는 문제입니다.
하노이의 탑도 재귀 함수하면 떠오르는 대표적인 문제입니다.
3층의 하노이의 탑을 옮기는 과정을 봅시다.
1번 기둥에 있는 3층의 탑을 3번 기둥으로 옮기려면,
먼저 바닥을 제외한 나머지 탑을 빈 자리로 옮깁니다.
그 다음 바닥을 원하는 기둥으로 옮깁니다.
마지막으로 나머지 탑을 다시 원하는 기둥으로 옮깁니다.
우리가 생략한 과정이 있습니다.
바로 바닥을 제외한 2층의 기둥을 옮기는 과정입니다.
이 과정은 사실 앞에서 봤던 과정과 같습니다.
먼저 바닥을 제외한 나머지 탑을 빈 자리로 옮깁니다.
그 다음 바닥을 원하는 기둥으로 옮깁니다.
마지막으로 나머지 탑을 다시 원하는 기둥으로 옮깁니다.
또 생략된 과정이 있습니다.
바로 바닥을 제외한 1층의 기둥을 옮기는 과정입니다.
이 과정은 한 층 밖에 없기 때문에 그냥 옮기면 됩니다.(종료 조건)
과정을 살펴보니 탑을 옮기는 과정이 재귀적으로 반복됨을 알 수 있습니다.
다만 주의할 점이 현재 탑의 기둥, 옮겨야 하는 기둥, 남는 기둥이 계속해서 바뀐다는 점입니다.
이를 주의하면서 코드를 짜봅시다.
n = 3
def 하노이(n, 탑의기둥, 남는기둥, 옮길기둥):
if n == 1:
print(탑의기둥, 옮길기둥)
else:
하노이(n-1, 탑의기둥, 옮길기둥, 남는기둥)
하노이(1, 탑의기둥, 남는기둥, 옮길기둥)
하노이(n-1, 남는기둥, 탑의기둥, 옮길기둥)
하노이(n, 1, 2, 3)
# 1 3
# 1 2
# 3 2
# 1 3
# 2 1
# 2 3
# 1 32. 백트래킹
백트래킹은 우리말로 퇴각 검색이라고도 합니다.
백트래킹의 시작은 깊이 우선 탐색입니다.
(깊이 우선 탐색은 재귀 함수를 잘 다루면 쉬우므로, 백트래킹도 주로 재귀 함수로 구현됩니다.)
깊이 우선 탐색은 가능한 모든 탐색이 종료되면 그 다음 탐색으로 넘어갑니다.
하지만 백트래킹은 탐색 도중 더이상 탐색의 필요가 없어지는 순간, 탐색을 종료(퇴각)하고 그 다음 탐색으로 넘어갑니다.
예를 들어 남자친구를 고를 때 외모, 성격, 재력이 모두 맘에 드는 사람을 고르려고 합니다.
남자가 3명이라면 깊이 우선 탐색은 아래와 같은 탐색을 모두 실행할 것입니다.
하지만 백트래킹은 아래와 같이 마음에 들지 않는 구석이 하나라도 보이면 더이상의 탐색이 필요 없으므로 곧바로 다음 사람으로 넘어갑니다.
백트래킹은 완전탐색인 깊이 우선 탐색에 비해 탐색 횟수가 줄어들기 때문에 더 효율적입니다.
백트래킹을 활용하여 문제를 풀어봅시다.
가. 근손실
https://www.acmicpc.net/problem/18429
하루에 k의 근손실이 일어날 때 n개의 키트를 n일 동안 하루에 하나씩 사용해서 근육량을 높입니다.
처음보다 근육량이 떨어지지 않도록 하는 경우의 수를 구하는 문제입니다.
일단 모든 경우의 수는 n개의 키트를 순서를 고려하여 나열한 경우(순열)이므로, n!가지입니다.
n의 최대값이 8이므로 최악의 경우, 8! = 40,320가지입니다.
1초 안에 충분히 살펴볼 수 있으므로 브루트포스로 풀 수 있습니다.
아이디어는 쉽게 떠올랐지만 n!의 경우를 모두 찾아내는 프로그램을 구현하는 게 쉽지 않습니다.
차근차근 한 단계 씩 접근해봅시다.
n이 3이라면 1, 2, 3을 나열하는 3!의 경우를 모두 찾아봅시다.
먼저 단순하게 3중 for문으로 접근해보면 다음과 같습니다.
for i in range(1, 4):
for j in range(1, 4):
for k in range(1, 4):
print(i, j, k)
# 1 1 1
# 1 1 2
# 1 1 3
# 1 2 1
# 1 2 2
# 1 2 3
# 1 3 1
# 1 3 2
# 1 3 3
# 2 1 1
# 2 1 2
# 2 1 3
# 2 2 1
# 2 2 2
# 2 2 3
# 2 3 1
# 2 3 2
# 2 3 3
# 3 1 1
# 3 1 2
# 3 1 3
# 3 2 1
# 3 2 2
# 3 2 3
# 3 3 1
# 3 3 2
# 3 3 3각 자리에 3까지 숫자가 모두 사용되는 \(3^{3}\) = 27 가지가 나옵니다.
중복 사용되면 안되므로, 조건문을 추가하여 다음과 같이 코드를 수정할 수 있습니다.
for i in range(1, 4):
for j in range(1, 4):
if i == j:
continue
for k in range(1, 4):
if i == k or j == k:
continue
print(i, j, k)
# 1 2 3
# 1 3 2
# 2 1 3
# 2 3 1
# 3 1 2
# 3 2 1드디어 3! = 6 가지를 찾았습니다.
하지만 문제가 있습니다. n이 8이면 8중 for문을 작성해야하고, n이 변하면 그때마다 for문의 깊이를 바꿔줘야하는데 어떻게 가능할까요?
바로 재귀 함수를 사용하면 코드를 간결하게 작성할 수 있습니다.
그럼 먼저 27가지를 찾는 코드를 재귀 함수로 구현해봅시다.
N = 3
def func(li):
if len(li) >= N:
print(*li)
return # else를 사용할 수 있으나 return하면 종료되는 함수의 특징을 사용하면 코드가 더 간결해집니다.
for i in range(1, N+1):
func(li+[i])
func([])
# 1 1 1
# 1 1 2
# 1 1 3
# 1 2 1
# 1 2 2
# 1 2 3
# 1 3 1
# 1 3 2
# 1 3 3
# 2 1 1
# 2 1 2
# 2 1 3
# 2 2 1
# 2 2 2
# 2 2 3
# 2 3 1
# 2 3 2
# 2 3 3
# 3 1 1
# 3 1 2
# 3 1 3
# 3 2 1
# 3 2 2
# 3 2 3
# 3 3 1
# 3 3 2
# 3 3 3재귀 함수의 인자로 이전의 숫자를 담은 배열을 넘겨주면서, 배열의 길이가 n이 되었을 때 종료(종료 조건)하는 재귀함수를 구현했습니다.
그렇다면 중복을 피해서 n! 경우만 찾으려면 어떻게 해야할까요?
이전 숫자들의 배열 안에 있는 숫자들을 피하면 될 것 같습니다.
N = 3
def func(li):
if len(li) >= N:
print(*li)
return
for i in range(1, N+1):
if i not in li:
func(li+[i])
func([])
# 1 2 3
# 1 3 2
# 2 1 3
# 2 3 1
# 3 1 2
# 3 2 1not in 키워드를 사용하여 중복을 피했습니다.
하지만 배열에서 원소를 찾는 방법은 선형 탐색이기 때문에 비효율적이라고 배웠습니다.
대신 집합을 사용하면 O(1) 시간에 찾을 수 있다고 했습니다.
앞서 배열을 넘겨주었으므로 집합도 마찬가지로 해보겠습니다.
N = 3
def func(li, visited):
if len(li) >= N:
print(*li)
return
for i in range(1, N+1):
if i not in visited:
func(li+[i], visited|{i})
func([], set())
# 1 2 3
# 1 3 2
# 2 1 3
# 2 3 1
# 3 1 2
# 3 2 1집합끼리의 합집합 연산에 주의합니다.
이렇게 재귀 함수의 인자로 배열과 집합을 넘겨 n이 변해도 사용할 수 있는 코드를 작성하였습니다.
하지만 배열과 집합을 매번 재귀적으로 넘기면 메모리의 낭비가 심할 것 같습니다.
따라서 배열과 집합을 전역 변수로 바꾸어 관리해봅시다.
N = 3
li = []
visited = set()
def func():
if len(li) >= N:
print(*li)
return
for i in range(1, N+1):
if i not in visited:
li.append(i)
visited.add(i)
func()
li.pop()
visited.remove(i)
func()
# 1 2 3
# 1 3 2
# 2 1 3
# 2 3 1
# 3 1 2
# 3 2 1이 부분이 재귀 함수를 사용하는 백트래킹의 가장 중요한 부분입니다.
자신을 호출하는 시점 이전에 전역 변수를 조정하고, 함수 실행이 끝난 이후에 다시 전역 변수를 원래대로 되돌려 놓습니다.
이를 통해 재귀가 깊어질수록 전역 변수의 변화폭이 커지고, 재귀가 얕아질수록 전역 변수가 서서히 원래대로 돌아옵니다.
이제는 n!의 모든 경우를 구하는 알고리즘을 구현하였습니다.
하지만 굳이 모든 경우를 끝까지 구할 필요는 없었습니다.
왜냐하면 중간에 근육량이 500보다 작아지는 경우 더이상의 탐색은 불필요하므로, 그 상태에서 바로 종료(퇴각)하면 됩니다.
나. 로또
https://www.acmicpc.net/problem/6603
K개의 숫자 집합을 주었을 때, 6개를 뽑는 모든 경우를 찾아 나열하는 문제입니다.
이전 문제가 순열(Permutation)이었다면 이번 문제는 조합(Combination)을 구현하는 문제입니다.
파이썬에서는 순열과 조합을 구해주는 모듈이 있으므로, 가져다 쓰면 단순하게 해결되는 문제입니다.
from itertools import combinations
nums = [1, 2, 3, 5, 8, 13, 21, 34]
print(*combinations(nums, 6), sep="\n")
# (1, 2, 3, 5, 8, 13)
# (1, 2, 3, 5, 8, 21)
# (1, 2, 3, 5, 8, 34)
# (1, 2, 3, 5, 13, 21)
# (1, 2, 3, 5, 13, 34)
# (1, 2, 3, 5, 21, 34)
# (1, 2, 3, 8, 13, 21)
# (1, 2, 3, 8, 13, 34)
# (1, 2, 3, 8, 21, 34)
# (1, 2, 3, 13, 21, 34)
# (1, 2, 5, 8, 13, 21)
# (1, 2, 5, 8, 13, 34)
# (1, 2, 5, 8, 21, 34)
# (1, 2, 5, 13, 21, 34)
# (1, 2, 8, 13, 21, 34)
# (1, 3, 5, 8, 13, 21)
# (1, 3, 5, 8, 13, 34)
# (1, 3, 5, 8, 21, 34)
# (1, 3, 5, 13, 21, 34)
# (1, 3, 8, 13, 21, 34)
# (1, 5, 8, 13, 21, 34)
# (2, 3, 5, 8, 13, 21)
# (2, 3, 5, 8, 13, 34)
# (2, 3, 5, 8, 21, 34)
# (2, 3, 5, 13, 21, 34)
# (2, 3, 8, 13, 21, 34)
# (2, 5, 8, 13, 21, 34)
# (3, 5, 8, 13, 21, 34)하지만 백트래킹 공부 중이므로 재귀를 이용한 백트래킹으로 조합을 구현하여 풀어봅시다.
순열은 순서가 다른 것도 모두 출력해야했으므로 이미 뽑은 것을 visited를 이용해 관리하면서 전체를 반복했지만,
조합은 순서는 고려하지 않으므로 이전에 뽑은 것 이후로만 뽑으면 됩니다.
nums = [1, 2, 3, 5, 8, 13, 21, 34]
limit = 6
li =[]
def dfs():
if len(li) == limit:
print(*[nums[i] for i in li])
return
for i in range(li[-1]+1 if li else 0, len(nums)):
li.append(i)
dfs()
li.pop()
dfs()
# (1, 2, 3, 5, 8, 13)
# (1, 2, 3, 5, 8, 21)
# (1, 2, 3, 5, 8, 34)
# (1, 2, 3, 5, 13, 21)
# (1, 2, 3, 5, 13, 34)
# (1, 2, 3, 5, 21, 34)
# (1, 2, 3, 8, 13, 21)
# (1, 2, 3, 8, 13, 34)
# (1, 2, 3, 8, 21, 34)
# (1, 2, 3, 13, 21, 34)
# (1, 2, 5, 8, 13, 21)
# (1, 2, 5, 8, 13, 34)
# (1, 2, 5, 8, 21, 34)
# (1, 2, 5, 13, 21, 34)
# (1, 2, 8, 13, 21, 34)
# (1, 3, 5, 8, 13, 21)
# (1, 3, 5, 8, 13, 34)
# (1, 3, 5, 8, 21, 34)
# (1, 3, 5, 13, 21, 34)
# (1, 3, 8, 13, 21, 34)
# (1, 5, 8, 13, 21, 34)
# (2, 3, 5, 8, 13, 21)
# (2, 3, 5, 8, 13, 34)
# (2, 3, 5, 8, 21, 34)
# (2, 3, 5, 13, 21, 34)
# (2, 3, 8, 13, 21, 34)
# (2, 5, 8, 13, 21, 34)
# (3, 5, 8, 13, 21, 34)다. 부분수열의 합
https://www.acmicpc.net/problem/1182
수열이 주어질 때, 부분수열의 합이 S가 되는 경우의 수를 찾는 문제입니다.
수열의 길이가 N일 때, 원소마다 더하는 경우와 안 더하는 경우로 나뉘므로 모든 경우의 수는 \(2^{N}\)가지 입니다.
N의 최대값은 20이므로, 최악의 경우에 \(2^{20}\) = 1,048,576가지이니까 주어진 2초 안에 충분히 모든 경우를 살펴볼 수 있습니다.
nums = [-7, -3, -2, 5, 8]
target = 0
cnt = 0 if target else -1 # 0을 만드는 경우는 공집합도 포함되므로 그 경우는 제외시킴.
def dfs(i, s):
if i == len(nums):
if s == target:
global cnt
cnt += 1
return
dfs(i+1, s+nums[i])
dfs(i+1, s)
dfs(0, 0)
print(cnt)
# 1
