재귀호출
재귀호출이 두번인 경우의 기본
1
2
3
4
5
6
7
8
9
10
11
12
13
# 완전탐색 / 부분집합의 합
## L은 len이 3인 1차원배열
### n 은 len(L)
def f(n, k):
{
if(n == k):
else:
L[n] = 0
f(n+1, k)
L[n] = 1
f(n+1, k)
}
깊이 = 다뤄야할 배열의 크기
옆으로 = 각 칸을 채울수 있는 숫자의 개수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 주어진 배열의 부분집합
def f(n, k):
if(n == k):
for i in range(k):
if(b[i] == 1):
print(a[i], end =" ")
print()
return
else:
#b[n]에 0을 채우고
b[n] = 0
# 모든 경우의 수를 만들어봐
f(n+1, k)
## b[n]에 1을 채우고
b[n] = 1
## 모든 경우의 수를 만들어봐
f(n+1, k)
k = 3
a = [10, 20, 30]
b = [0]*k # 원소의 포함여부를
f(0, k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def f(n, k, m):
global cnt
if(n == k):
s = 0
for i in range(k): # 부분집합의 합 계산
if(b[i] == 1):
s += a[i]
if(s == m): # 문제에 주어지 조건
cnt += 1
for i in range(k): # 부분집합의 합 계산
if (b[i] == 1):
print(a[i], end=" ")
print()
return
else:
#b[n]에 0을 채우고
b[n] = 0
# 모든 경우의 수를 만들어봐
f(n+1, k,m)
## b[n]에 1을 채우고
b[n] = 1
## 모든 경우의 수를 만들어봐
f(n+1, k,m)
k = 10
m = 10 # 찾고자 하는 부분집합의 합
a = [1,2,3,4,5,6,7,8,9,10]
b = [0]*k # 원소의 포함여부를 나타내는 배열
cnt = 0
f(0, k,m)
print(cnt)
백트래킹(많이 날리기)
1 2 3 4 5 6 7 8 9 10
n = 4 일때
- 1 ~~~4가
고려한 구간(결정된 구간) : 포함여부 결정- 고려한 구간의 합 S일때 고려한 구간에서 합이 X와 같거나 크다면 아직 고려하지 않은 구간에서 어떤 원소를 더해도 안되기 때문에 고려하지 않아도 된다.
- 이 경우 백트래킹
- 고려한 구간의 합이 S일때, 고려한 구간에서 합이 X보다 작을때만 아지 고려하지 않은 구간에서 연산을 고려해야 한다.
- 고려한 구간의 합 S일때 고려한 구간에서 합이 X와 같거나 크다면 아직 고려하지 않은 구간에서 어떤 원소를 더해도 안되기 때문에 고려하지 않아도 된다.
- 5 ~~~10은 아직
고려하지 않은 구간: 포함여부 미결정
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def f(n, k, m, s): # s는 n-1까지(이전에) 포함된 원소의 합
global cnt
global cnt2 # 호출회수
cnt2 += 1
if(s == m):
cnt += 1
elif(n == k): # 한개의 부분집합 완성
return
elif(m < s): # 이부분의 코드가 없다면 재귀 호출의 수가 늘어난다.
## 단 합의 수가 커질수록 효과는 미미하다
### 하지만 재귀호출을 줄이는게 목표 ( 백트래킹 )
#### 그렇다면 합이 수가 커질때는 어떻게 줄일 수 있을까?
return
else:
b[n] = 0
f(n+1, k, m, s) # a[n]이 포함되지 않는 경우
b[n] = 1
f(n+1, k, m, s+a[n]) # a[n]이 포함되는 경우
k = 10
m = 27 # 찾고자 하는 부분집합의 합
a = [1,2,3,4,5,6,7,8,9,10]
b = [0]*k # 원소의 포함여부를 나타내는 배열
cnt = 0
cnt2 = 0
f(0, k,m, 0)
print(cnt, cnt2)
합이 커질 때 줄이기
-
찾고자 하는 합이 m = 50
- 고려구간중 포함된 원소의 합 = s
- 고려하지 않은 구간 = rs
- s + rs < m인 경우가 생긴다 : 남은애들을 다 더해도 m이 안될 경우 제외
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def f(n, k, m, s, rs): # s는 n-1까지(이전에) 포함된 원소의 합
elif(m < s): # 백트래킹을 위한 조건 1
return
elif(s + rs < m): # 백트래킹을 위한 조건 2
## 추가된 코드
### 앞, 뒤 몰려있는 애들 제거해주는걸로 확 줄일수 있음
return
else:
b[n] = 0
f(n+1, k, m, s, rs-a[n]) # a[n]이 포함되지 않는 경우
b[n] = 1
f(n+1, k, m, s+a[n], rs-a[n]) # a[n]이 포함되는 경우
k = 10
m = 27 # 찾고자 하는 부분집합의 합
a = [1,2,3,4,5,6,7,8,9,10]
b = [0]*k # 원소의 포함여부를 나타내는 배열
cnt = 0
cnt2 = 0
f(0, k,m, 0, sum(a))
print(cnt, cnt2)
중복순열
1,2,3을 중복을 이용해 3자리 숫자 만들기
1
2
3
4
5
6
7
8
9
10
11
12
def f(n, k):
if(n == k):
print(p)
else:
for i in range(1, k+1):
p[n] = i
f(n+1, k)
k = 3
p = [0]*k
f(0,k)
1,2,3,4,5중 3개의 숫자를 중복 사용해 3자리 숫자 만들기
1
2
3
4
5
6
7
8
9
10
11
12
def f(n, k, m):
if(n == k):
print(p)
else:
for i in range(1, m+1):
p[n] = i
f(n+1, k, m )
k = 3
m = 5
p = [0]*k
f(0, k, m)
분할 정복 알고리즘
- 분할 / 정복 / 통합으로 나누어 설계
- 대표적인 예 : 퀵 정렬
