(자료구조)순차적 자료구조/스택과 큐 - postfix 계산기와 첫 증발

---

C언어에서 배열(Array)과 Python에서 List의 차이.

자료구조 - 신찬수 교수님

+ 파이썬 리스트 내부 구조 - seoyeon hwang님

 

C언어는,

1. 배열에 쓰일 자료형과 그 수를 지정해줘야 한다.

2. 배열에 원소가 저장되면, 메모리에 그 배열이 연속적으로 저장되고(값 자체), 첫 원소의 주소를 통해 원소들에 접근한다.

 

한편 Python은,

1. 자료형과 수를 지정해줄 필요가 없다.

(내장 기능을 통한 resize와 작동원리로 인해)

 

2. C언어와 다르게, 이중으로 배열을 저장한다.

(C언어는 메모리에 그 값 자체를 저장하고 배열의 주소를 이용해 호출하였지만,

Python은 메모리에 그 값의 주소를 저장하고, 배열의 주소 - 값의 주소를 이용해 호출한다.)

-> 이로 인해 자료의 type에 구애받지 않고 서로 다른 자료형을 저장할 수 있고,

C언어에 비해 속도가 느리다.

 

즉, 신찬수 교수님의 설명에 따르면

Python에서 list는 그 값을 갖는 '객체의 주소'를 배열에 저장한다.

---

append의 작동원리와 다른 메소드들의 시간복잡도

Python의 list는 C의 array와는 다르게 동적 배열이다.

list라는 class가 내장되어 있는 것이고, 

그 list의 크기에 따라 알아서 capacity가 조절되게끔 작동한다.

 

이렇게 생각해보면, 튜플은 정적 배열이라고 할 수 있을 것 같다.

하지만 list와 같이 여러 자료형을 가질 수 있는

---

어제 풀었던 Queue 문제는 어떻게 보면 사실 Dequeue였다. (front와 back을 통해 앞/뒤로 pop했음)

---

'아직 제대로 수강을 안 했음'

---

Stack(위에서 위로, 후입선출)과 Queue(위에서 아래로, 선입선출)가 입출구가 한개,

Dequeue가 입출구가 두개인 것이다.

 

Linked List(연결 리스트)는 메모리로 연속되어있는 것이 아닌,

다음 값이 올 주소를 현재의 값이 갖고 있는 것이라고 한다.

-> 배열처럼 index로 접근할 수 없고, n번째 값을 탐색하려면, 처음부터 n번째까지 순차적으로 탐색해야한다.

---

스택 class의 구현

이전에 풀었던 스택 문제를 class를 이용해서 다시 풀어보기로 했다.

import sys
 
class Stack:
    def __init__(self):
        self.items = []
        
    def push(self, val):
        self.items.append(val)
        
    def pop(self):
        try:
            print(self.items.pop())
        
        except IndexError:
            print("-1")
    
    def top(self):
        try:
            print(self.items[-1])
        
        except IndexError:
            print("-1")
            
    def empty(self):
        if len(self.items) == 0:
            print('1')
        
        else:
            print('0')
            
    def __len__(self):
        return len(self.items)
#########################################
N = int(sys.stdin.readline().rstrip())
S = Stack()
 
for _ in range(N):
    command = sys.stdin.readline().rstrip()
    
    if ' ' in command:
        S.push(command.split(' ')[1])
        
    elif command == 'pop':
        S.pop()
    
    elif command == 'top':
        S.top()
    
    elif command == 'empty':
        S.empty()
    
    else:
        print(len(S))

역시나 그냥 input()으로 했을 때에는 시간초과가 났다.

class를 사용할 때 print와 return을 섞어 쓰지 않고, 일관되게 사용하는 것이 더 좋지 않을까..?

하는 생각에 다시 작성해보았다.

