220809_TIL / DataStructure Fundamental

신두다·2022년 8월 9일

TIL

목록 보기

70/82

Key words

자료구조(Data Structure), 추상자료형(ADT), Queue, Stack

자료구조를 생각할 때 오늘도 역시 'python'에 집중하기보단 컴퓨터 공학에서 말하는 자료구조의 맥락에서 생각해야 한다!

1. 자료 구조 (Data Structure)

자료 구조의 목적

큰 데이터를 효율적으로 관리하려는 것이다!
이 말에 대해 오늘 봤던 Warm-up 영상에 나왔던 현실의 예시를 살펴보면,
- 우리가 책을 1,2권 가지고 있을 때는 딱히 효율을 생각하거나 할 필요없이 그냥 쓰면 되는데, 만약 100권, 500권을 가지고 있다면? 공간도 많이 차지할 뿐 아니라 내가 원하는 책을 쉽게 찾기가 어려워진다. 그래서 우린 책장을 사고, 여러 기준(테마 등)에 따라 분류를 해둔다. 그럼 공간도 줄일 수 있고 가장 중요하게는 내가 원하는 책을 빠르게 찾을 수 있게 된다.
위 예시를 컴퓨터 공학으로 가져와보자. 우리가 데이터를 적게 가지고 있으면 자료 구조의 필요성이 작을 수 있지만, 100만개, 1000만개의 데이터를 가지고 있다면? 그 많은 데이터를 효율적으로 관리하고 원하는 데이터를 쉽게 찾아 쓰려면 그에 맞는 자료 구조를 잘 활용하는 것이 중요한 것이다.

자료 구조의 활용

똑같은 알고리즘을 사용하더라도 어떤 자료 구조를 사용하는지에 따라 효율성이 달라진다고 한다.
즉, 모든 자료 구조가 같은 효율성을 가지고 있는 것은 아니다. 따라서 우리는 자료 구조의 종류와 장단점은 무엇인지 잘 이해하고 있어야 하고, 내 목적에 따라 어떤 자료 구조를 사용할지 고를 줄 알아야 하는 것이다.

추상 자료형 (ADT, Abstract Data Type) - 자료구조의 핵심!

지난 주에도 추상화에 대해서 다룬적이 있는데 오늘도 자료 구조와 관련해 이를 다시 다뤘다.
- 추상화는 쉽게 생각해 핵심요약이다. 오늘 좋은 예시를 보았는데, 네 각이 모두 직각이다. 네 변의 길이가 같다.를 우리는 그냥 정사각형이라고 부른다. 이것도 추상화라고 함! (네이버 지식백과에 나온 예시 참고.)
- 즉 CS에서 추상화란, 프로그램의 크기나 복잡도가 증가하면서 프로그램의 핵심부분을 간단하게 설명하기 위해 생겨났다고 기억하면 될 것 같다.
오늘 배운 연결 리스트(linked-list), Queue, stack도 마찬가지다. 이런 ADT는 기본 자료형인 리스트, 숫자, 문자열 등을 활용하여 사용자에 의해 구현된다.
- 무슨 말이냐? 연결리스트건, 큐건, 스택이건 이들은 실재하는 것이 아니다. 다만, 우리에게 자료를 다룰 구조를 만들 규칙들을 제공한다.

2. Queue, Stack

대표적인 ADT인 queue와 stack에 대해서 배웠는데 좋은 예시가 많아서 이해하는데 크게 어렵지는 않았다.

Queue

우선 이름이 참 직관적이다. 큐를 이해하려면 마트 계산대에서 줄 서 있는 걸 생각하면 된다. 먼저 줄 서 있던 사람이 먼저 계산하고 나간다. 나중에 온 사람은 줄 맨 뒤에 선다. 이보다 직관적인 예시가 어딨어?!!
- 콜센터 백엔드 시스템을 예를 들면, 먼저 온 전화부터 상담하도록 하니까 이럴 땐 큐를 사용한거다!
다른 말로는 선입선출, First IN First OUT이라고 할 수 있다.
이 그림을 이해하면 좋을 듯.
- 큐는 자료의 입출력이 한 방향에서만 이루어지는 자료 구조이다. 즉, 큐의 맨 뒤에서만 값이 들어오고, 맨 앞에서만 값이 나간다. (enqueue는 큐에 값을 집어넣는 함수고, dequeue는 빼내는 함수다.) 파이썬으로 구현할 때 rear, front를 지정해주는 이유다.
deque라고 collections 모듈에 있는게 있어서 이걸로 큐 구현을 쉽게 할 수도 있다. (그 외 방법은 실습 코드의 레퍼런스 주석 참고!)

