내가 정리하는 자료구조 00 (Node, List, Queue)

목표

• 기본 자료 구조/알고리즘 익히기
  • 알고리즘 풀이를 위해, 기본적으로 알고 있어야 하는 자료구조와 알고리즘 정리

자료구조란?

• 용어: 자료구조 = 데이터 구조 = data structure
• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미
• 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화해야 함.
  • 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라진다.

효율적으로 데이터를 관리하는 예

• 우편번호

  • 5자리 우편번호로 국가의 기초구역을 식별
  • 5자리 우편번호에서 앞 3자리는 시,군,자치구를 의미, 뒤 2자리는 일련변호로 구성

• 학생관리

  • 학년, 반, 번호를 학생에게 부여해서, 학생부를 관리
  • 위같은 기법이 없었다면, 많은 학생 중 특정 학생을 찾기 위해, 전체 학생부를 모두 훑어야 하는 불편함이 생긴다.

대표적인 자료 구조

• array(배열), stack(스택), queue(큐), linked list(링크드 리스트), hash table(해쉬 테이블), heap(힙) 등

알고리즘이란?

• 용어: 알고리즘(algorithm)
• 어떤 문제를 풀기 위한 절차/방법
• 어떤 문제에 대해, 특정한 ‘입력’을 넣으면, 원하는 ‘출력’을 얻을 수 있도록 만드는 프로그래밍

자료구조와 알고리즘이 중요한 이유

• 어떤 자료구조와 알고리즘을 쓰느냐에 따라, 성능이 많이 차이나기 때문이다. 결과적으로, 자료구조와 알고리즘을 통해 프로그래밍을 잘 할 수 있는 기술과 역량을 검증할 수 있다.

자료구조/알고리즘, 그리고 Python

• 어떤 언어로든 자료구조/알고리즘을 익힐 수 있다.
  • 이전에는 무조건 C 또는 C++로만 작성하도록 하는 경향이 많았다.
  • 최근에는 언어로 인한 제약/평가는 없어졌다고 봐도 무방할 것 같다.
    • 그러므로, 가장 쉽고 진입장벽이 상대적으로 낮은 Python을 통해 필자는 정리해 볼 것이다.

ADT(Abstract Data Type)

추상 자료형

실제 정의)

- 내부 구조(object)
- 기능(operation) ==> 함수로 구현

간단한 말로는 내가 사용하고자 하는 자료구조의 함수의 사용법이다.

필자는 Python을 통해 각 알고리즘을 구현해 볼 것이다. 물론 Python에는 이미 만들어져 놓은 library 중 대부분의 알고리즘을 구현해 놓은 것들이 존재하지만, 그렇게 사용하다보면 내부적으로 뜯어보지 않는 이상 어떠한 방식으로 작동되는지 알지 못하기 때문에 각 알고리즘의 구조를 설명한 후 ADT를 작성해 보고 class를 만들어 function을 작성하여 구현하는 방식으로 글을 써 갈 것이다. 물론, Python 내부에 존재하는 library의 사용법도 같이 소개할 것이다.

선형구조

• 배열
• 연결리스트
• 스택
• 큐

비선형구조

• 트리 (BTS —> B-tree, red-black tree)
• 그래프
• 테이블
• etc

Array(배열)

• 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
• Python에서는 리스트 타입이 배열 기능을 제공한다.

1. 배열은 왜 필요할까?

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종류의 데이터를 순차적으로 저장
• 장점:
  • 빠른 접근 가능
  • 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)
• 단점:
  • 데이터 추가/삭제의 어려움
  • 미리 최대 길이를 지정해야 함

C 언어 예: 영어 단어 저장

• 배열을 생성할 때 먼저 길이를 정해주어야 하기 때문에, 아래와 같이 []안에 최대 길이를 지정해준 것을 확인할 수 있다.

#include <stdio.h>

int main(int argc, char * argv[])
{
    char country[3] = "US";
    printf ("%c%c\n", country[0], country[1]);
    printf ("%s\n", country);    
    return 0;
}

