[TIL: 0215] 백트래킹, 부분집합, 순열

계산기

문자열 수식 계산의 일반적 방법

중위 표기법 수식을 후위표기법으로 변경 (스택 이용)
후위 표기법의 수식을 스택 이용해 계산

중위표현식

일반적으로 알고있는 산술 방식

연산자를 피연산자의 가운데 표기하는 방법 (A+B)
일반적으로 알고있는 산술 방식

Stack 내부와 외부의 연산자 우선순위

중위 표현식으로 된 식을 순회할 것
1. 순회되는 원소는 "토큰"
2. 토큰을 담을 빈 스택을 만든다
3. 토큰이 연산자인 경우

• 스택이 비어있을 경우 스택에 push
  - 스택에 들어올 토큰이 (면 스택에 push
• 스택에 들어올 토큰 > 스택 top 에 존재하는 토큰의 isp
  - push
  • 스택에 들어올 토큰 <= 스택 top에 존재하는 토큰의 isp
    • 2번이 만족할 때까지 스택에서 pop 결과에 push
      • 2번이 만족하면 스택으로 들어오는 토큰을 스택에 push
  • 스택에 들어올 토큰이 )면
    • (를 만날 때까지 스택에서 pop 한 토큰을 결과에 push
      (는 결과에 push 하지 않고 pop만

4. 순회를 마치마녀 스택이 비어있을 때까지
   • 스택에서 pop한 토큰을 결과에 push

후위표현식

연산자를 피연산자 뒤에 표기하는 방법 AB+

• 컴퓨터가 이해하는 산술 방식으로 변경
• 속도가 올라간다
• stack 내부와 외부의 연산자 우선순위

*닫는 괄호가 나오면 중요
여는괄호를 만날 때까지 다 꺼냄

곱셈 우선순위 2, 나눗셈의 우선순위도 2
높으면 push
내가 스택에서 낮은애보다 위에 와야한다
나보다 낮지 않은(같거나 높은 연산자)는 나가라

후위표기법

백트래킹

해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아 가는 기법이다

• 최적화 문제와 결정 문제를 해결할 수 있다
• 결정 문제
  문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes', 또는 'no'가 답하는 문제

백트래킹과 깊이우선탐색과의 차이

• 깊이우선탐색이 모든 경로를 추적하는 것에 비해 백트래킹은 불필요한 경로를 조기에 차단 (가지치기)
• 깊이우선탐색 하기에는 경우의 수가 너무나 많다 N! 가지 경우 수 가진 문제에 대해서는 처리 불가
• 백트래킹 적용하면 경우의 수 줄어들지만 최악의 경우에는 여전히 지수함수 시간 요하므로 처리 불가능

백트래킹은 모든 후보를 검사하지 않는다
노드의 유망성을 점검한 후 유망하지 않다고 결정되면 노드 부모로 되돌아가 다음 자식 노드로 간다
가지치기: 유망하지 않은 노드가 포함되는 경로는 더 이상 고민하지 않는다

일반 백트래킹 알고리즘

def checknode(V) : # node
	if promising(V):
    	if there is a solution at v:
        	write the solution
        else:
        	for u in each child of v:
            	checkvode(v)

부분집합 구하기

백트래킹 기법으로 powerset(공집합과 자기 자신을 포함한 모든 부분집합) 구하기

def backtrack(a, k, input):
    global MAXCANDIDATES
    c = [0] * MAXCANDIDATES
    
    if k == input: # 다 채웠을 때
        process_solution(a, k) # 답이면 원하는 작업을 한다
    else:
        k += 1
        # 추려낸 후보군 추천
        # ncandidates는 후보들 (1, 2)
        ncandidates = construct_candidates(a, k, input, c)
        # 후보를 차례대로 적용해라
        for i in range(ncandidates):
            a[k] = c[i]
            # 위에서 k + 1 되어있으니까 다음 후보 찾으러 가라
            backtrack(a, k, input)

# 후보군 추려서 추천
def construct_candidates(a, k, input, c):
	c[0] = True # 포함되거나
    c[1] = False # 포함되지 않거나
    return 2 # 두 개 원소 리턴할테니 가져다 써라
    
MAXCANDIDATES = 2
NMAX = 4
a = [0] * NMAX
backtrack(a, 0, 3)

순열

단순하게 순열생성하는 방법

• 예) {1, 2, 3}을 포함하는 모든 순열 생성 함수
  동일한 숫자 포함되지 않을 때, 각 자리 수 별로 loop 이용

for i1 in range(1, 4):
	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)

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

def backtrack(a, k, input):
	global MAXCANDIDATES
    c = [0] * MAXCANDIDATES
    
    if k == input:
    	for i in range(1, k + 1):
        	print(a[i], end=" ")
        print()
    else:
    	k += 1
        # 후보 추천해줘 > 사용할 수 있는 후보 개수 몇 개야
        ncandidates = construct_candidates(a, k, input):
        # 그 후보를 하나씩 넣어볼게
        for i in range(ncandidates):
        	a[k] = c[i]
            # 그 다음 결정
            backtrack(a, k, input)

부분집합 구하는 방법과 유사

# 재귀로 할 경우
# 후보군을 추천하기 위해서는 앞에서 사용된 숫자는 제외
def construct_candidates(a, k, input, c):
	# 사용한 요소를 파악
	in_perm = [False] * NMAX
    
    # 앞에서 사용한 숫자 파악
    for i in range(1, k):
    # a[i]는 원래 주어짐
    # 앞에서 사용한 요소를 True 라고 표기
    	in_perm[a[i]] = True
        
    ncandidates = 0
    for i in range(1, input + 1):
    	# 아직까지 사용되지 않은 애들을
    	if in_perm[i] == False:
        	# c라는 후보 그룹에 추천
        	c[ncandidates] = i
            ncandidates += 1
    return ncandidates