# 리스트 메소드를 사용해서 큐를 만들어보기
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           
queue.append("Graham")

print('queue:', queue)
print('queue.popleft():',queue.popleft())
print('queue.popleft():',queue.popleft())
print('queue:', queue)

Stack

쌓인다는 이름을 가지고 있다. 스택은 배열이 수직으로 쌓여있는 걸 말하고, 쉽게 팬케이크를 생각하면 된다. 팬케이크를 쌓아두고 먹을 때 우리는 맨 위에 있는 것부터 먹는다.
즉, 가장 나중에 온 팬케이크가 가장 먼저 집어 먹힌다! 다른 말로는 Last In First OUT이다.
stack에 데이터를 추가하는 기능을 push라고 하고, 최상위 데이터를 꺼내는 기능을 pop이라고 한다.
참고로 스택의 최상위 데이터를 가르키는 용어로는 top,peek,head가 있다!
우리가 브라우저에서 뒤로가기 버튼을 누르면 이전 페이지로 돌아가는데, 이건 스택을 쓴거다. (상상하면 된다.. 내가 처음 브라우저를 켜면 홈페이지가 쌓이고, 그 위에 그 다음 페이지, 그 위에 그 다음 페이지...)

3. 배열이란?

연결 리스트가 뭔지 정리하기 전에, 먼저 배열에 대해서 적어보자!

배열이란?

기본적인 자료 구조인데, 배열은 정해진 크기의 같은 타입의 데이터를 저장하는 구조를 가진다. (cf. 파이썬 리스트는 다양한 타입을 혼재해서 넣을 수 있음)
정적배열, 동적배열, 연결리스트 같은 건 선형 자료구조라고 하는데, 이 말은 데이터들을 일렬로 나열된 형태로 저장되어 있다는 뜻이다.
- (비선형 자료구조인 트리, 그래프는 다음 스프린트 때 배울 예정이라고 함)

배열에는 정적 배열과 동적 배열이 있다.

(정적) 배열
- 선언시 반드시 배열의 크기를 결정해야하고, 이 크기는 고정적이며 절대 변경될 수 없다. 메모리상에서도 원소들이 연속적으로 붙어있다.
- 메모리 안에 연속적으로 붙어있기 때문에 index를 통한 read가 빠르고 편한 장점이 있다.
- 반면 단점으로는, 위 정의를 읽기만 해도 알 수 있듯이, 크기를 추가하거나 축소하는게 불가능하다는 것.
- (장점이 꼭 필요할 때만 쓰게될 것 같다는 생각이 든다..)
동적 배열
- 배열의 크기를 유동적으로 할 수 있고 메모리 상에서도 원소들이 연속적으로 붙어있다. 정적 배열의 보완판 느낌인듯.
- 실제로 사용할 크기보다 여유있게 1.5~2배 크게 배열의 크기를 두고 선언한다고 한다. 그러나 만약 이 크기도 모자라면 이사를 해야하는데 그 비용이 큰게 단점이다._ (예를 들어, 도서관에 책이 꽉차면 더 큰 도서관 지어서 옮겨야할 것 아닌가!)
- 또 메모리의 연속성 때문에 중간에 데이터를 삽입/삭제하는게 어렵다고 한다.

자 배열에 대해서 알아봤으니 이제 배열의 단점을 보완한 연결 리스트에 대해서 알아보자!

4. 연결 리스트 (linked-list)

다시 한 번 강조하고 싶은 건, 배열의 단점을 보완하기 위해 나온게 연결리스트라고 해서 연결리스트가 배열보다 무조건 좋다고는 할 수 없다는 것이다. 자료 구조 생각할 때는 언제나 내 목적에 맞는 가장 좋은 자료구조를 고르는 것이라는 것 유의하자!

