2024. 2. 15. 08:39ㆍ알고리즘
- 부분집합 구하기
# 연습) 집합 {1,2,3}의 원소에 대해 각 부분집합에서의 포함 여부를 살피기
def f(i, k):
if i == k: # 모든 원소에 대해 결정하면
ss = 0 # 부분집합 원소의 합
for j in range(k):
if bit[j]: # bit 값이 1이면 = A[i]가 포함된 경우
print(A[j], end=' ')
ss += A[j]
print(ss)
else:
for j in range(1, -1, -1):
bit[i] = j
f(i+1, k)
# bit[i] = 1
# f(i+1, k)
# bit[i] = 0
# f(i+1, k)
N = 3
A = [1, 2, 3]
bit = [0] * N # bit[i]는 A[i]가 부분집합에 포함되는지 표시한다
f(0, N)
# 1 2 3 6
# 1 2 3
# 1 3 4
# 1 1
# 2 3 5
# 2 2
# 3 3
# 0
# {1,2,3,4,5,6,7,8,9,10} 의 부분집합 중 원소의 합이 10인 부분집합을 구하시오.
# for 문을 10번 돌아도 구할 수는 있다...! 하지만 백트래킹으로 구해보자 (=재귀를 이용한 완전탐색)
# 10인 부분집합을 모두 구할 수도 있고 그 중 하나만 구해도 된다!
def f(i, k, t): # k개의 원소를 가진 배열, 합이 t인 부분집합의 경우를 찾기
if i == k: # 모든 원소에 대해 결정하면
ss = 0 # 부분집합 원소의 합
for j in range(k):
if bit[j]: # bit 값이 1이면 = A[i]가 포함된 경우
ss += A[j]
if ss == t:
for j in range(k):
if bit[j]:
print(A[j], end=' ')
print()
else:
for j in range(1, -1, -1):
bit[i] = j
f(i+1, k, t)
# bit[i] = 1
# f(i+1, k)
# bit[i] = 0
# f(i+1, k)
N = 10
t = 10
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
bit = [0] * N # bit[i]는 A[i]가 부분집합에 포함되는지 표시한다
f(0, N, t)
# 1 2 3 4
# 1 2 7
# 1 3 6
# 1 4 5
# 1 9
# 2 3 5
# 2 8
# 3 7
# 4 6
# 10
그런데 위 코드에서 후보군을 만드는 것은 잘 하고 있는데…
모든 경우를 살피면서 가지치기 즉, 유망성 체크가 안되고 있어서 아쉽다!
탐색 하는 과정에서 이미 가망이 없다는 걸 안다면?
즉, 이미 조건을 만족하지 못하는게 확정되면 조기에 쳐내는 유망성 체크를 추가해보자!
def f(i, k, s, t): # k개의 원소를 가진 배열, 합이 t인 부분집합의 경우를 찾기
global count; count += 1
if s == t: # 목표값에 도착하면
for j in range(k):
if bit[j]:
print(A[j], end=' ') # 부분집합 출력
print()
elif i == k: # 모든 원소에 대해 결정했으나 s != t
return
elif s > t: # 고려한 원소의 합이 t보다 큰 경우
return
else:
# for j in range(1, -1, -1):
# bit[i] = j
# f(i+1, k, s+A[i]*j, t)
bit[i] = 1
f(i+1, k, s+A[i], t)
bit[i] = 0
f(i+1, k, s, t)
N = 10
t = 10
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
bit = [0] * N # bit[i]는 A[i]가 부분집합에 포함되는지 표시한다
count = 0
f(0, N, 0, t)
print(f'count :', count)
# 1 2 3 4
# 1 2 7
# 1 3 6
# 1 4 5
# 1 9
# 2 3 5
# 2 8
# 3 7
# 4 6
# 10
# count : 349
이전 코드, 유망성 체크를 추가하기 전에는 count : 2047 이다!
유망성 체크를 하는 경우 함수를 호출하는 횟수가 크게 감소하는 것을 볼 수 있다.
추가로 남은 원소의 합을 다 더해도 찾는 값인 t 미만일 경우 중단하는 것도 고려할 수 있다.
(유망성 체크하는 조건을 추가할 수 있다는 의미)
- 순열
A[1, 2, 3] 의 모든 원소를 사용한 순열
총 6가지
123 132 213 231 312 321
순열은 부분집합과 달리 순서가 중요하고 중복이 안되는 경우 점점 선택의 폭이 줄어든다.
앞에서 안 쓴 원소를 뒤에서 넣는 방법과 처음부터 원소를 나열해놓고 앞 원소와 자리를 바꾸는 방법이 있는데, 뒤 방법으로 코드를 짜보았다.
# 순열을 만들어보자!
def f(i, k):
if i == k:
print(*P)
else:
for j in range(i, k): # P[i]자리에 올 원소 P[j]
P[i], P[j] = P[j], P[i] # P[i] <-> P[j]
f(i + 1, k)
P[i], P[j] = P[j], P[i] # 교환 이전으로 복구
N = 3
P = [1, 2, 3]
f(0, N)
# 1 2 3
# 1 3 2
# 2 1 3
# 2 3 1
# 3 2 1
# 3 1 2
앞 방법으로 순열을 구하면 다음과 같다.
def f(i, k):
if i == k:
print(*new_p)
else:
for j in range(N):
if visited[j] == 1:
continue
new_p.append(P[j])
visited[j] = 1
f(i + 1, k)
new_p.pop()
visited[j] = 0
N = 3
P = [1, 2, 3]
new_p = []
visited = [0 for _ in range(N)]
f(0, N)
# 1 2 3
# 1 3 2
# 2 1 3
# 2 3 1
# 3 1 2
# 3 2 1
- 순열 연습문제
# N * N 배열에 숫자가 들어있는데, 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 한다
# 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다
# p[i] = i 행에서 고른 열
def f(i, k):
global min_v
if i == k:
# print(*P)
s = 0 # 선택한 원소의 합
for j in range(k): # j행에 대해
s += arr[j][P[j]] # j행에서 P[j]열을 고른 경우의 합 구하기
if min_v > s:
min_v = s
else:
for j in range(i, k): # P[i]자리에 올 원소 P[j]
P[i], P[j] = P[j], P[i] # P[i] <-> P[j]
f(i + 1, k)
P[i], P[j] = P[j], P[i] # 교환 이전으로 복구
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
P = [i for i in range(N)]
min_v = 100
f(0, N)
print(min_v)
앞에서와 마찬가지로 백트래킹! 유망성 체크를 추가해보자!
def f(i, k, s): # i-1까지 선택한 원소의 합
global min_v
global count
count += 1
if i == k:
# print(*P)
if min_v > s:
min_v = s
elif s >= min_v:
return
else:
for j in range(i, k): # P[i]자리에 올 원소 P[j]
P[i], P[j] = P[j], P[i] # P[i] <-> P[j]
f(i + 1, k, s+arr[i][P[i]])
P[i], P[j] = P[j], P[i] # 교환 이전으로 복구
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
P = [i for i in range(N)]
min_v = 100
count = 0
s = 0
f(0, N, s)
print(min_v, count)
유망성 체크 전에는 count = 326 였지만, 181로 줄었다.
값이 크면 클수록 줄어드는 효과도 커진다.
물론 최악의 경우에는 가지치기를 해도 경우를 많이 돌 수 있긴 하다…
원래는 재귀 호출을 하면 함수 스택이 쌓이기 때문에 단순한 문제에서는 그냥 반복문 돌리는게 빠르다.
하지만 문제에서 부분집합의 합을 따지는 것처럼 유망성 체크가 가능한 조건이 있다면,
그 조건을 갖고 가지치기를 할 수 있는 재귀 호출 방법이 더 효율적이게 된다!
- 상태 공간 트리와 부분집합 구하기
상태 공간 트리가 선택의 과정이 된다.
무엇을 선택? → 각 원소의 부분집합 포함 여부!
ex) { a, b, c } 에서 원소의 수 (= 3) 만큼 선택을 하면 하나의 부분집합이 생성되는 것
원소의 수 = 선택해야 하는 횟수 = 트리의 높이 = 함수 처리 횟수 (시작한 후 return 조건을 만족할 때까지)
선택마다 고를 수 있는 옵션 = 부분집합 문제일 경우는 2개 ( 포함 / 미포함 ) = 함수 내에서 재귀 호출하는 횟수 = 트리에서 갈라지는 가지 수
- 순열 연습
arr = ['A', 'B', 'C', 'D']
N = len(arr)
for i in range(0, N):
arr[0], arr[i] = arr[i], arr[0] # 자리 바꾸기
for j in range(1, N):
arr[1], arr[i] = arr[i], arr[1]
print(arr)
arr[1], arr[i] = arr[i], arr[1]
arr[0], arr[i] = arr[i], arr[0] # 다음 바꾸기 반복을 위해서 다시 원상 복구
# for 반복문 형태를 재귀 호출을 사용하여 똑같은 원리로 구현할 수 있다.
def perm(k):
if k == N:
print(*arr)
return
for i in range(k, N):
arr[k], arr[i] = arr[i], arr[k]
# 재귀 호출
perm(k + 1)
arr[k], arr[i] = arr[i], arr[k]
perm(0)