자료구조 | Permutations, N Queens problem | backtracking

Backtracking

가능성을 탐색하는 알고리즘

candidate가 제거되는 캐이스를 체크한다. 

 

Permutation

겹치지 않는 알파벳이 주어졌을 때

[a, b, c]를 어떻게 순열 계산을 해줄 것인가? 

n!, abc, acb, bac, bca, cab, cba

 

a b c가 주어지면, 세 개의 빈 공간 _ _ _이 생기는 것과 같다. 

첫 자리에는 무엇이 올까? 다음 자리에는? 그 다음 자리에는 무엇이 오게 될까? 

이 부분을 결정해주어야 한다. 

 

a가 온 경우, b, c가 올 수 있다. 

b가 온 경우, a, c가 올 수 있다. 

c가 온 경우, a, b가 올 수 있다. 

 

하나씩 탐색 구조가 만들어진다. 

 

sudo code

def BT(level, letters[])

// 종료 조건
if leve == letters[]:
	output.add(letters[])
    return
    
// 진행 파트
// 후보 중에서 자격이 안 되는 것은 생략한다. 
for i in input array: // 하나의 for loop
	if c in letters:
    	continue
    else:
    	for j in letters:
        	BT(level+1, letters+c)
            
// return 파트

space complexity : O(n)

time complexity : O(n*n!) <= <= O(n^2*n!)

 

swap을 이용하면, 가능성들을 계산 없이 만들어줄 수도 있다. 

a가 선두

b가 선두

c가 선두

를 level에 대하여 반복할 수 있다. 

 

구현

def swap(str, a, b):
    str[a], str[b]
    return str
    
def permutation(level, str):
    str = (list(str))
    if level >= len(str):
        print("".join(str))
        return
    
    else:
        for i in range(level, len(str)):
            str[level], str[i] = str[i], str[level]
            permutation(level+1, str)
    return

permutation(0,'STRI')

 

참고 ) 코딩테스트, 초급, Permutations - YouTube