[TIL] 자료구조-02.배열,리스트,스택,큐(1)

인정어임정합니다·2020년 7월 30일
0

자료구조

목록 보기
2/4
post-thumbnail

❌ 학부생 수준에서 작성된 글로 정확하지 않을 수 있습니다!
❌ 틀린 부분 피드백 미리 감사드려요..🥺

👩‍💻 순차적 자료구조

1. 배열, 리스트

정의: 데이터를 연속적(순차적) 메모리 공간 안에 저장하고, 저장된 곳의 주소를 index number를 통해 빠르게 접근할 수 있는 자료구조

📍 C언어 배열(array)과 Python 리스트(list)의 가장 큰 차이점?
: Python 이 더 다양한 연산을 지원하며, 동적 자료구조라는 점이다

1.1. C언어 배열

  • 배열 크기가 처음 사용자가 지정한대로 굳어지기 때문에, 특정 용량을 넘어가는 삽입 연산을 수행할 수 없다
  • 배열 시작 주소, 저장된 값의 data type(to know byte), 몇 번째에 저장되어있는지만 알면 값이 저장된 곳의 주소 계산 가능
  • ❗️ 읽기, 쓰기 연산만 제공하는 제한된 자료구조!

    📌 C언어 배열을 그림으로 이해하기 - C언어에는 파이썬의 append함수처럼 공간을 임의로 다시 할당해서 데이터를 추가하는 기능이 없기 때문에 A[4]라는 인덱스를 발견할 수 없어, IndexError가 발생한다.

1.2. Python 리스트

  • 객체의 주소값이 저장되는거지, 객체가 직접 리스트 칸에 저장되지는 않는다
  • C언어 배열보다 더 유연한 연산 제공
  • 연산 종류 참고 📎https://wikidocs.net/14#_11
  • 연산에 따른 수행시간은 이전 포스팅에서 정리함.

    📌 Python 배열을 그림으로 이해하기
    보다시피 7이라는 객체는 RAM의 어딘가에 존재하고 있으며, 단지 A[2]가 가리키는 객체가 9로 변경된 것이다.

⭐️ 그래서 중요한게 뭔데!!🤬

리스트 = "동적배열" 이라는 것이다.

  • append, insert 함수를 통해 파이썬 리스트는 공간이 부족하면 더 큰 메모리를 할당받아 새로운 리스트를 만들고, 이전 리스트의 값을 모두 이동시킨다.

  • 식구가 늘어서 작은집에서 큰 새집으로 이동하는거라고 생각하면 된다.

    📍 동적배열이란?
    필요에 따라 크기가 변하는 배열. 사용자가 전혀 배열 크기를 신경쓰지 않아도 되서 편리하다

  • 빈 리스트는 0바이트보다 클 수 없다

  • 파이썬 내부에서 자체적으로 현재 리스트 용량(capacity)와 저장된 값의 개수(n)을 관리한다.
    ex) .append()연산의 작동 예시

def append(A, value):
   if A.capacity == A.n: #만약 A의 용량이 가득 차게 되면
      allocate a new list B with larger memory and
      update B.capacity and B.n
      #B라는 새로운 리스트를 생성한다(단, B's capacity > A's capacity)
      for i in range(n): 
         B[i] = A[i] #새로운 리스트 B에다가 A를 싹 옮긴다
      dispose A #용량이 넘 작은 옛날 리스트 A는 버린다
      A = B #B리스트의 이름을 A로 변경한다

==> 이렇게 되면 결과적으로 A[n] = value(새로운 값), A.n = n+1이 된다.
-Resize⭕️ .append() 수행시간: O(n)
-Resize❌ .append() 수행시간: O(1)

2. Stack, Queue, Deque

이들의 공통점: 매우 제한적인 연산을 지원하는 자료구조

2.1. Stack

  • 데이터는 리스트에 저장된다(append, pop함수 이용)
  • 연산: push, pop, top, isEmpty, size(len) ...
  • Stack_queue.py 파일을 만들고, 클래스를 선언해서 구현한다.

스택이라는 개념이 참 쉬우면서도 어려운 것 같다.. 개념 자체는 회계원리때 배운 LIFO로 이해하니까 이런거구나~ 하는데 막상 활용해서 코드를 짜보려고 하니까 그렇게 어려울 수가 없다..
내 학습능력에 통탄하는 나의 모습.. 하루 종일 붙들어매고있는데 진도도 못나가고 속상함이 오만배..🥺

