Stack 2

• 스택을 이용한 문자열 수식 계산

문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.

 

중위표기법 : 연산자를 피연산자의 가운데 표기하는 방법

후위표기법 : 연산자를 피연산자 뒤에 표기하는 방법

 

• 중위표기식의 후위표기식 변환 방법 1

수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 묶어준다.

각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동시킨다.

모든 괄호를 제거한다.

 

• 중위 표기법에서 후위 표기법으로의 변환 2 (스택을 이용한 알고리즘)

입력 받은 중위표기식에서 토큰을 읽는다.

토큰이 피연산자면 토큰을 출력한다.

토큰이 연산자(괄호 포함)일 때는 토큰이 스택의 top에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 push하고 그렇지 않으면 top의 우선순위가 토큰보다 작을 때까지 스택에서 pop 한 후 토큰의 연산자를 push 한다. top에 연산자가 없어도 push 한다.

토큰이 닫는 괄호면 스택 top에 여는 괄호가 나올 때까지 pop을 하면서 pop 한 연산자를 출력한다. 여는 괄호는 pop만 하고 출력하지는 않는다.

중위표기식에 더 읽을 것이 없다면 스택에 남아 있는 연산자를 모두 pop 하여 출력한다.

 

스택 안에 있을 때 우선순위와 스택으로 들어오기 전의 우선순위가 다르다. (기억하기!)

여는 괄호는 넣기 전에는 우선순위 수치가 3으로 가장 높지만, 스택 안으로 들어가면 0이 된다.

 

• step 2 : 후위 표기법의 수식을 스택을 이용하여 계산하기

피연산자를 만나면 스택에 push 한다.

연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고(pop 한 순서대로 먼저 꺼낸 숫자를 연산자 뒤에 놓고 계산) 연산결과를 다시 스택에 push 한다.

수식이 끝나면 마지막으로 스택을 pop하여 출력한다.

• 실습 코드

# fx = (6+5*(2-8)/2)

top = -1
stack = [0]*100

icp = {'(':3, '*':2, '/':2, '+':1, '-':1}   # 스택 밖에서의 우선순위
isp = {'(':0, '*':2, '/':2, '+':1, '-':1}   # 스택 안에서의 우선순위

fx = '(6+5*(2-8)/2)'
postfix = ''    # 후위표기식
for tk in fx:
    # 여는 괄호는 무조건 push, 연산자이면서 top 원소보다 우선순위가 높으면 push
    if tk == '(' or (tk in '*/+-' and isp[stack[top]] < icp[tk]):   
    # 수식은 무조건 괄호로 묶여서 제공되기에 스택이 비어있으면 무조건 여는 괄호 나옴
        top += 1    # push
        stack[top] = tk
    elif tk in '*/+-' and isp[stack[top]] >= icp[tk]:
    # 연산자이고 top 원소보다 우선순위가 높지 않으면
        while isp[stack[top]] >= icp[tk]:
            top -= 1
            postfix += stack[top+1]
        # top 원소보다 우선순위가 높을 때까지 pop 한다
        top += 1
        stack[top] = tk     # pop이 다 끝나면 토큰을 push 한다
    elif tk == ')':     # 닫는 괄호면, 여는 괄호 만날 때까지 pop
        while stack[top] != '(':
            top -= 1
            postfix += stack[top+1]
        top -= 1    # 여는 괄호 마저 하나 버려준다
        stack[top+1]
    else:   # 피연산자인 경우
        postfix += tk

print(postfix)

• 백트래킹

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

백트래킹 기법은 최적화 문제와 결정 문제를 해결할 수 있다.

 

결정 문제 → 어떤 방법, 경우, 해가 있니 없니? yes or no! 해법 1가지만 찾아도 됨!

 

최적화 문제 → 어떤 방법, 경우, 해가 있니 없니? 있다면!! 어떠한 조건을 만족하는 해를 찾아라!

그래서 최적화 문제는 최적해를 찾는 문제이기에 보통은 완전탐색을 해야 문제를 풀 수 있다.

그런데 경우의 수를 따지는 과정이 조합과 관련된 경우가 많다보니 완전탐색을 체계적으로, 효율적으로 진행하는 방법을 찾게 되는데, 그 중 하나가 백트래킹인 것이다.

 

• 백트래킹과 깊이 우선탐색(DFS)과의 차이

어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.

DFS는 모든 경로를 추적하지만 백트래킹은 불필요한 경로를 조기에 차단한다.

백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 많은 시간을 요하므로 처리가 불가능하다.

 

• 백트래킹 기법

어떤 노드의 유망성을 점검한 후에 유망하지 않다고 판단되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다.

어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.

