파이썬 자료구조 정리(1)

자료구조

정의

• 대량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터의 구조를 의미한다.
• 데이터 특성에 따라서, 체계적인 데이터 구조화가 필요하며, 이러한 데이터 구조는 코드의 효율성, 성능을 결정한다.

종류

• 대표적인 자료구조로는 배열(Array), 스택(Stack), 큐(Queue), 링크드 리스트(Linked List), 해쉬 테이블(Hash Table),
• Python에서는 대표적으로 List, tuple, set, dictionary가 존재하며, 위 자료구조 대부분을 모두 구현이 가능하다.

 

배열(Array)

배열은 같은 종류의 데이터를 순차적으로 저장하는 자료구조이다. python에서는 list로 구현이 되어있다.

• index를 통해 직접 접근이 가능하다
• 장점 : 빠른 접근이 가능하다는 점이다
• 단점 : 데이터 추가와삭제에 비용이 많이 사용된다는 점이다. 데이터 추가 시, 공간이 많이 필요하며, 삭제 시 빈공간이 생겨 이를 관리해주어야 합니다. 길이 조절이 어렵다는 단점이 있다

# 1차원 배열 = 리스트
data = [1, 2, 3, 4, 5]
string1 = 'Hello World'
print(data[3]) # 4 출력
print(string1[3]) # l 출력

# 2차원 배열
data2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(data[1][0]) # 4 출력

 

특정 Alphabet의 빈도수 측정 함수

특정 데이터 세트에서 특정한 알파벳이 몇번이나 사용되었는지를 찾아보는 함수를 작성해보자

def find_alphabet(dataset, alphabet):
    count = 0
    for data in dataset:
        for i in range(len(data)):
            if data[i] == alphabet:
                count += 1
    print(count)

 

큐(Queue)

먼저 넣은 데이터를 가장 먼저 꺼내는 데이터 구조로, FIFO(First-In, First-Out : 선입선출) 또는 LILO(Last-In, Last-Out) 방식을 사용한다.

기능 

• Enqueue : 큐에 데이터를 넣는 기능을 의미한다. python list의 append() 메서드와 유사하다.
• Dequeue : 큐에서 데이터를 꺼내는 기능을 의미한다. python list의 pop(0) 메서드와 유사하다.

종류

python에서는 queue라이브러리를 제공한다. 하지만 대부분의 큐와 관련된 자료구조는 list를 통해 구현 가능하다.

import queue

 

Queue() 일반적인 큐 자료구조

  data_queue = queue.Queue()
  data_queue.put(1) # 1
  data_queue.put(2) # 1 - 2
  data_queue.put(3) # 1 - 2 - 3
  data_queue.get() # 1 출력
  data_queue.get() # 2 출력

 

LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(Stack과 동일)

  data_queue = queue.LifoQueue()
  data_queue.put(1) # 1
  data_queue.put(2) # 2 - 1
  data_queue.put(3) # 3 - 2 - 1
  data_queue.get() # 3 출력
  data_queue.get() # 2 출력

 

PriorityQueue() : 데이터마다 우선순위를 지정하여, 정렬된 큐로, 우선순위 높은 순으로 출력하는 자료 구조

  data_queue = queue.LifoQueue()
  data_queue.put(1) # 1
  data_queue.put(2) # 2 - 1
  data_queue.put(3) # 3 - 2 - 1
  data_queue.get() # 3 출력
  data_queue.get() # 2 출력

 

큐는 멀티 테스킹을 위한 프로세스 스케줄링 방식에 사용된다.

 

리스트로 Queue 구현

class ListQueue:
    def __init__(self):
        self.my_list = list()

    def put(self, element):
        self.my_list.append(element)

    def get(self):
        return self.my_list.pop(0)

    def qsize(self):
        return len(self.my_list)

간단하게 Enqueue기능을 가지는 put 메서드, Dequeue기능을 가진 get 메서드, 큐의 길이를 반환하는 qsize 메서드를 구현한 코드입니다.

리스트로 PriorityQueue 구현

class ListPriorityQueue:
    def __init__(self):
        self.my_list = list()

    def put(self, element):
        self.my_list.append(element)
        self.my_list.sort(key=lambda x: x[0])

    def get(self):
        return self.my_list.pop(0)

    def qsize(self):
        return len(self.my_list)

list의 메소드 중 하나인, sort를 이용하여 구현하였습니다. lambda함수를 사용하여 첫 번째 원소가 작은 순서로 우선순위를 정렬하였습니다.