#Stack_queue.py
class Stack:
    def __init__(self): #생성함수
        self.items =[] #데이터 저장을 위한 리스트를 준비한다.(값들이 저장될 곳)

    def push(self, val):
        self.items.append(val) #append함수를 활용해서 push()를 만들었다
        #push(self, val) --> self라는 객체(스택)에 val을 넣어라

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty") 
            # pop할 item이 없으면 IndexError가 발생하고, 
            #'Stack is empty'라는 메시지가 뜬다
            
    def top(self): #pop()과는 달리 그냥 맨 위에 있는 item이 뭔지 보여주기만 함(삭제하지 않는다!!!)
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self): #len()호출시, stack item 수 반환
        return len(self.items)

    def isEmpty(self): #stack이 비어있는지를 판단. 길이가 0인지?
        return len(self) == 0

📍 try-except vs if-else
둘 다 조건문이고 수행하는 역할이 같아 보이지만 완전 다르다!

📍 IndexError
Raised when a sequence subscript is out of range. (Slice indices are silently truncated to fall in the allowed range; if an index is not an integer, TypeError is raised.)
리스트에서 없는 걸 참조하라고 할 때 발생. 지정한 범위 외에 없는 값을 참조하라면 나타난다.
📎 https://docs.python.org/3/library/exceptions.html#IndexError

위 코드는 스택의 기본적 구조이고 이를 활용하는 방법이 진짜 중요하다.

❗️과제 1) 괄호 쌍 맞추기

예를 들어 수식 ((a + b) * 3 + (2 + 4)) 는 괄호 쌍이 맞는다. 임의로 입력한 수식에서 괄호 쌍 갯수가 맞는지 코드로 확인한다.

✏️ 문제 풀이

# 괄호 쌍 맞추기 과제 1
from Stack_queue import Stack #스택 클래스 가져오기
def parChecker(parSeq):
	S = Stack() #괄호 쌍을 쌓아둘 빈 스택 공간 준비
	for i in parSeq: #임의의 괄호들로 이루어진 문자열에서..
		if i =='(': #일단 무조건 왼쪽괄호가 나오면
			S.push(i) #스택에 넣어준다
		else: #만약 오른쪽괄호가 먼저 나오면?
			if len(S) == 0:
				return False #쌍이 안맞는다
			else:
				S.pop() #쌍이 맞으면, pop을 통해 스택을 비운다
	if len(S) == 0:
    # if S.isEmpty(): 를 대신 사용할 수도 있다
		return True #스택 내 item이 없이 깔끔하면 True
	else:
		return False
				
		
A = input()
print(parChecker(A))

❗️❗️과제 2), 과제 3) 수행시간이 더 빠른 코드나 알고리즘이 있는지 찾아볼것. 훈수 환영합니다.

😫 자꾸 런타임 에러가 특정 부분에서 발생하는데, 실습환경에서만 발생하는 문젠지,, 파이참 또는 다른 플랫폼에서는 멀쩡하게 작동합니다.

❗️과제 2) infix to postfix 변환


이 문제를 교수님설명없이 혼자 해보려했는데 뭔소린지 몰라서 설명을 들었다.

🧐 내 말로 다시 풀어서 설명하면..
1. 우리가 알고 있는 연산 순서대로 한눈에 확 들어오게 괄호를 친다
2. 괄호의 밖으로 연산 기호를 빼내고, 피연산자를 나열한다.
--> 위에 있는 식에서 보면 B*C를 제일 먼저 해결해야 한다. "피연산자들은 붙여버리고, 연산자는 제일 안쪽 괄호 밖으로 빼낸다."
--> 그렇게 되면 ( A + B C
* ) 형태가 된다
3. 다음으로 마지막 괄호 밖으로 + 연산자를 빼주면.. 맨 오른쪽 형태 완성
📎 아가에게 설명해주듯 친절한 설명. 단점은 영어라는것이다 https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

✏️ 문제 풀이