연결 리스트가 뭔지는 우선 아래의 그림을 보자.

(위가 연결리스트고 아래가 배열이다. 차이 위주로 보면 됨.)
연결 리스트는 배열과 다르게 메모리 연속성을 가지지 않는다. 리스트의 길이를 별도로 지정해줄 필요도 없다.
연결 리스트는 노드로 구성되어 있고 각 노드에는 value와 다음 원소의 위치 정보를 포함하고 있는 식으로 서로 연결되어 있는 식이다. 즉, 연결 리스트의 핵심은 노드 간의 연결이다!
- (위 그림의 head를 보면 4라는 값을 가지고 있고, 다음 노드가 어디인지 위치 정보를 가지고 있는 것! 무슨 말인지 헷갈리면 아래 실습 코드에서 연결 리스트 구현할 걸 보면 도움이 될 것이다.)
- 파이썬의 리스트는 이런 의미에서 배열과 연결 리스트의 중간에 위치한다고 할 수 있다. 인덱스로 간편하게 접근할 수 있으면서도 크기가 고정되어 있지 않다.
next 노드 정보만 가지고 있다면 이걸 단방향 연결 리스트라고 하고, 이전 노드, 다음 노드의 정보 모두를 갖고 있다면 양방향 연결 리스트라고 부른다. (원형(환영) 연결 리스트라는 것도 있긴 함)
따라서 데이터를 추가하고 삭제하기 빠르고 편한 것이 장점이다. 중간에 뭐 하나를 제거했으면, 제거한 노드의 전 노드에서 다음 노드의 위치 정보를 변경하기만 해주면 되는거다.
- 만약 head에 있는 노드를 제거했다면? 그걸 바로 제거하는게 아니라 그 다음 노드를 head로 바꿔주고 난 다음에 원래 head를 제거한다. 위치를 바꿔주는거지!
- 그런 의미에서 연결 리스트는 복잡도는 O(1)이다.
- (이것도 오늘 연결 리스트 구현 코드 중에 있으니 참고)
단점은 딱 반대인데, 메모리 연속성을 갖고 있지 않으니 어떤 값을 찾으려면 head부터 차례차례 보면서 넘어가야 한다는 것이다.

5. 실습한 것

queue, stack을 파이썬 리스트를 통해 구현하기

파이썬으로 연결리스트 구현하기

코드 잘 보면 각 자료 구조에 대해 이해하기 도움되니 나중에도 잘 참고하자.

[리스트 메서드 이용해서 큐, 스택 구현하기]

"""
Bare Minimum Requirements

요구사항
    큐, 스택을 구현해주세요.
    각 메소드에 작성되어있는 문제를 확인하여 코드를 작성해주세요.

    리스트 메소드를 활용해서 구현해보세요.
    메소드 이름은 변경하지 마세요.
    메소드의 매개변수를 추가하거나 삭제하지 마세요.
"""

# 문제에서 리스트 메소드를 활용해서 구현하라고 한 것 놓쳐선 안됨!

class Queue(): # reference https://daimhada.tistory.com/107 (리스트 뿐 아니라 다양한 방법으로 큐를 구현하는 예시를 볼 수 있음.)
    def __init__(self):
        """
        # 문제 1.
        Queue의 생성자 함수를 구현해주세요.
        Queue 생성시 데이터를 담을 공간을 만들어주세요.
        구현하시려는 로직에 맞게 해당 함수를 구현해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        self.queue = [] # 빈 리스트(큐)를 생성한다. 

    def enqueue(self, item):
        """
        #. 문제 2.
        queue에 item 매개변수에 들어온 값을 집어넣는 메소드를 구현해주세요.

        input: item
            queue로 들어갈 값입니다.
        output: 
            반환값은 없습니다.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        self.queue.append(item) # 리스트의 끝에 더해나가도록 한다. 


    def dequeue(self):
        """
        #. 문제 3.
        queue 동작에 알맞게 값을 queue에서 삭제하는 메소드를 구현해주세요.

        input: 
            input은 없습니다.
        output: 
            queue동작에 맞게 queue에서 삭제된 값을 반환해주세요.
            만약 삭제한 값이 없다면 None을 반환해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        # 가장 처음 들어간 값(=리스트의 맨 앞 요소)를 추출하자. (input이 없다고 했으므로)
        if len(self.queue) == 0: # 만약 큐가 비어있어 삭제할 게 없다면 None을 반환하라.
            return None
        else: 
            return self.queue.pop(0) # 큐가 비어있지 않다면 가장 첫 값을 추출하고 반환해라.


    def return_queue(self):
        """
        #. 문제 4.
        queue내부에 있는 값을 반환하는 메소드를 구현해주세요.

        input: 
            input은 없습니다.
        output: 
            queue내부에 있는 값을 리스트 형태로 반환해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        return self.queue

