Python : Stack (1)

이제 시작이다.. 여기서 부터는 알면 알수록 많은 풀이법을 생각 해낼 수 있고, 시뮬레이션이나 시간 복잡도를 개선하는 방식들이 있기 때문에 알고리즘 문제를 푸는데 실질적으로 도움이 많이 될 형태들이다. 가보자고.

---

스택 (=Stack)

: 데이터를 후입 선출 구조 (LIFO : Last In, First Out 구조)이며 가장 최근에 들어온 데이터가 가장 먼저 빠진다는 개념이다. 실생활 예시로는 설거지한 컵들을 정리할 때, 가장 위에 있는 컵이 가장 먼저 사용될 것이고, 마지막 맨 아래의 컵은 마지막에 사용된다고 생각하면 좋을 것 같다.

• 스택에 저장된 데이터들은 선형 구조(데이터 간의 관계가 1대1 관계)의 특성을 띄고있다
• 스택에 데이터를 삽입하거나 스택에서 데이터를 빼낼 수 있다

Stack을 넣을때는 1-2-3-4-5-6(push)                                                         (pop)Stack에서 빼낼때는 6-5-4-3-2-1

 

스택을 프로그램에서 사용하기 위해서는 자료구조와 연산이 필요하다.

 

자료구조

: 자료를 선형으로 저장할 저장소

- 배열을 사용할 수 있다

- 저장소 자체를 스택이라고도 한다

- 스택에서 가장 마지막에 삽입된 데이터의 위치를 'top' 이라 부른다

 

연산

- 삽입 : 저장소에 데이터를 저장한다. 보통 push라고 불리며 파이썬 list에서는 append() 함수를 사용한다.

- 삭제 : 저장소에서 데이터를 꺼낸다. 꺼낸 데이터는 삽입한 자료의 역순으로 꺼내며 보통 pop이라고 불리며 함수역시                     pop() 을 사용한다.

- 스택 내부가 비어있는지 확인하는 연산은 isEmpty. 파이썬에서는 len(stack)으로 내부 데이터 유무를 확인할 수 있다.

- 스택의 top에 있는 데이터를 반환하는 연산은 peak. 파이썬에서는 pop()을 사용하면 자동적으로 peak를 연산한다.

 

비어있는 스택에 데이터 A, B, C를 차례로 3번 삽입 후에 한번 삭제하는 과정을 그림으로 표현했다

 

파이썬 형식으로 바꿔서 나타내 보겠다.

5칸을 나눠서 표현했지만, 파이썬은 짱짱 좋은 가변 list기 때문에 stack 크기를 정하지 않아도 괜찮다

 

파이썬으로 구현하면 아래와 같다. 파이썬은 이보다 더 간결하게 가능하지만 굳이 전개한 이유는, 곧 나올 DP, DFS 때문에 큰 틀을 연습해두는 것이 좋다고 생각한다. 다음 시간만 되어도 무슨 뜻인지 이해할 수 있다.

def push(data, size):

    global top

    top += 1

    if top == size:

        print('overflow')

    else:

        stack[top] = data

def pop(stack,top):

    if len(stack) == 0:

        # underflow : 리스트가 비어있을때 오류를 피하기 위함

        return

    else:

        top -= 1

        stack.append(0)             # 스택 size 유지

        return stack.pop(top+1) # + 1은 인덱스 보정

   

size = 10                  # 스택 사이즈

stack = [0] * size      # 파이썬에서는 최적화가 아닌이상 필요한 부분은 아님

top = -1                    # top의 초기 위치

push('A', size)         # data와 size를 인자로 넣어준다

top += 1                  # 스택에 데이터가 쌓일때마다 마지막 삽입된 데이터 위치 증가

stack[top] = 'B'        # push('B')

push('C', size)

pop(stack,top)        # top에 있는 데이터 삭제

print(stack)             # ['A', 'B', 0, 0, 0, 0, 0, 0, 0, 0]

print(top)                # top의 위치 2

 

굉장히 지저분해졌는데, 아래의 코드가 일반적으로 파이썬에서 사용하는 코드라고 생각된다.

def push(data, stack):              # 가변형인 리스트에서는 push로 인한 overflow 조건은 필요없다

    stack.append(data)              # 데이터를 자동으로 스택의 top 부분에 추가

    return print(stack)                # 스택 출력(보기위함)

