TIL#36 자료구조 -3

Dasom·2020년 8월 18일
0

자료구조

목록 보기
4/8

추상자료형

기능 vs 구현

예) 삽입연산
기능 - 연산이’무엇’을 하는지
순서데이터에서 원하는 위치에 데이터를 저장
구현 - 연산의 기능을 ‘어떻게’하는지

추상화 - 구현을 몰라도 기능만 알면 프로그래밍을 할 수 있게 해주는 개념
추상화를 하면 이미 쓴 코드를 재활용하고 개발자들끼리 협력하기 쉬워짐
자료구조를 사용할때도 추상화를 많이 사용

추상자료형(Abstract Data Type)
자료구조를 추상화 한것
데이터를 저장/사용할때 구현 부분을 생각하지 않고 순수한 기능이 무엇인지 나열한 것

추상자료형을 생각하면 코드의 흐름에 집중할 수 있다

파이썬 - 추상화가 많이 된 고수준 언어, 많은 자료형 이름이 추상 자료형

큐(Queue)

FIFO : First-in-first-out
-> 먼저 들어온 데이터가 먼저 삭제된다.

데이터간 순서 관계를 유지할 수 있다
-맨뒤 데이터 추가
-맨앞 데이터 삭제
-맨앞 데이터 접근

큐는 동적배열과 링크드 리스트로 구현할수 있다.

<시간복잡도>

동적 배열더블리 링크드 리스트
맨앞삭제O(n)O(1)
맨뒤삽입분할상환-> O(1)O(1)
맨앞접근O(1)O(1)

-> 파이썬에서는 deque 를 이용하여 큐를 쓸 수 있음
Deque : Doubly-ended-queue(양면큐)
맨 앞과 뒤에서 데이터 삽입, 삭제를 모두 할 수 있게 해주는 자료형

파이썬 deque는 내부적으로 더블리 링크드 리스트로 구현되어 있다.

# deque 는 파이썬 collections 모듈에서 가지고 온다.

from collections import deque

queue = deque()

# 큐의 맨 끝에 데이터 삽입
queue.append('Sam')
queue.append('Jane')
queue.append('Tom')
queue.append('Erin')
queue.append('Sera')

print(queue)  # 큐 출력.

# 큐의 가장 앞 데이터에 접근
print(queue[0])

# 큐 맨앞 데이터 삭제
print(queue.popleft())   # popleft() 제일 앞 데이터 삭제하는 메소드
print(queue.popleft())
print(queue.popleft())

print(queue)
# 고객센터 문의 처리.
from collections import deque

class CustomerComplaint:
    """고객 센터 문의를 나타내는 클래스"""

    def __init__(self, name, email, content):
        self.name = name
        self.email = email
        self.content = content


class CustomerServiceCenter:
    """고객 서비스 센터 클래스"""

    def __init__(self):
        self.queue = deque()  # 대기 중인 문의를 저장할 큐 생성

    def process_complaint(self):
        """접수된 고객 센터 문의 내용 처리하는 메소드"""
        if self.queue:
            complaint = self.queue.popleft()
            print(f"{complaint.name}님의 {complaint.content} 문의 내용 접수되었습니다. "
                  f"담당자가 배정되면 {complaint.email}로 연락드리겠습니다!")
        else:
            print("더 이상 대기 중인 문의가 없습니다!")

    def add_complaint(self, name, email, content):
        """새로운 문의를 큐에 추가 시켜주는 메소드"""
        new_complaint = CustomerComplaint(name, email, content)
        self.queue.append(new_complaint)

스택(Stack)

LIFO : Last-in-first-out
-> 가장 마지막에 들어온 데이터가 가장 먼저 삭제된다

데이터간 순서관계를 유지할 수 있다
맨 뒤 데이터 추가, 맨 뒤 데이터 삭제, 맨 뒤 데이터 접근.
파이썬에는 스택의 이름을 갖는 자료형은없다. 큐를 이용할 때와 같이 데크를 이용한다.

동적배열과 링크드 리스트를 이용해서 구현할 수 잇다.
출력결과나 시간 복잡도는 같다. -> O(1)

# Stack 은 파이썬 collections 모듈에서 가지고 온다

from collections import deque

stack = deque()

# 스택 맨 끝에 데이터 추가
stack.append('E')
stack.append('s')
stack.append('w')
stack.append('q')
stack.append('t')

print(stack)

# 맨 끝 데이터 접근
print(stack[-1])

# 맨 끝 데이터 삭제
print(stack.pop())
print(stack.pop())
print(stack.pop())

print(stack)
# 스택을 이용해 괄호 짝이 맞는지 확인하기

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()} 번째 위치에 있는 괄호가 닫히지 않았습니다")
# 이렇게 입력하게 되면 정답이 나온다

case1 = "(1+2)*(3+5)"
case2 = "((3*12)/(41-31))"
case3 = "((1+4)-(3*12)/3"
case4 = "(12-3)*(56/3))"
case5 = ")1+14)/3"
case6 = "(3+15(*3"

parentheses_checker(case1)
parentheses_checker(case2)
parentheses_checker(case3)
parentheses_checker(case4)
parentheses_checker(case5)
parentheses_checker(case6)
profile
개발자꿈나무🌲

0개의 댓글