파이썬 언어 예: 영어 단어 저장

country = 'US'
print (country)

2. 파이썬과 배열

• 파이썬에서는 리스트로 배열 구현 가능

1차원 배열: 리스트로 구현시

data_list = [1, 2, 3, 4, 5]
data_list

2차원 배열: 리스트로 구현시

data_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
data_list

결과

print (data_list[0])
# [1, 2, 3]

print (data_list[0][0])
# 1
print (data_list[0][1])
# 2
print (data_list[0][2])
# 3
print (data_list[1][0])
# 4
print (data_list[1][1])
# 5
print (data_list[1][2])
# 6

3. 프로그래밍 연습

연습1: 위의 2차원 배열에서 9, 8, 7 을 순서대로 출력해보기

print(data_list[2][2], data_list[2][1], data_list[2][0])

연습2: 아래의 dataset 리스트에서 전체 이름 안에 M 은 몇 번 나왔는지 빈도수 출력하기

dataset = ['Braund, Mr. Owen Harris',
'Cumings, Mrs. John Bradley (Florence Briggs Thayer)',
'Heikkinen, Miss. Laina',
'Futrelle, Mrs. Jacques Heath (Lily May Peel)',
'Allen, Mr. William Henry',
'Moran, Mr. James',
'McCarthy, Mr. Timothy J',
'Palsson, Master. Gosta Leonard',
'Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)',
'Nasser, Mrs. Nicholas (Adele Achem)',
'Sandstrom, Miss. Marguerite Rut',
'Bonnell, Miss. Elizabeth',
'Saundercock, Mr. William Henry',
'Andersson, Mr. Anders Johan',
'Vestrom, Miss. Hulda Amanda Adolfina',
'Hewlett, Mrs. (Mary D Kingcome) ',
'Rice, Master. Eugene',
'Williams, Mr. Charles Eugene',
'Vander Planke, Mrs. Julius (Emelia Maria Vandemoortele)',
'Masselmani, Mrs. Fatima',
'Fynney, Mr. Joseph J',
'Beesley, Mr. Lawrence',
'McGowan, Miss. Anna "Annie"',
'Sloper, Mr. William Thompson',
'Palsson, Miss. Torborg Danira',
'Asplund, Mrs. Carl Oscar (Selma Augusta Emilia Johansson)',
'Emir, Mr. Farred Chehab',
'Fortune, Mr. Charles Alexander',
'Dwyer, Miss. Ellen "Nellie"',
'Todoroff, Mr. Lalio']

m_count = 0
for data in dataset:
    for index in range(len(data)):
        if data[index] == 'M':
            m_count += 1
print (m_count)

• 위에서와 같이 간단하게 이미 만들어져 있는 Python의 자료형인 list를 사용하여 Array를 사용하는 것 말고 Node 개념을 도입하여 Array를 만들어 볼 것이다.

Node

• 아래와 같이 하나의 노드는 실제 데이터와 다음데이터를 가리키고 있는 참조로 구성되어있다.

• Node Class 구현
  • 위의 그림과 같이 실제 데이터를 가리키는 부분과 다음 데이터를 참조하는 부분을 나누어서 정의해 준다.

혼자 노드를 만들때 필요한 과정을 정리하면서 만들어보기

1) Node의 정의를 먼저 살펴보면 노드는 데이터를 포함하고있는 부분과 다음데이터를 가리키는 참조부분으로 이루어져 있다!

2) 그러므로 Node class에는 먼저, 데이터 부분과 참조부분을 만들어주어야 하는데, 우선 우리의 목표는 어디까지나 Node의 기능을 구현하는 것이다.

3) Node의 데이터 조회, 데이터 바꾸기와 같은 기능, 그리고 참조를 어디로 하는지 등이필요할 것이다!

