[Python] [알고리즘] 4. 스택(2)

계산기

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

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

step 1. 중위 표기법의 수식을 후위 표기법으로 변경한다(stack 이용)

step 2. 후위 표기법의 수식을 스택을 이용하여 계산한다.

 💡 중위 표기법 : 연산자를 피연산자의 가운데 표기하는 방법 예: A+B

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

 

step 1. 중위 표기법에서 후위 표기법으로 변환 알고리즘

1. 입력 받은 중위 표기식에서 토큰을 읽는다.
2. 토큰이 숫자면 토큰을 출력한다.
3. 토큰이 연산자일 때, 토큰이 stack에 저장되어 있는 연산자보다 우선순위가 높으면 stack에 push하고, 그렇지 않다면 스택의 top 연산자의 우선순위가 토큰의 우선순위보다 낮을 때까지 pop한 후 토큰의 연산자를 push한다. 만일 top에 연산자가 없을 경우 push한다.
4. 토큰이 ‘)’이면 스택 top에 ‘(’가 올 때까지 pop연산을 수행하고 pop한 연산자를 출력한다. 왼쪽 괄호를 만나면 pop만 하고 출력하지 않는다.
5. 중위 표기식에 더 읽을 것이 없다면 중지하고, 더 읽을 것이 있다면 1부터 다시 반복한다.
6. 스택에 남아 있는 연산자를 모두 pop하여 출력한다.

• 스택 밖의 ‘(’는 우선 순위가 가장 높으며, 스택 안에서는 우선 순위가 가장 낮다.(왼쪽 괄호 때문에 우선순위 딕셔너리를 두 종류 만들어준다.)

💡 3+4*5에서 우선순위는 *가 +보다 높다. 따라서 스택에 *가 먼저 들어가 있고 + 를 처리해야 한다면 *를 pop해야 하고, + 가 먼저 들어가 있고 *를 처리해야 한다면 *를 그냥 push한다.

step 2. 후위 표기법의 수식을 스택을 이용해서 계산

1. 피연산자를 만나면 스택에 push한다.
2. 연산자를 만나면 필요한 만큼의 피연산자를 pop해서 연산하고, 연산결과를 다시 스택에 push한다.
3. 수식이 종료되면, 마지막으로 pop하여 출력한다.

python
def step1(exp): #후위 표기법으로 바꾸는 함수
    isp = {'+':1, '-':1, '*':2, '/':2, '(':0}
    icp = {'+':1, '-':1, '*':2, '/':2, '(':3}

    Stack = []
    res = []
    for c in exp:
        if c.isdigit():
            res.append(c)
        elif c== ')':
            while Stack and Stack[-1] != '(':
                res.append(Stack.pop())
            Stack.pop()
        else:
            if Stack and isp[Stack[-1]] >icp[c]:
                res.append(Stack.pop())
                Stack.append(c)
            else:
                Stack.append(c)

    while Stack:
        res.append(Stack.pop())
    return res

	def cal(v1,v2,op):
	    if op == '+':
	        return v1+v2
	    elif op =='-':
	        return v1-v2
	    elif op == '*':
	        return v1*v2
	    elif op == '/':
	        return v1//v2
	
	def step2(exp): #후위 표기법을 계산하는 함수
	    Stack = []
	    for c in exp:
	        if c.isdigit():
	            Stack.append(int(c))
	        else:
	            v2 = Stack.pop()
	            v1 = Stack.pop()
	            Stack.append(cal(v1,v2,c))
	    return Stack[-1]
exp = '(6+5*(2-8)/2)'
post = step1(exp)
print(step2(post))

백 트래킹

해를 찾는 도중에 해가 아니면 되돌아가서 다시 해를 찾는 과정이다. 백 트래킹 기법은 최적화 문제와 결정 문제를 해결할 수 있다.

결정 문제: 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes나 no로 답하는 문제

(미로 찾기, n-Queen 문제, Map coloring, 부분 집합의 합 문제 등)

백 트래킹과 DFS의 차이

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 거 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.
• DFS이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기 차단한다.
• 백 트래킹을 사용하면 DFS에 비해 경우의 수가 줄어들기는 하지만 최악의 경우 지수함수 시간을 요하기 때문에 실행 시간이 길어질 수 있다.

백 트래킹은 모든 후보를 검사하는 것이 아니다. 어떤 노드의 유망성을 점검한 후 유망하지 않다고 결정되면 그 노드의 부모로 돌아가 다음 자식 노드로 간다. 어떠한 노드를 방문했을 때 노드를 포함한 경로의 해답이 될 수 없다면 유망하지 않다고 한다. 유망하지 않은 노드가 포함되는 경로는 더 고려하지 않는다.

백 트래킹을 이용한 알고리즘은 다음과 같은 절차로 진행된다.

1. 상태 공간 트리의 DFS를 실시한다.
2. 각 노드가 유망한지를 점검한다.
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속한다.

부분집합 구하기

n개의 원소가 들어있는 집합의 2**n개의 부분집합을 만들 때는 true, 또는 false값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용한다. 여기서 배열의 i번째 항목은 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값이다.

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)
#i2는 i1의 영향을 받고, i3는 i2와 i1의 영향을 받는다.(제한된다)

 

 

#부분집합 만들기

def f(i,k):
    if i==k:
        print(bit)
    else:
        bit[i] = 1
        f(i+1,k)
        bit[i] = 0
        f(i+1, k)


A = {1,2,3}
N = len(A)
bit = [0]*N
f(0,N)
'''
출력
[1, 1, 1]
[1, 1, 0]
[1, 0, 1]
[1, 0, 0]
[0, 1, 1]
[0, 1, 0]
[0, 0, 1]
[0, 0, 0]
'''

 

 

NUMS = [1,2,3]
N = 3
a = [-1]*N #0으로 초기화하면 원소가 포함되지 않은 0인지, 초기화된 0인지 알기 힘들기 때문에 -1로 초기화


def construct_candidates(c):#부분집합의 후보 만들기
    c[0] = 0
    c[1] = 1
    return 2

#모든 부분집합 구하기

def backtrack(a, k): #후보군을 줄인다는 의미로 그냥 백트랙으로 부름. 뒤에서 언급하는 백트랙과는 다르다.
    c = [-1] * 2 #(후보군의 개수에 따라 달라짐)
    if k == N:#끝까지 내려가는 것임.
        print(a)
        return
    nc = construct_candidates(c)
    for i in range(nc):
        a[k] = c[i] #k는 k번째 원소를 결정하고, i는 후보의 인덱스
        backtrack(a, k+1)

backtrack(a,0)
'''
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
'''

 

 

#0 1 2로 순열을 만드는 코드(여기서 순열은 nums의 idx이다. idx를 이용하지 않아(문제에서 요구 X) 관계가 없어보이는 것뿐)
NUMS = [1,2,3]
N = 3
a = [-1]*N #0으로 초기화하면 원소가 포함되지 않은 0인지, 초기화된 0인지 알기 힘들기 때문에 -1로 초기화

def construct_candidates(c,k): #순열의 후보 만들기
    pos = 0
    for i in range(N):
        if i not in a[0:k]:
            c[pos] = i
            pos += 1 #포지션에 넣고 하나 증가시킨 후 좌표에 넣음
    return pos


def backtrack(a, k):
    c = [-1] * N #(후보군의 개수에 따라 달라짐)
    if k == N:#끝까지 내려가는 것
        print(a)
        return
    nc = construct_candidates(c,k)
    for i in range(nc):
        a[k] = c[i] #k는 k번째 원소를 결정하고, i는 후보의 인덱스
        backtrack(a, k+1)

backtrack(a,0)

 

 

#재귀 이용

nums = [1,2,3,4,5,6,7,8,9,10]
N = 10

c = [0,1] #있거나, 없거나 둘 중 하나
def partial(k):
    if k==N:
        print(a, '->', end=' ')
        sumV = 0
        for i in range(N):
            if a[i]:
                sumV += nums[i]
        print(sumV)
        return
#c = [-1]*후보의 개수
#nc = c_c(c)
    for i in range(2):
        a[k] = c[i]
        partial(k+1)


a = [-1]*N #부분집합 리스트(goal의 i번째 데이터)가 들어갈 배열
partial(0)
#k는 실제 데이터의 인덱스가 된다.

 

 

#부분집합 구하기 (재귀 이용)(인덱스 뽑아내기)
nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k):
    if k==N:
        print(a)
        return

    a[k] = 0
    partial(k+1)
    a[k] = 1
    partial(k+1)
    # for i in range(2):
    #     a[k] = c[i]

