[수업기록] 알고리즘 : stack(3) - 백트래킹(2)

240809 파이썬반

#일반적 백트캐래킹 알고리즘 수도코드 def checknode (v) : #node
  if promising(v):
    if there is a solution at v:
      wrote the solution
    else:
      for u in each child of v:
        checknode(u)

---

1. 부분집합

1) 개념 : 백트래킹의 대표적 예시

2) 후보군을 정하고, 그 후보 중 하나를 선택한다. 

 

def backtrack(a,k,n) :
	c = [0] *maxcandidates # 주어진 배열 a, 결정할 원소 k, n은 모든 선택의 수(트리의 높이)
    
	if k == n:
    	process_solution(a,k)  #답이면 원하는 작업을 한다
    else:
    ncandidates = construct_candidates(a,k,n,c) #c : 후보 추천 -> 0이나 1
    for i in range(ncandidates):
        a[k] = c[i]
        backtrack(a,k+1,n)
        
        
maxcandidates = 2
nmax = 4
a = [0] *nmax
num=[1,2,3,4]
backtrack(a,0,nmax)
        
        
def construct_candidates(a,k,n,c):
	c[0] = True
    c[1] = False
    return 2

def process_solution(a,k):
	for i in range(k):
    if a[i]:
    	print(num[i], end=' ')
    print()

 

 

2. 순열

1) 개념 : 중복x, 모든 가능한 순서 배열을 생성 ex. [1,2,3] != [1,3,2]

2) 비교예시 

- 단순 순열 생성 : 집합 {1,2,3}에서 모든 순열을 생성하는 함수 

# 동일한 숫자가 포함되지 않았을 때 각 자리수 별로 loop을 이용해 아래와 같이 구현 가능

#1 뒤에 2가 오고 , 3이 오고
#1 뒤에 3이 오고, 2가 오고

for i1 in range(1,4):
#이 부분은 숫자 1, 2, 3 중 하나를 선택합니다. i1은 이 숫자 중 하나를 가지게 됩니다.
	for i2 in range(1,4):
		if i2 != i1:
        	for i3 in range(1,4):
            	if i3 != i1 and i3 != i2:
                	print(i1,i2,i3)
                    
                    
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

백트래킹을 이용하여 순열 구하기

그 중 하나를 고름

# 사용된 적이 없는 애를 찾아요!

def backtrack(a,k,n):
	c = [0] * maxcandidates 
    
    if k ==n :
	    for i in range(0,k):
        	print(a[i], end= " " )
        print()
    else:
    ncandidates = construct_candidates(a,k,n,c)
    for i in range(ncandidates):
    	a[k] = c[i]
        backtrack(a,k+1,n)
        
def construct_candidates(a,k,n,c):
	in_perm = [False] * (nmax+1) #visited 배열
    
    for i in range(k):
    	in_perm[a[i]] = True
        
    n_candidates = 0
    
    for i in range(1,nmax+1):
    	if in_perm[i] == False:
 		#사용된 적 없는 숫자라면       
    		c[n_candidates] = i
        	n_candidates += 1
    return n_candidates
    
    
maxcandidates = 3
nmax = 3
a = [0]*nmax
backtrack(a,0,3)

---

3. 가지치기

1) 개념 : 가지치기(짤라내기)

부분 집합의 합

def f(i,K): #bit[i]를 결정하는 함수
	 if i == K: #모든 원소에 대해 결정하면 
     	s = 0 #부분집합 합 저장
        for j in range(K):
        	if bit[j]: #bit[j]가 0이 아니면
                print(a[j], end = ' ')
                s += a[j]
        print(' : ', s) #부분집합을 한행에 표시
    else:
    	#bit[i] = 1
        #f(i+1, K)
        #bit[i] = 0
        #f(i+1, K)
        for j in [1,0]:
        	bit[i] = j
            f(i+1, K)
        

n = 3
a = [1,2,3] #주어진 원소의 집합
bit = [0]* n #원소의 포함여부 표시 배열

f(0,N) # n개의 원소에 대해 부분집합을 만드는 함수