'''
[기록] 만든거 테스트해보기 - 잘 되는군.
qtest = Queue() # 객체 생성

print('first enqueue= ', qtest.enqueue(5)) # => first enqueue=  None
print('return enqueue= ', qtest.return_queue()) # => [5]
print('delete queue= ', qtest.dequeue()) # => 5
print('return enqueue= ', qtest.return_queue()) # => []
print('delete empty enqueue= ', qtest.dequeue())  # => None
'''


class Stack():
    def __init__(self):
        """
        # 문제 5.
        Stack의 생성자 함수를 구현해주세요.
        Stack 생성시 데이터를 담을 공간을 만들어주세요.
        구현하시려는 로직에 맞게 해당 함수를 구현해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        self.stack = [] 


    def push(self, item):
        """
        #. 문제 6.
        Stack에 item 매개변수에 들어온 값을 집어넣는 메소드를 구현해주세요.

        input: item
            Stack로 들어갈 값입니다.
        output: 
            반환값은 없습니다.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        self.stack.append(item)


    def pop(self):
        """
        #. 문제 7.
        Stack 동작에 알맞게 값을 Stack에서 삭제하는 메소드를 구현해주세요.

        input: 
            input은 없습니다.
        output: 
            Stack동작에 맞게 Stack에서 삭제된 값을 반환해주세요.
            만약 삭제한 값이 없다면 None을 반환해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        if len(self.stack) == 0: 
            return None
        else:
            return self.stack.pop() # 가장 마지막에 나온 값을 출력하고 제거한다. 


    def return_stack(self):
        """
        #. 문제 8.
        Stack내부에 있는 값을 반환하는 메소드를 구현해주세요.

        input: 
            input은 없습니다.
        output: 
            Stack내부에 있는 값을 리스트 형태로 반환해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        return self.stack

참고로 파이썬에서 큐를 구현할 땐 리스트가 아니라 연결 리스트로 구현하는 편이라고 하는데 이는 효율성 때문이다. 리스트는 맨 끝에 있는 원소를 빼거나 맨 끝에 넣는 건 빠르지만, 만약 list[0]을 제거한다면? 나머지 원소가 하나씩 왼쪽으로 이동해야 하기 때문이다. 자세한 건 이 자료 참고.

[연결리스트 구현하기]

"""
Bare Minimum Requirements
연결리스트의 개념은 변수의 인덱스에 직접접근하는 배열개념과는 다릅니다.
참조의 개념을 활용하여 변수에 접근하는 방법을 익혀봅니다.

요구사항:
    주어진 문제는 연결리스트지만 독립적으로 개념이 운용되는 것은 아닙니다.

    연결리스트를 구현해주세요.
    각 메소드에 작성되어있는 문제를 확인하여 코드를 작성해주세요.

    단 collections 라이브러리는 사용하지 마세요.
    메소드 이름은 변경하지 마세요.
    메소드의 매개변수를 추가하거나 삭제하지 마세요.
"""