a = [-1] * N
partial(0)

 

 

#부분집합 다 뽑기 (재귀 이용, 원소를 뽑기)
nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k):
    if k==N:
        for i in range(N):
            if a[i]:
                print(nums[i], end=' ')
        print()
        return

    a[k] = 0
    partial(k+1)
    a[k] = 1
    partial(k+1)

a = [-1] * N
partial(0)

 

 

#전체 부분집합의 합
nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k):
    if k==N:
        sumV = 0
        for i in range(N):
            if a[i]:
                print(nums[i], end=' ')
                sumV += nums[i]
        print('->', sumV)
        return

    a[k] = 0
    partial(k+1)
    a[k] = 1
    partial(k+1)

a = [-1] * N
partial(0)

 

 

nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k, curS):
    if k==N:
        # sumV = 0
        for i in range(N):
            if a[i]:
                print(nums[i], end=' ')
                # sumV += nums[i]
        print('->', curS)
        return

    a[k] = 0 #0일 때는 그냥 내려보내기
    partial(k+1, curS)
    a[k] = 1
    partial(k+1, curS+nums[k]) #1일 때는 nums[k] 합쳐서 구하기

a = [-1] * N
partial(0,0)

 

 

부분집합의 합이 10인 경우만 뽑아내기
nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k, curS):
    if k==N:
        if curS==10:#백트래킹이 아니다. 보이지 않지만 밑에서 잘 돌아간다.
            for i in range(N):
                if a[i]:
                    print(nums[i], end=' ')
            print('->', curS)
        return

    a[k] = 0 #0일 때는 그냥 내려보내기
    partial(k+1, curS)
    a[k] = 1
    partial(k+1, curS+nums[k]) #1일 때는 nums[k] 합쳐서 구하기