class Node_mine():
    # 생성자에는 우선적으로 노드의 component들을 필수요소로 넣어줘야할 것이다.
    # 여기서 처음 부터 next를 argument에서 빼 놓은 이유는?
    # 이어져 있기 때문에 다음 노드를 바로 참조하면 되기 때문에 argument로 넣어줄 필요는 없다.
    # 즉, 우리가 마음대로 4번째 노드를 1번째노드로 참조하게끔하는 것은 linked list의 정의를 벗어나므로
    # 참조부분을 Node를 생성하면서부터 지정할 필요는 없다는 것이다.

    def __init__(self, data):
        self.__data=data
        self.__next=None

    # 소멸자: 객체가 메모리에서 사라질때 반드시 한번은 호출해 주는 것
    def __delete__(self):
        print("{} is deleted".format(self.__data))

    @property
    def get_data(self):
        return self.__data

    @get_data.setter
    def get_data(self, data):
        self.__data=data

    @property
    def get_next(self):
        return self.__next

    @get_next.setter
    def get_next(self, nt):
        self.__next=nt

• node 정의 및 생성

n1=Node_mine(5)

• node의 value 출력

n1.get_data

### 결과
### 5

• node에 새로운 값 할당

n1.get_data=3

• 변경된 값을 제대로 할당 받았는지 확인

  n1.get_data
  ### 결과
  ### 3

현업에서 사용하는 linked list라 함은 dummy duable linked list를 의미하고, 아래에서의 single linked list에서 single이 의미하는 것은 참조가 하나 즉 한개의 방향만을 참조하고 duable은 양방향을 참조한다.

Singel Linked list

Instance Member

1. head
   • 리스트의 첫번째 노드를 가리킨다.
2. d_size
   • 리스트의 요소 개수

class SingleLinkedList:
    def __init__(self):
        self.head = None
        self.d_size = 0

    def empty(self):
        if self.d_size==0:
            return True
        else :
            return False

    def size(self):
        return self.d_size

    def add(self, data):
        new_node=Node_mine(data)

        # 아래에서와 같이 단방향으로 이루어져 있고, 기존에 있던 Node를 새로운 Node의 다음으로 참조시켜준 뒤에, SingleLinkedList 클래스의 head값에는 새로운 Node를 추가해준다.
        new_node.next=self.head
        self.head=new_node

        self.d_size+=1

    def search(self, target):
        cur=self.head
        while cur :
            if cur.data == target :
                return cur
            else :
                cur=cur.next
        return cur

    def delete(self):
        # head에 있는 값을 지울것이므로 head값을 기존의 head의 다음 값으로 바꾸어주면 garbage collector에 의해서 사라지게 된다.
        self.head=self.head.next
        self.d_size-=1

    def traverse(self):
        cur=self.head
        while cur:
            yield cur
            cur=cur.next

Queue(큐)

• array와 함께 가장 쉬운 자료구조 중 하나
  • 컴퓨터에서 가장 핵심적인 OS(운영체제)에서도 많이 사용되며, 인터넷에서도 네트워크 기능에서도 많이 사용된다.

1. Queue 구조

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

• 출처: http://www.stoimen.com/blog/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

2. 알아둘 용어

• Enqueue: 큐에 데이터를 넣는 기능
• Dequeue: 큐에서 데이터를 꺼내는 기능
• Visualgo 사이트에서 시연해보며 이해하기 (enqueue/dequeue 만 클릭해보며): https://visualgo.net/en/list

3. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
• 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
  • Queue(): 가장 일반적인 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

일반적인 큐 외에 다양한 정책이 적용된 큐들이 있음

3.1. Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))

import queue

data_queue = queue.Queue()
data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize()

결과

2

data_queue.get()

결과

'funcoding'

data_queue.qsize()

결과

1

data_queue.get()

결과

'funcoding'

결과

1

data_queue.qsize()

결과

0

3.2. LifoQueue()로 큐 만들기 (LIFO(Last-In, First-Out))

import queue
data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize()

결과

2

그냥 Queue 구조가 아닌 Lifo Queue이기 때문에 마지막에 추가해 준 1이 출력으로 나온다.

data_queue.get()

결과

1

3.3. PriorityQueue()로 큐 만들기

import queue

