후위 표기법

• 우리가 하는 산수방식(중위 표기법)은 컴퓨터가 이해하는 방식이 아님

• 중위 표현식

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

• 후위 표현식

  • 왜? 컴퓨터가 이해하는 산술 방식으로 변경해주기 위해
    • 계산 속도가 올라감
  • 연산자가 피연산자 뒤에 온다.
  • 스택 내부와 외부의 연산자 우선순위

토큰	isp (stack top, 내부) 비교대상	icp (자신, 외부)
)	-	-
*,/	2	2
+,-	1	1
(	0	3

1. 중위 표현식으로 된 식을 순회할 것

   • 순회되는 원소를 "토큰"

2. 토큰을 담을 빈 스택을 만든다.

3. 토큰이 연산자인 경우

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

4. 순회를 마치면 스택이 비어있을 때까지

   1. 스택에서 pop한 토큰을 결과에 push

코드로 구현 해보기

infix = '(6 + 5 * ( 2 - 8 ) / 2 )'

stack = []
result = ''

#변환할 식을 순회
for token in infix:
    # 토큰이 피연산자인 경우
    if token.isdecimal():
        result += token

    # 토큰이 연산자인 경우
    else:
        # 스택이 비어있는 경우, 스택에 push
        if not stack:
            stack.append(token)
        else:
            # (는 incoming 우선순위가 가장 높음
            if token == '(':
                stack.append(token)
            # )는 (가 나올때까지 스택에서 pop, result에 append
            elif token == ')':
                while stack[-1] != '(':
                    result += stack.pop()
                stack.pop()
    
            # incoming 우선순위기 2인 걍우
            elif token == '*' or token == '/':
                # 스택의 top의 토큰이 우선순위가 낮을 때까지 스택에서 pop, result append
                while stack and stack[-1] == '*' or stack[-1] == '/':
                    result += stack.pop()
                stack.append(token)

            # incoming 우선순위기 1인 걍우
            elif token == '+' or token == '-':
                # 스택의 top의 토큰이 우선순위가 낮을 때까지 스택에서 pop, result append
                # (가 아닌 경우 모두 동치
                while stack and stack[-1] != '(':
                    result += stack.pop()
                stack.append(token)
                
while stack:
    result += stack.pop()
print(result) #6528-*2/+

# 계산하기

# 피연산자
    # 스택에 push
# 연산자
    # 스택에 담겨잇는 2개의 토큰을 pop 후 연산 후 stack에 push

백트래킹

• 백트래킹 기법은 해를 찾는 도중에 '막히면' (해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법
• 백트래킹 기법은 최적화 문제와 결정 문제를 해결할 수 있음
• 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes 또는 no가 답하는 문제
  • 미로찾기
  • n-Queen문제
  • Map coloring
  • 부분 집합의 합 문제 등

미로찾기 알고리즘

• 스택에 지나온 경로들을 push
• 스택을 이용하여 지나온 경로를 역으로 되돌아 간다
• 스택을 이용해서 다시 경로를 찾음

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

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도 횟수를 줄임
• 깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기 차단
• 깊이우선탐색을 가하기에는 경우의 수가 너무나 많음
• 백트래킹 알고리즘을 적용하면 일반적으로 경우의 숙 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간을 요하므로 처리 불가능

백트래킹 기법

• 어떤 노드의 유망성을 점검한 후에 윰ㅇ하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감
• 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
• 가지치기 (pruning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다

백트래킹 알고리즘 절차
1. 상태 공간 트리의 깊이 우선 검색을 실시
2. 각 노드가 유망한지를 점검
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

부분집합 구하기

• 어떤 집합의 공집합과 자기 자신을 포함한 모든 부분집합을 powerset이라고 하며 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n개 이다

• 백트래킹 기법으로 powerset 구하기

  • 앞에서 설명한 일반적인 백트래킹 접근 방법을 이용
  • n개의 원소가 들어있는 집합의 2^n개의 부분집합을 만들 때는, true 또는 False값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용
  • 여기서 배열의 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값

def backtrack(a, k, input) :
	global MAXCANDIDATEDS
    c = [0] * MAXCANDIDATES
    
    if k == input : 
    	process_solution(a,k) # 답이면 원하는 작없을 한다 
    else:
    	k+=1
        ncandidates = constrict_candidates(a,k,input,c)
        for i in range(ncandidates) :
        	a[k] = c[i]
            backtrack(a,k,input)
            
def constrict_candidates(a,k,input,c) :
	c[0] = True
    c[1] = False
    return 2
MAXCANDIDATES = 2 
NMAX = 4
a = [0] * NMAX
backtrack(a,0,3)
    

순열

def f(i,k):
if i == k :
	print(p)
else:
	for j in range(i,K):
    	p[i], p[j] = p[j], p[i]
        f(i+1, k)

p = [1,2,3]
N = len(p)
f(i, N)

퀵정렬

• 주어진 배열을 두개로 분할하고, 각각을 정렬한다
  • pivot item을 기준으로 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다
  • 보통 (begin + end) // 2 인덱스를 pivot으로 설정 (but 뭐든 상관없음)
• 이미 어느정도 정렬이 되어 있으면 시간복잡도가 좋지 못하다

알고리즘

def quicksort(a, begin, end) :
	if begin < end :
    	p = partition(a, begin, end)
        quicksort(a, begin, p-1)
        quicksort(a, p+1, end)