def pop(stack):

    if len(stack) == 0:                 # 비어있는데 pop을 했을경우 오류 발생하므로 조건 추가

        return print('underflow')

    else:

        return print(stack.pop())   # 스택의 top부분을 삭제

   

stack = []

                         # push된 데이터 출력

push(1, stack)  # [1]

push(2, stack)  # [1, 2]

push(3, stack)  # [1, 2, 3]

                       # pop된 데이터 출력

pop(stack)      # 3

print(stack)     # [1, 2]

pop(stack)      # 2

print(stack)     # [1]

pop(stack)      # 1

print(stack)     # [ ]

 

 

원래 Stack에서 고려해야할 사항이 있다. 앞서 한번 설명 했는데, 스택의 크기를 변경하기 어렵다라는 단점은 파이썬에서는 동적 list를 사용하기 때문에 크게 상관없다!

---

Stack의 응용

처음 배운다면 스택을 어떻게 써야하는지 감이 안잡힐텐데 굉장히 유용하게 사용할 수 있다. 대표 유형인 괄호검사를 통해 알아보도록 하자. 백준에 괄호만 검색해도 다양한 난이도로 접할 수 있다. https://www.acmicpc.net/problem/9012가 가장 일반적인 유형이라고 생각한다.

기본 조건을 먼저 알고가보자. 괄호의 종류는 총 3가지로

[   ]  : 대괄호

{   }  : 중괄호

(   )  : 소괄호 가 있으며

우선순위는 기본적으로 소괄호( ) - 중괄호{ } - 대괄호[ ] 순이다

문제는 주로 괄호를 사용했을때 문제가 있는 계산식인지 아닌지를 판단하는 것이다.

예를들어 (a(b), a{b(c[d]e}f) 등 괄호가 완전한 짝을 이루지 않거나, 괄호끼리 닫히는 순서가 알맞지 않을 경우 등이 있다. 이러한 경우에 stack을 사용하여 열린 괄호가 나온다면 스택에 담아두었다가 짝이 맞는 닫는 괄호가 나올때를 판단하여 문제를 해결할 수 있다.

• 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 Stack에 삽입하고, 오른쪽 괄호를 만나면 Stack에서 'top부분=stack[-1]' 을 삭제 및 꺼낸 후 오른쪽 괄호와 짝이 맞는지 검사한다.
• 이때 빼려한 스택이 비어있다면(왼쪽 짝이 없다면) 조건에 위배되고 다른 짝이 나오거나 방향이 다르다면 또한 조건에 위배된다.
• 마지막까지 문자열을 조사 했는데, 모두 사라졌어야 할 Stack에 데이터가 남아있다면 짝이 맞지 않는다는 의미로 조건에 위배된다.

judge_data = input()

stack = []

for i in judge_data:

    if i == "{" or i == "(" or i == '[':            # 좌측 괄호 데이터를 받으면 조건에 상관 없이 stack에 push

        stack.append(i)                             # 괄호에 조건을 확인하여 짝이 맞다면 해당 요소 pop.

    elif stack and i == "}" and stack[-1] == "{":   # stack이 비어있지 않고, top의 요소와 짝이 맞는지 확인  

        stack.pop()

    elif stack and i == ")" and stack[-1] == "(":   # stack이 비어있지 않고, top의 요소와 짝이 맞는지 확인

        stack.pop()

    elif stack and i == "]" and stack[-1] == "[":   # stack이 비어있지 않고, top의 요소와 짝이 맞는지 확인

        stack.pop()

    elif i == "}" or i == ")" or i == ']':          # 만약 stack이 비어있고 i가 닫힌 괄호일때도 push한다

                                                              # 또한 괄호의 순서가 잘못되어도 stack에 쌓이게 되는 것을 볼 수 있다.

        stack.append(i)                             # 잘못된 식인것을 출력하기 위함이며

                                                              # 짝이 맞지 않기 때문에 스택에 끝까지 남아있는다.

if stack:

    answer = 'Fail'                                   # 스택에 데이터가 남아있다면 짝이 맞지 않다는 뜻이므로 Fail

else:

    answer = 'Success'                           # 문제가 없다면 Success

print(answer)

 

[ { ( ) } ] 이 주어졌을 때의 그림

[ { } ( ) ) 이 주어졌을 때의 그림

---

더 나아가 중위 계산식에서 후위 계산식으로 변환 및 계산할 때도 사용할 수 있다.

갑자기 중위 계산식 후위 계산식이 왜 튀어나오냐? 그것이 공부니까..

• 중위 표기법 (infix notation) : 연산자를 피연산자 가운데 표기하는 방법 
• 후위 표기법 (postfix notation) : 연산자를 피 연산자 뒤에 표기하는 방법

흔히 우리가 아는 표기법은 중위 표기법이다. 근데 굳이 이걸 왜 하는가 싶지만, 컴퓨터는 천재라서 연산자를 피연산자 뒤에 표기한다. 진지하게는 컴퓨터 계산기는 피연산자와 연산자로 나뉘어 계산을 하기 때문이다. 놀랍지만 전위 표기법도 있지만 크게 다루진 않았다.

사실 ' + ', ' - ', ' * ', ' / ' 만 있으면 쉽겠지만, 여기서부터는 괄호도 출연하게 된다. 

텍스트로 단계를 보여주자면

ex ) A * B - C / D