가지치기(pruning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.

 

• 상태 공간 트리 : 모든 가능한 경우 (=후보해)를 생성하는 과정을 트리로 나타낸 것

→ 답을 찾는 과정을 설계하기 위해 그린다.

→ 백트래킹은 ‘상태 공간 트리’가 중요하다.

 

백트래킹은 대략 이런 개념이다~

→ 유망한 노드를 남기기 + 안되는 애는 끝까지 안하고 중간에 손절하기

 

• 부분집합

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

 

백트래킹 기법으로 powerset을 만들어 보자.

→ n개의 원소가 들어있는 집합의 2**n개의 부분집합을 만들 때는 n개의 배열을 만드는 방법을 이용한다. 이때 배열의 i 번째 항목은 i 번째의 원소가 부분집합의 값인지 나타내는 값이다.

 

• 부분집합 구하는 코드

def f(i, k):
    if i == k:
        for j in range(k):
            if bit[j]:
                print(arr[j], end=' ')
        print()
    else:
        for j in range(2):
            bit[i] = j
            f(i+1,k)

N = 4
arr = [1, 2, 3, 4]
bit = [0] * N   # bit[i] : arr[i]가 부분집합에 포함되었는지 나타내는 배열
f(0, N)      # bit[i]에 1 또는 0을 채우고, N개의 원소가 결정되면 부분집합을 출력

• 재귀 호출

자기 자신을 내부에서 부르기

재귀 함수 안에서 재귀 호출이 일어남

알고리즘에서 재귀 함수의 사용 → 점화식 구현 (동적 계획법) or 그래프 탐색(DFS 재귀로 구현) or 백트래킹 or 분할 정복 (이진탐색)

결국은 다 ‘반복’이다.

해야할 일이 동일하면 기본적으로 반복하도록 코드를 짜게 됨.

재귀 함수는 그러한 ‘반복’을 특성으로 갖는 함수다.

for 나 while 로 구현하기 까다로울 때 재귀를 활용하면 효율적인 경우가 많다.

i = 0
while i < 3:
    print('hello')
    i += 1

def print_hello(i):  # 재귀 함수로 위 반복을 구현해보기 (3번 hello 출력)
    if i == 3:
        return
    else:   # i < 3, 사실 위에 return 쓰면 else 안 써도 된다
        print(i, 'hello')
        print_hello(i + 1)   # 재귀 함수 반복 종료는 더 이상 재귀호출을 하지 않아야 함
        # 재귀 호출을 언제 멈출 지 어떤 식으로 판단하는가?
        # 보통 매개변수를 통해 판단한다! 이게 정석임
				# 멈추는 기준인 3도 매개변수로 받아서 함수에 넣는 값으로 조정할 수 있다

print_hello(0)

즉, 재귀 호출은 똑같은 코드를 가진 별개의 함수를 실행시킨다고 생각하면 된다.

단, 무한반복을 막기 위해 매개변수를 변화시켜 함수를 호출하여 차별점을 만들어주는 것이다.

i = 0
while i < 3:
    print('hello')
    i += 1

def print_hello(i):  # 재귀 함수로 위 반복을 구현해보기 (3번 hello 출력)
    if i == 3:
        return
    else:   # i < 3, 사실 위에 return 쓰면 else 안 써도 된다
        print(i, 'hello')
        print_hello(i + 1)   # 재귀 함수 반복 종료는 더 이상 재귀호출을 하지 않아야 함
        print(i, 'hello')    # 재귀 호출을 언제 멈출 지 어떤 식으로 판단하는가?
                             # 보통 매개변수를 통해 판단한다! 이게 정석임

print_hello(0)

재밌는 것은 재귀 호출 뒤에 출력 코드를 넣으면 거꾸로 뒤 함수의 출력 코드부터 실행된다는 것이다.

마치 스택에서의 후입선출처럼 뒤에서부터 출력된다.

그래서 스택을 사용하지 않고도 pop을 한 효과를 줄 수 있고 이렇게 재귀 함수로 stack 을 사용한 효과를 낼 수 있어서 재귀 함수로도 DFS를 구현할 수 있는 것!

def print_hello(i):
    if i == 3:
        global count
        count += 1
        return
    else:
        print_hello(i + 1)
        print_hello(i + 1)

count = 0
print_hello(0)
print(count)

함수 안에 재귀 호출이 2번씩 들어간다?

원래 함수에서 count는 1로 출력되지만 재귀 호출이 2번씩 들어가게 되면 3번 반복되는 루프인 경우 23 = 8이 되고 재귀 호출이 3번씩 들어가면 count는 33 = 27이 된다.

그리고 이 과정을 그려보면 결국 DFS와 같다!