class Stack:
    def __init__(self):
        self.items = []
        
    def push(self, val):
        return self.items.append(val)
        
    def pop(self):
        try:
            return self.items.pop()
        
        except IndexError:
            return "-1"
     
    def top(self):
        try:
            return self.items[-1]
        
        except IndexError:
            return "-1"
            
    def empty(self):
        if len(self.items) == 0:
            return '1'
        
        else:
            return '0'
            
    def __len__(self):
        return len(self.items)
#########################################
N = int(input())
S = Stack()
 
for _ in range(N):
    command = input()
    
    if ' ' in command:
        S.push(command.split(' ')[1])
        
    elif command == 'pop':
        print(S.pop())
    
    elif command == 'top':
        print(S.top())
    
    elif command == 'empty':
        print(S.empty())
    
    else:
        print(len(S))

---

예시 문제 1 - 괄호(9012)

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다.

그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다.

한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다.

만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다.

그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다.

예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다.

입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.

각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다.

하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를

한 줄에 하나씩 차례대로 출력해야 한다. 

예시문제 설명을 듣기 전에 먼저 백준으로 풀어보기로 했다.

---

1차로 든 생각.

'이거 그냥 ' ( '랑  ' ) ' 갯수 세서 다르면 VPS아니라고 하면 되는 거 아니야?

-> ())( 일 때 반례이므로 안 됨.

 

그리고 생각해본 결과 다음과 같이 이해했다.

 

어떻게든 VPS는 반드시 () 한 짝 이상을 가지게 된다.

스택으로 입력을 받으면서, ()이 되는 상태가 된다면, 그 쌍을 pop한다.

확인해서 다시 ()이 있다면 pop 한다.

.... 반복한다 ...

확인해서 스택이 비어있다면 VPS이고, 아니면 VPS가 아니다.

 

예시출력이랑 다른 하나는 괄호를 잘못 적은 듯

---

예제 2 - 스택을 활용한 계산기

우리가 흔히 아는 infix 수식 vs postfix

마지막에 출력하는 outstack은 list, opstack은 stack이다.

0. expr(expression)에 있는 모든 토큰(의미가 있는 단위 - 알파벳, 연산자)들 중,

1. 피연산자(operand)는 outstack에 append

2. '(' 라면 opstack에 push (우선순위는 가장 낮으나 무조건 push - 괄호의 계산을 먼저 하므로)

3. ')'라면 '('가 나타날 때 까지 모든 연산자(operator)를 pop.

4. token이 '사칙연산'중에 있다면, opstack에서 본인보다 높은 연산자를 모두 pop하고 자신을 push

5. expr 반복문이 끝났다면 남은 opstack의 연산자를 모두 pop, outstack에 append.

---

예시와 stack을 이용한 postfix 계산방법 / S.push(b token a)가 올바르다.

---

처절한 싸움

---

고지가 보인다!

---

outstack은 성공했는데 계산 결과 구현에 고통받는 중..

for문만 계속 고집해서 썼더니

순서가 어긋나서 자꾸만 안 됐다.

그런데!

'while'의 존재가 떠올랐다.

 

그. 런. 데.

while문의 무한 루프를 못 견디고 함께 바람처럼 사라졌다.

돌아와줘... 나 너무 슬퍼.. 미안해.. 내가 더 잘 짤게..

내가 시간 조금 들여서 짠 코드 날려도 이런 기분인데..

실무에서 쓰는 거 하나 날라가면 어떤 기분일까.. 싶다.

---

 

여기 중지 버튼이 떡하니 있었는데...

일단 슬픔을 추스르고 후반부의 outstack을 이용해서 결과를 계산해보기로 했다.

휴~

---

오늘 그리디 알고리즘까지 진도를 빼보려고 했는데 어쩌다보니 시간이 좀 많이 흘렀다.

깃허브에 처음으로 올릴 생각에 싱글벙글이었는데..

여태 짜본 코드 중에 가장 길었는데..

내일 다시 해봐야겠다.

 

앞으로 while문을 시험해볼 때에는

반드시.. 반드시 케이스를 떼서 굴려볼 것이다..

반드시...