이질감이 드는 식이 완성되었다.

이번엔 다른 예시로 코드를 살펴보자

 

text = '(1+(1+3)*4/5)'

# 스택을 사용한 후위식으로 표현 바꾸기

stack = [ ] # append(x) / pop()

result = ' ' # 후위식을 넣을 result 변수 설정

# 스택의 상태가 항상 내가 넣으려고 하는 연산자가

# 기존에 있었던 연산자보다 우선순위가 높도록 유지

# 중위식을 순회하면서 후위식을 만들어야한다.

for ch in text:

    # 1. 숫자가 나오면 그대로 출력

    if ch.isdigit():

        result += ch

    # 2. '(' 여는 괄호가 나오면

    elif ch == '(':

        # ( 여는 괄호를 스택에 push한다

        stack.append(ch)

    # 3. '*' '/' 나오면

    elif ch == '*' or ch == '/':

        # 스택에 들어있는 값이 * or / 연산자라면

        # 들어있던 연산자를 먼저 빼준다

        if len(stack) > 0 and (stack[-1] == '*' or stack[-1] == '/'):

            result += stack.pop()

        stack.append(ch)

    # 4. '+' '-' 나오면

    elif ch == '+' or ch == '-':

        # 스택내에 나보다 높은 우선순위가 바로 아래에 없게끔 만들어야 한다.

        # 우선순위가 나보다 아래인 경우를 먼저보면 스택이 비어있거나 여는괄호가있다면 그냥 append

        # 위의 조건을 만족하기 위해 여는 괄호가 나오거나 스택이 아에 비울때까지 pop을 반복 먼저해야한다

        while len(stack) > 0 and stack[-1] != '(':

            result += stack.pop()

        stack.append(ch)

    # 5. ')' 닫는 괄호가 나오면

    elif ch == ')':

        # '(' 여는 괄확 나올 때까지 pop해라

        while stack[-1] != '(':

            result += stack.pop()

        stack.pop()     # while 다 돌고 '(' 까지 제거해준다

# 순회가 끝난 후, stack의 내용을 모두 pop 해준다.

while len(stack) > 0:

    result += stack.pop()

print(result)

 

 

위의 식 말고도 여러가지 방법이 있다. 예를들어 우선순위를 적용한 알고리즘으로 operation에 대한 정보를 딕셔너리에 우선순위로 저장하고 연산자가 나올때 stack에 쌓여있는 연산을 쏟아내는 방식이 있다. 

 

1. 입력 받은 중위 표기식에서 데이터를 순차적으로 읽는다.
2. 데이터가 피연산자면 데이터를 바로 출력(저장)한다
3. 데이터가 연산자(괄호포함)일 때, 해당 데이터가 스택에 저장되어있는 top 연산자보다 우선순위가 높으면 스택에 push. 그렇지 않다면 top의 연산자가 우선순위가 높은 데이터의 우선순위보다 작아질 때까지 스택에서 pop한 후(+출력저장)에 데이터의 연산자를 스택에 push한다. 만약 스택에 데이터가 없다면 push한다.
4. 데이터가 오른쪽 괄호 ' ) '이면 스택에 top 부분에 왼쪽 괄호 ' ( '가 올 때까지 스택에 pop 연산을 실행하고, 출력 저장한다. 왼쪽 괄호를 만난다면 pop만 하고 출력은 진행하지 않는다.
5. 중위 표기식의 끝까지 도달했다면 종료한다.
6. 스택에 남아있는 연산자를 모두 pop하고 출력저장을 한다.

 

text = '(1+(1+3)*4/5)'

stack = []

result = ''