class Node:
    def __init__(self,value,next=None):
        """
        # 문제 1.
        Linkedlist에서 사용할 Node의 생성자 함수를 구현해주세요.
        
        속성값: value, next
            value: Node의 값
            next: 생성될 Node의 다음 Node, 기본값은 None
        output:
            반환값은 없습니다.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        self.value = value
        self.next = next 


class linked_list:
    def __init__(self, value):
        """
        # 문제 2.
        Linkedlist의 생성자 함수를 구현해주세요.
        
        속성값: head
            head: Linkedlist의 value값을 가진 Head Node
        output:
            반환값은 없습니다.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        self.head = Node(value) # Node 클래스를 통해 생성한 노드를 head로 지정. next = None.


    def add_node(self, value):
        """
        # 문제 3.
        Linkedlist에 새로운 Node를 추가하는 메소드를 작성해주세요.
        
        input: value
            value: Linkedlist에 들어올 새로운 Node Value
        output:
            반환값은 없습니다.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        if self.head == None: # 연결 리스트에 노드가 del_node로 없는 경우를 대비.
            self.head = Node(value) # 그럴땐 새로 넣는 value를 가진 노드를 만들어 head로 지정.
        else: # 연결 리스트에 값이 존재하는 경우
            node = self.head
            while node.next: # head의 next에, 그 다음 next에 ..(반복).. node.next = None일 때까지.
                node = node.next # 즉, 마지막 노드까지 가는 것.
            node.next = Node(value) # 위에서 찾은 마지막 node의 next에 새로운 node를 추가하라. 


    def del_node(self,value):
        """
        # 문제 4.
        Linkedlist에 value값을 가지고 있는 Node를 삭제하는 메소드를 작성해주세요.
        
        input: value
            value: Linkedlist에서 삭제할 Node Value
        output:
            값을 삭제하였다면 삭제한 Node의 value를 반환
            만약 LinkedList에 값이 없다면 None 반환
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        if self.head == None: # 연결 리스트에 head가 아예 없는 경우엔 삭제고 뭐고 할 필요가 없음.
            return None
        elif self.head.value == value: # 만약 삭제하려는 값이 head의 값이었다면? 
            tmp = self.head # 원래 head였던 노드를 변수에 할당.
            self.head = self.head.next # head 노드를 원래 헤드의 다음 노드로 새로 지정하고
            del tmp # 원래 헤드였지만 지금은 헤드가 아닌 그 노드를 삭제하라!
            return value # 이거 나중에 헷갈릴 수 있겠다. 연결 리스트로 된 노드들을 직접 그림으로 그려보면서 생각해보자.
        else: 
            node = self.head # 항상 head 노드부터 시작.
            while node.next:
                if node.next.value == value: # 내가 지우려는 값을 찾았다면?
                    tmp = node.next
                    node.next = node.next.next # 내가 지우려는 노드의 다음 값을 원래 노드의 next로 바꾸고
                    del tmp # 지우려는 노드 지워! 
                    return value
                else:
                    node = node.next # 못 찾았으면 다음 노드로 가!

        
        
        # 값이 여러 노드에 있으면 어떻게 되지?


    def ord_desc(self):
        """
        # 문제 5.
        Linkedlist에 저장된 값들을 리스트 형태로 반환하는 메소드를 작성해주세요.
        
        input: 
            input값은 없습니다.
        output:
            Linkedlist의 Head부터 시작하여 저장된 모든 Node의 Value들을
            리스트 형태로 반환해주세요.
        아래 pass를 지워주시고 코드를 작성해주시면 됩니다. 
        """
        res = [] # value 모아서 리턴할 리스트

        node = self.head
        while node: # 노드가 있을 때까지 반복
            res.append(node.value)
            node = node.next # 다음 노드로 'node'를 변경.
        
        return res



    def search_node(self,value):
        """
        # 문제 6.
        Linkedlist에 value값이 어디에 위치하는지 찾는 메소드를 작성해주세요.
        
        input: value
            value: Linkedlist내부에서 찾고자 하는 값
        output:
            연결리스트에서 value를 가진 노드를 찾아 노드를 반환
            아래 pass를 지워주시고 코드를 작성해주시면 됩니다.
        """
        node = self.head # 연결리스트는 늘 head 부터 탐색한다는 점 기억!
        while node:
            if node.value == value: #노드의 값이 내가 찾는 값이라면
                return node 
            else: # 해당 노드가 내가 가진 값을 안 갖고 있다면
                node = node.next # 다음 노드로 'node'를 변경.