data_queue = queue.PriorityQueue()

아래에서 보는 것과 같이 우선 순위와 값을 튜플형태로 같이 넣어준다. 우선순위는 숫자가 낮을 수록 높은 우선 순위를 지닌다.

data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "china"))

data_queue.qsize()

결과

3

data_queue.get()

우선순위가 제일 높은 제일 낮은 숫자인 5를 지닌 값 1이 출력된다.

(5, 1)

data_queue.get()

그 다음 우선 순위인 10을 지닌 korea가 출력된다.

(10, "korea")

참고: 어디에 Queue가 많이 쓰일까?

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용된다. (운영체제 참조)

Queue의 경우에는 장단점 보다는 (특별히 언급되는 장단점이 없음), 큐의 활용 예로 프로세스 스케쥴링 방식을 함께 이해해두는 것이 좋음

4. 프로그래밍 연습

• 연습1: 리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현해보기

queue_list = list()

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

• 위에서 만든 queue_list 안에 0~9까지의 수를 넣는다.

for index in range(10):
    enqueue(index)

len(queue_list)

결과

10

dequeue()

결과

• FIFO 구조이므로 제일 먼저 들어간 0이 출력된다.

0

파이썬 리스트를 이용한 큐 구현

• 위에서 만들었던 function들을 이용하여 좀더 많은 기능이 포함되어 있는 하나의 class로 Queue를 구현해 볼 것이다.

• Python list 자료형의 pop 메서드를 통해 dequeue를 구현할 것이다.

Enqueue

class Queue:
    def __init__(self):
        self.container=list()

    def empty(self):
#         if self.container is None:
        if not self.container:
            return True
        return False

    def enqueue(self, data):
        self.container.append(data)


    def dequeue(self):
        return self.container.pop(0)

    def peek(self):
        return self.container[0]

q=Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

while not q.empty():
    print(q.dequeue(), end='  ')

결과

1 2 3 4 5

single linked list를 이용해 Queue를 구현

ADT

• Queue.empty() -> Boolean

  • Queue가 비어있으면 True, 아니면 False

• Queue.enqueue(data) -> None

  • Queue의 맨 뒤에 데이터를 쌓는다.

맨 처음 enqueue 한 데이터는 front에 위치하고 최근에 추가로 삽입해준 데이터는 rear로 위치시킨다. 각각의 Node는 next로 연결을 시켜준다.

먼저 새로운 Node를 추가해주기 위해서는 현재 self.rear.next를 new_node를 가리키도록하고, self.rear를 new_node로 설정해주면 된다.

• Queue.dequeue() -> data
  • Queue 맨 앞의 데이터를 삭제하면서 반환

우선 Dequeue를 하면 제일 먼저 추가해놓았던 데이터의 값을 출력해주면 해당 Node를 제거해 주어야하므로, self.front의 데이터를 cur라는 변수에 따로 저자해 주는데, Node가 하나일때를 생각해 보면 self.front와 self.rear가 동일하므로 먼저 self.rear를 None으로 만들어준다. 그리고 나서 cur에 self.front를 할당해주고, self.front는 self.front.next를 할당해주며, cur.data를 출력해주면 된다.

• Queue.peek() -> data
  • Queue 맨 앞 데이터를 반환

class Node:
    def __init__(self, data):
        self.__data = data
        self.__next = None

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        self.__data=data

    @property
    def next(self):
        return self.__next

    @next.setter
    def next(self, n):
        self.__next=n

class LQueue:
    def __init__(self):
        self.front=None
        self.rear=None

    def empty(self):
        if self.front is None:
            return True
        return False

    def enqueue(self, data):
        new_node=Node(data)
        if self.empty():
            self.front=new_node
            self.rear=new_node
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.empty():
            return None

        if self.front is self.rear:
            self.rear = None
        cur = self.front
        self.front = self.front.next
        return cur.data

    def peek(self):
        return self.front.data

q = LQueue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

while not q.empty():
    print(q.dequeue(), end='  ')

결과

1 2 3 4 5