icp = {'*' : 2,

       '/' : 2,

       '+' : 1,

       '-' : 1,

       '(' : 3} # 입력될 때의 연산자 우선순위

isp = {'*' : 2,

       '/' : 2,

       '+' : 1,

       '-' : 1,

       '(' : 0} # 스택 내에 있을 때의 연산자 우선순위

for ch in text:

    # 1. 숫자(피연산자)가 나오면 그대로 출력

    if ch.isdigit():

        result += ch

    # 2. 연산자 * / + - ( 포함이 된다면

    if ch in ['*','/','+','-','(']:

        # - 입력된 연산자가 > 스택 맨 위의 연산자보다 우선순위

        if len(stack) == 0 or icp[ch] > isp[stack[-1]]:

            stack.append(ch)

        # - 입력된 연산자가 <= 스택 맨 위의 연산자보다 우선순위

        else:

            while len(stack) > 0 and icp[ch] <= isp[stack[-1]]:

                result += stack.pop()

            stack.append(ch)

    elif ch == ')':

        # '(' 여는 괄확 나올 때까지 pop해라

        while stack[-1] != '(':

            result += stack.pop()

        stack.pop()     # while 다 돌고 '(' 까지 제거해준다

# 순회가 끝난 후, stack의 내용을 모두 pop 해준다.

while len(stack) > 0:

    result += stack.pop()

print(result)            

 

 딕셔너리에 계산식을 넣는 방법인 lambda 식을 적용하여 코드의 길이를 완전히 줄여버리는 case

 

# 연산자들을 딕셔너리에 람다식을 통해 간결하게 표현 가능

text = '(1+(1+3)*4/5)'

oper = { # 연산자 - 람다식을 key-value로 매칭

    '*' : lambda a, b : a * b,

    '/' : lambda a, b : a // b,

    '+' : lambda a, b : a + b,

    '-' : lambda a, b : a - b

}

stack = []

for ch in text:

    # 피연산자를 스택에 넣고

    if ch.isdigit():

        stack.append(ch)

    # 연산자를 만나면 피연산자를 두개 빼서 연산한다. 그 결과를 다시 스택에 넣는다.

    else:   # 피연산자 제외한 연산자 모두

        b = int(stack.pop())

        a = int(stack.pop())

        temp = oper[ch](a,b)

        stack.append(temp)

    # 순회가 다 돌고나면 stack에는 결과만 남게된다

result = stack.pop()

print(result)

 

 

사실 lambda는 아직 제대로 다룰 줄 몰라서 정말 간단한 것 아닌 이상은 자주 쓰진 않는다. 실제로 시간복잡도에는 크게 상관이 없다고 알고있고, 쉬운 식이 아닌 이상 직관적이진 않아서 자주 쓰진 않다보니 더 안쓰게 되는거 같다.

---

후위 계산식으로 바꾸었다면 해당 연산을 진행도 해봐야 하지 않겠는가? 다행히 중위에서 후위를 바꾸는 것보다 훨씬 간단하다. 

이번에는 피연산자를 스택에 넣고 연산자를 만나게 된다면 피연산자 데이터 2개를 꺼내어 연산 후에 다시 스택에 넣어준다. 여기서 주의할 점은 pop을 두번 진행할 때, 데이터의 순서에 따라 출력이 달라질 수 있음에 주의하자. 예를들어 a-b 혹은 a/b 해야하는 연산에서 b-a 와 b/a로 잘못 계산되어 틀리는 경우가 종종있다. 나도 백준풀 때 그랬다.

 

 

text = '113+4*5/+'

stack = []

for ch in text:

    # 피연산자를 스택에 넣고

    if ch.isdigit():

        stack.append(ch)

    # 연산자를 만나면 피연산자를 두개 빼서 연산한다. 그 결과를 다시 스택에 넣는다.

    else:   # 피연산자 제외한 연산자 모두

        b = int(stack.pop())

        a = int(stack.pop())

        if ch == '*':

            stack.append(a*b)

        elif ch == '/':

            stack.append(a//b)

        elif ch == '+':

            stack.append(a+b)

        elif ch == '-':

            stack.append(a-b)

    # 순회가 다 돌고나면 stack에는 결과만 남게된다

result = stack.pop()

print(result)

 

---

여기까지는 아직 stack을 이용한 순한맛 응용이다. 다음 시간에 배울 Backtracking, 부분집합, 순열 등이 있는데.. 벌써 한숨나온다. 아자아자 화이자...