a = [-1] * N
partial(0,0)

 

 

nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k, curS):
    if k==N:
        if curS==10:
            print(a)

        return

    a[k] = 0 #0일 때는 그냥 내려보내기
    partial(k+1, curS)
    a[k] = 1
    partial(k+1, curS+nums[k]) #1일 때는 nums[k] 합쳐서 구하기

a = [-1] * N
partial(0,0)
'''
[0, 1, 1, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
를 뽑아내지만 뒤에서는 계속 연산을 수행 중이다.(백트래킹 된 거 X)
'''

 

 

nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k, curS):
    if curS>10:
        return 
    if k==N:
        if curS==10:
            print(a)

        return

    a[k] = 0 #0일 때는 그냥 내려보내기
    partial(k+1, curS)
    a[k] = 1
    partial(k+1, curS+nums[k]) #1일 때는 nums[k] 합쳐서 구하기

a = [-1] * N
partial(0,0)
'''
[0, 1, 0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0] 뽑아낸다. 백트래킹 되었고 부분집합을 뽑아내는 것
'''

 

 

nums = [1,2,3,4,5,6,7,8,9,10]
N = 10
c = [0,1]
def partial(k, curS):
    if curS>10:
        return
    if k==N:
        if curS==10:
            for i in range(N):
                if a[i]:
                    print(nums[i], end=' ')
            print()
        return

    a[k] = 0 #0일 때는 그냥 내려보내기
    partial(k+1, curS)
    a[k] = 1
    partial(k+1, curS+nums[k]) #1일 때는 nums[k] 합쳐서 구하기

a = [-1] * N
partial(0,0)

#백트래킹이 된 것. 백트래킹 후 원소들만 뽑아내기

'''
10 
4 6 
3 7 
2 8 
2 3 5 
1 9 
1 4 5 
1 3 6 
1 2 7 
1 2 3 4
'''