TIL (2020.08.18) (2)

Awesome·2020년 8월 18일

TIL python 자료구조 추상자료형

TIL

목록 보기

24/46

자료구조

추상 자료형

기능과 구현

기능 : 연산이 무엇을 하는지에 대한 내용
예시) 삽입연산의 기능 : 순서 데이터에서 원하는 위치에 데이터를 저장

구현 : 연산이 기능을 어떻게 하는지에 대한 구체적인 내용
예시) 동적배열을 활용하여 인덱스 뒤 데이터를 한 칸씩 뒤로 밀고, 데이터를 저장

추상 자료형(Abstract Data Type)

추상 자료형: 자료 구조를 추상화 한 것으로, 데이터를 저장/사용할 때 기능만을 고려하면 됨

프로그래밍을 할 때, 추상 자료형을 활용하면 코드의 흐름에 집중할 수 있다.

리스트(List)

파이썬은 추상화가 많이 된 고수준의 언어이다. 파이썬의 list, dictionary, set 등이 대표적인 추상 자료형이다.

파이썬의 리스트는 추상 자료형으로 동적 배열과 링크드 리스트로 구현할 수 있다.

리스트를 구현할 때, 어떤 기능을 더 많이 활용하는가에 따라서 자료구조가 바뀔 수 있다. 시간 복잡도를 고려하였을 때, 접근이 많은 경우라면 동적 배열을, 데이터를 앞에서부터 삽입하는 경우가 많다면 링크드 리스트를 활용하여 구현하는 것이 좋다.

기본적으로 파이썬은 동적 배열로 구현되어 있다. 따라서 이를 고려하여 리스트를 활용할수록 보다 나은 프로그래밍이 가능하다.

큐(Queue)

데이터 간의 순서를 약속하는 추상 자료형이며, 선입선출(First-In-First-Out)의 특징을 갖는다. 큐는 대표적으로 세 개의 연산을 갖는다.

맨 뒤 데이터 추가
맨 앞 데이터 삭제
맨 앞 데이터 접근

파이썬에서는 Collections 모듈의 deque(doubly-ended-queue) 자료형을 사용할 수 있다. 리스트와 마찬가지로 동적 배열과 링크드 리스트로 구현 가능하다.

시간 복잡도를 고려하였을 때, 큐는 링크드 리스트로 구현하는 것이 보다 효율적이다. 파이썬의 deque 는 내부적으로 더블리 링크드 리스트로 구현되어 있다. 참고자료

스택(Stack)

스택은 큐와 다르게 LIFO(Last-In-First-Out) 으로 가장 나중에 들어온 데이터가 가장 먼저 처리된다.
스택은 다음 세 개의 연산을 대표적으로 갖는다.

맨 뒤 데이터 추가
맨 뒤 데이터 삭제
맨 뒤 데이터 접근

파이썬에서는 큐와 마찬가지로 deque를 이용하여 스택을 사용할 수 있다.
스택도 큐, 리스트와 마찬가지로 동적 배열과 링크드 리스트로 구현 가능하다.

두 자료 구조 모두 $O(1)$ 의 시간 복잡도를 갖는다. 따라서 어떠한 자료 구조를 사용하더라도 차이가 크지 않음을 알 수 있다. 따라서 파이썬의 리스트(동적 배열)를 사용하는 것과 deque(링크드 리스트)를 사용하는 것에 차차이가 없다. 메소드의 이름도 동일하다.

스택을 활용한 대표적인 문제가 괄호의 짝을 찾는 문제이다.

from collections import deque

def parentheses_checker(string):
    """주어진 문자열 인풋의 모든 괄호가 짝이 있는지 확인해주는 메소드"""


    print(f"테스트하는 문자열: {string}")
    stack = deque() # 사용할 스택 정의

    # 코드를 쓰세요
    for i in range(len(string)):
        if string[i] == "(":
            stack.append(i)
            
        if string[i] == ")":
            if stack:
                stack.pop()
            else:
                print(f"문자열 {i} 번째 위치에 있는 닫는 괄호에 맞는 열리는 괄호가 없습니다")
                
    while stack:
        print(f"문자열 {stack.pop()} 번째 위치에 있는 괄호가 닫히지 않았습니다")

반복문을 실행하면서 열린 괄호의 인덱스만 스택에 담는다. 그리고 닫힌 괄호가 나올 때마다 스택의 가장 마지막 데이터를 제거한다. 그 이유는 가장 최근에 나오는 닫힌 괄호는 가장 나중에 나오는 열린 괄호와 짝이 되기 때문이다.
만약 열린 괄호가 없는 상태에서 즉, 스택에 인덱스가 없는 상태에서 닫힌 괄호가 나타나면 이는 짝이 없는 경우이다. 반대로, 닫힌 괄호를 찾는 반복문이 종료됐음에도 stack에 인덱스가 남아있다면, 해당 열린 괄호는 짝이 없는 것으로 볼 수 있다.