Stacks and Queues(6) : Stack and Queue Applications(optional)

Java collections library

• java의 collections라는 라이브러리엔 유용한 툴들이 많이 들어있습니다.
  python에도 같은 이름의 라이브러리가 있어서 코딩테스트 문제를 풀이할 때 종종 사용됩니다.

 

War story (from Assignment 1)

• 과제 1이었던 percolation 문제를 예로 들어서 라이브러리 사용에 충분한 이해가 전제되어야 함을 강조하고 있습니다.
  • n by n 사이즈의 문제를 다룰 때, 이를 배열로 풀이한 사람은 N^2 만큼의 시간이 소요됩니다.
  • 반면 이를 linked list로 풀이하면 N^4의 시간, 즉 제곱만큼의 시간이 소요됩니다.
  • 이는 linked list가 탐색을 수행할 때 배열의 길이 n에 비례하는 시간 복잡도를 가지기 때문입니다.
    즉, 상수(constant)가 아니라 선형(linear) 비례라는 것이죠.
    이 문제는 n by n 이므로 제곱이 되어 차이가 엄청나게 벌어집니다.

 

Stack applications

 

Function calls

 

Arithmetic expression evaluation

• 스택 자료구조를 활용한 예시로 다익스트라의 two-stack algorithm을 배웠습니다.
  원래 스택을 공부할 때 맨 처음 배우는 대표 문제가 괄호인데, 여기서도 괄호 문제입니다.
• 키 포인트는 두 개의 스택을 쓴다는 점입니다.
  value, operator 두 개의 스택을 구분합니다.
• 열린 괄호일 때는 무시하고, 숫자는 모두 value 스택에 추가합니다. 연산자는 operator에 추가하면 되겠죠?
• 닫힌 괄호를 만나면 value 스택에 있는 두 개의 숫자를 꺼내고 operator 한 개를 꺼내어 연산을 수행합니다.
  그리고 그 결과를 다시 value 스택에 집어 넣습니다.
  이를 끝까지 반복하면 됩니다.

 

Dijkstra's two-stack algorithm demo

 

Arithmetic expression evaluation

ops, vals = [], []

for idx in range(len(strs)):
	s = strs[idx]
    if s == '(':
    	continue
    elif s == '+' or s == '*':
    	ops.append(s)
    elif s == ')':
    	op = ops.pop()
        if op == '+':
        	vals.append(vals.pop() + vals.pop())
        elif op == '*':
        	vals.append(vals.pop() * vals.pop())

print(vals.pop())

• two-stack algorithm을 파이썬으로 구현하면 위와 같습니다.
  파이썬은 리스트에 원소를 추가하고 제거하는 것에 큰 제약이 없기 때문에 굳이 stack을 불러오거나 하지 않고 리스트 자료형을 그대로 사용할 수 있다는 특징이 있습니다.
  그냥 pop, append를 사용해도 어차피 맨 마지막의 값을 빼고 더하는 것이라서 상수 시간이 소요되기 때문입니다.

 

Correctness

• 위의 풀이가 왜 타당한지를 생각하는 것은 엄청 간단합니다.
  두 숫자를 꺼내어 연산하고 다시 집어 넣는 것은 사실 괄호를 제거하고 한 숫자만 쓰는 것이랑 동일하기 때문이죠.

 

Stack-based programming languages

 

 

출처: Coursera, Algorithms, Part 1, Princeton University