from stack_queue import Stack
def infix_to_postfix(infix):
    prec = {} #연산자 딕셔너리를 만들어서 우선순위 매기기
    prec["*"] = 3 #{'*':3} 과 같은 말
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1

    opstack = Stack() #연산자를 쌓을 스택 공간을 만들어주기
    outstack = [] #postfix 결과를 쌓을 list 공간
    token_list = infix.split()
    #입력은 스페이스바로 하나하나 띄워서 받으니까 split()을 통해 각 인덱스에 문자 하나씩 넣기

    for token in token_list: 
        if token == '(': 
            opstack.push(token)
            
        elif token == ')': #오른쪽 괄호가 나타나면
            toptoken = opstack.pop() #맨 위에 있는 토큰을 toptoken이라 한다
            while toptoken != '(': #왼쪽괄호를 만나기 전까지
                outstack.append(toptoken) #만나는 모든 토큰을 outstack리스트에 저장한다
                toptoken = opstack.pop() #toptoken 값 바꾸기
                
        elif token in '+-/*^': #연산자를 만나면
            while (not opstack.isEmpty()) and (prec[opstack.top()] >= prec[token]): #연산 순위와, opstack내에 무언가가 존재한다는 전제 하에
                  outstack.append(opstack.pop()) 
            opstack.push(token) #연산자 우선순위에 따라 토큰 붙인다
            
        else: #피연산자는 그냥 붙이면 된다
            outstack.append(token)

    while not opstack.isEmpty(): #연산자 스택이 빌 때까지
        outstack.append(opstack.pop()) #연산자 다뽑아버리기
    return " ".join(outstack) #입력 형태랑 똑같이 만들어서 출력하기

infix_expr = input()
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr)

🧐 이게 어떤 원리냐면.. ex) ((A + B) * C) --> A B + C *

그림이 넘 큰데 나도 작게 넣고싶다... 미래의 내가 보겠지 뭐..

❗️과제 3) postfix 연산

infix to postfix를 리버스 시켜서 연산결과를 도출해내는 문제이다. 사실 앞에거보다 시간은 덜걸렸다. 애초에 postfix라는 개념을 이해를 못해서..🤦‍♀️

✏️ 문제 풀이

from stack_queue import Stack
def compute_postfix(postfix):
    operand = Stack() #이번엔 값을 알아내야되니까 피연산자가 스택에 들어가야 한다
    token_list = postfix.split()
    for token in token_list:
        if token in '1234567890': #사실 문자도 더할 수 있다. and 알파벳리스트 하면 된다
            operand.push(int(token)) #토큰은 문자열로 받았으니까 꼭 형변환 해주기!
            
        else: #연산자를 만나면
            b = operand.pop() #LIFO 원칙을 따르므로 맨 뒤 숫자부터 배정!! 여기서 실수해가지고 답이 이상해짐..
            a = operand.pop()
            result = calculator(token, a, b) #함수로 구현하는게 보기도 깔끔하고 따라가기도 굿
            operand.push(result) #연산 결과를 operand스택에 넣기
    return operand.pop() 
    #결과적으로 계속 피연산자 넣기 -> 연산자 만나면 연산 후 결과값 하나 넣기를 반복하므로 깔끔하게 답 하나만 나온다!

def calculator(i,op1,op2): #파이썬 응애시절 만들었던 계산기 함수..^^
    if i == '+':
        return op1 + op2
    elif i == '-':
        return op1 - op2
    elif i == '*':
        return op1 * op2
    elif i == '/':
        return op1 / op2
    else:
        return op1 ** op2

postfix_eval = input()
print('%.4f' %compute_postfix(postfix_eval)) 
#저희 교수님은 소수점 4자리까지 출력을 원하셨기 때문에 이렇게 했습니다.

왜 맨날 부동소수점 표현만 안외워지는지.. 부동소수점 문제만 10개씩 풀어야되나..
글이 너무 길면 나중에 찾아보기도 싫을거 같아서 큐와 디큐는 좀 나눠서 해야겠다.

📌 참고 사이트 및 출처
📎 파이썬 실행 과정을 알아볼 수 있는 "Python Tutor"
http://www.pythontutor.com/visualize.html#mode=display
(아나콘다 환경으로 하면 여러 기능이 지원되고 그림으로 나타내줘서 내가 뭘 실수하는지, 이 코드가 어캐 돌아가는지를 알 수 있음. 나 이거없음 과제못해..)
📎 교수님 유튜브 강의
https://www.youtube.com/playlist?list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK
📎 교수님 책(학교 서점에서만 살 수 있는걸로 앎)
📎 구름 실습환경
https://hufs.goorm.io/learn/lecture/21628/2020-%EC%97%AC%EB%A6%84%EB%B0%A9%ED%95%99-%EC%9E%90%EA%B8%B0%EC%A3%BC%EB%8F%84%ED%95%99%EC%8A%B5%EC%9A%A9-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%B0%8F%EC%8B%A4%EC%8A%B5-python

profile
뇌로만 부지런한 사람

0개의 댓글