Python 자료구조

배열(Array)

• 파이썬(Python)에서 다음과 같이 배열을 초기화할 수 있다.

# [0, 0, 0, 0, 0]
n = 5
arr = [0] * n
print(arr)

# [0, 1, 2, 3, 4]
n = 5
arr = [i for i in range(n)]
print(arr)

[0, 0, 0, 0, 0]
[0, 1, 2, 3, 4]

n = 3
m = 5
arr = [[0] * m for i in range(n)]
print(arr)

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

n = 3
m = 5
arr = [[i * m + j for j in range(m)] for i in range(n)]
print(arr)

[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]

n = 3
m = 5
arr1 = [[0] * m] * n
arr2 = [[0] * m for i in range(n)]

arr1[1][3] = 7
arr2[1][3] = 7

print(arr1)
print(arr2)

[[0, 0, 0, 7, 0], [0, 0, 0, 7, 0], [0, 0, 0, 7, 0]]
[[0, 0, 0, 0, 0], [0, 0, 0, 7, 0], [0, 0, 0, 0, 0]]

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
print(arr)

[0, 1, 2, 3, 4, 5, 6, 7, 8]

연결 리스트(Linked List)

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


class LinkedList:
    def __init__(self):
        self.head = None

    # 가장 뒤에 노드 삽입
    def append(self, data):
        # 헤드(head)가 비어있는 경우
        if self.head == None:
            self.head = Node(data)
            return
        # 마지막 위치에 새로운 노드 추가
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    # 모든 노드를 하나씩 출력
    def show(self):
        cur = self.head
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

    # 특정 인덱스(index)의 노드 찾기
    def search(self, index):
        node = self.head
        for _ in range(index):
            node = node.next
        return node

    # 특정 인덱스(index)에 노드 삽입
    def insert(self, index, data):
        new = Node(data)
        # 첫 위치에 추가하는 경우
        if index == 0:
            new.next = self.head
            self.head = new
            return
        # 삽입할 위치의 앞 노드
        node = self.search(index - 1)
        next = node.next
        node.next = new
        new.next = next

    # 특정 인덱스(index)의 노드 삭제
    def remove(self, index):
        # 첫 위치를 삭제하는 경우
        if index == 0:
            self.head = self.head.next
            return
        # 삭제할 위치의 앞 노드
        front = self.search(index - 1)
        front.next = front.next.next


linked_list = LinkedList()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    linked_list.append(data)

print("전체 노드 출력:", end=" ")
linked_list.show()

linked_list.insert(4, 4)
print("\n전체 노드 출력:", end=" ")
linked_list.show()

linked_list.remove(7)
print("\n전체 노드 출력:", end=" ")
linked_list.show()

linked_list.insert(7, 2)
print("\n전체 노드 출력:", end=" ")
linked_list.show()

전체 노드 출력: 3 5 9 8 5 6 1 7 
전체 노드 출력: 3 5 9 8 4 5 6 1 7 
전체 노드 출력: 3 5 9 8 4 5 6 7 
전체 노드 출력: 3 5 9 8 4 5 6 2 7 

파이썬에서의 리스트(List)

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(arr[4]) # 인덱싱(indexing)

# 저장(storing)
arr[7] = 10

# 뒤에 붙이기(append)
arr.append(10)
print(arr)

# 뒤에서 꺼내기(pop)
arr.pop()
print(arr)

# 길이(length)
print(len(arr))

# 배열 비우기(clear)
arr.clear()
print(arr)

4
[0, 1, 2, 3, 4, 5, 6, 10, 8, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 10, 8, 9]
10
[]

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
new_arr = arr[2:7] # 슬라이싱(slicing)
print(new_arr)

arr1 = [0, 1, 2, 3, 4]
arr2 = [5, 6, 7, 8, 9]
arr1.extend(arr2) # 확장(extend)
print(arr1)

arr = [0, 1, 2, 3, 4]
arr.insert(3, 7) # 삽입(insertion)
print(arr)

del arr[3] # 삭제(delete)
print(arr)

data = {7, 8, 9}
arr = list(data) # 다른 자료구조로 리스트 만들기
print(arr)

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

arr = [0, 1, 2, 3, 4]

print(3 in arr) # 존재 여부(in)
print(7 not in arr) # 비존재 여부(not in)

arr.pop(1) # 인덱스 1에 해당하는 원소 꺼내기(pop)
print(arr)

arr.remove(3) # 리스트의 특정 원소 삭제(remove)
print(arr)

new_arr = arr.copy() # 복제(copy)
print(new_arr)

True
True
[0, 2, 3, 4]
[0, 2, 4]
[0, 2, 4]

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

print(min(arr)) # 최소(min)
print(max(arr)) # 최대(max)

for x in arr: # 원소 순회(iteration)
    print(x, end=" ")
print()

print(arr * 2) # 리스트 반복하여 곱하기(multiply)

arr.sort() # 정렬(sorting)
print(arr)

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

스택(Stack) - 리스트 자료형을 이용한 구현

• 가장 마지막에 들어온 원소가 가장 먼저 추출되는 자료구조다.

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        # 마지막 위치에 원소 삽입
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return None
        # 마지막 원소 추출
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            return None
        # 마지막 원소 반환
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0


stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)

while not stack.is_empty():
    print(stack.pop())

2
4
6
5
2
7
9

스택(Stack) - 연결 리스트를 이용한 구현

• 가장 마지막에 들어온 원소가 가장 먼저 추출되는 자료구조다.

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


class Stack:
    def __init__(self):
        self.head = None

    # 원소 삽입
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # 원소 추출하기
    def pop(self):
        if self.is_empty():
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    # 최상위 원소(top)
    def top(self):
        if self.is_empty():
            return None
        return self.head.data

    # 먼저 추출할 원소부터 출력
    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next

    # 스택이 비어있는지 확인
    def is_empty(self):
        return self.head is None


stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)
stack.show()
print()

while not stack.is_empty():
    print(stack.pop())

2 4 6 5 2 7 9 
2
4
6
5
2
7
9

큐(Queue) - 연결 리스트를 이용한 구현

• 가장 먼저 삽입된 원소가 먼저 추출되는 자료구조다.

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        node = Node(data)
        if self.head == None:
            self.head = node
            self.tail = node
        # 꼬리(tail) 위치에 새로운 노드 삽입
        else:
            self.tail.next = node
            self.tail = self.tail.next

    def dequeue(self):
        if self.head == None:
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


queue = Queue()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    queue.enqueue(data)

print("\n전체 노드 출력:", end=" ")
queue.show()

print("\n[원소 삭제]")
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

print("[원소 삽입]")
queue.enqueue(2)
queue.enqueue(5)
queue.enqueue(3)

print("전체 노드 출력:", end=" ")
queue.show()

전체 노드 출력: 3 5 9 8 5 6 1 7 
[원소 삭제]
3
5
9
[원소 삽입]
전체 노드 출력: 8 5 6 1 7 2 5 3 

• 큐(queue)의 구현 방식에 따른 연산 속도를 비교할 수 있다.

import time

data_list = [i for i in range(100000)]

start_time = time.time()

queue = []
for data in data_list:
    queue.append(data)
while queue:
    queue.pop(0)

print(f"Elapsed time: {time.time() - start_time} seconds.")
print(queue)

start_time = time.time()

queue = Queue()
for data in data_list:
    queue.enqueue(data)
while queue.head != None:
    queue.dequeue()

print(f"Elapsed time: {time.time() - start_time} seconds.")
queue.show()

Elapsed time: 3.0279040336608887 seconds.
[]
Elapsed time: 0.7380266189575195 seconds.

덱(Deque) - 파이썬 라이브러리를 이용한 구현

• 왼쪽과 오른쪽 모두에서 삽입과 삭제할 수 있는 자료구조다.

from collections import deque


d = deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
print(d)

while d:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
print(d)

while True:
    print(d.pop())
    if not d:
        break
    print(d.popleft())
    if not d:
        break

deque([1, 2, 3, 4, 5, 6, 7, 8])
1
2
3
4
5
6
7
8
deque([8, 7, 6, 5, 4, 3, 2, 1])
1
8
2
7
3
6
4
5

덱(Deque) - 연결 리스트를 이용한 구현

• 왼쪽과 오른쪽 모두에서 삽입과 삭제할 수 있는 자료구조다.

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def appendleft(self, data):
        node = Node(data)
        if self.front == None:
            self.front = node
            self.rear = node
        else:
            node.next = self.front
            self.front.prev = node
            self.front = node
        self.size += 1

    def append(self, data):
        node = Node(data)
        if self.rear == None:
            self.front = node
            self.rear = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self.size += 1

    def popleft(self):
        if self.size == 0:
            return None
        # 앞에서 노드 꺼내기
        data = self.front.data
        self.front = self.front.next
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.front == None:
            self.rear = None
        else:
            self.front.prev = None
        self.size -= 1
        return data

    def pop(self):
        if self.size == 0:
            return None
        # 뒤에서 노드 꺼내기
        data = self.rear.data
        self.rear = self.rear.prev
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.rear == None:
            self.front = None
        else:
            self.rear.next = None
        self.size -= 1
        return data

    def front(self):
        if self.size == 0:
            return None
        return self.front.data

    def rear(self):
        if self.size == 0:
            return None
        return self.rear.data

    # 앞에서부터 원소 출력
    def show(self):
        cur = self.front
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


d = Deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
d.show()

print()
while d.size != 0:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
d.show()

print()
while True:
    print(d.pop())
    if d.size == 0:
        break
    print(d.popleft())
    if d.size == 0:
        break

1 2 3 4 5 6 7 8 
1
2
3
4
5
6
7
8
8 7 6 5 4 3 2 1 
1
8
2
7
3
6
4
5

이진 탐색 트리(Binary Search Tree)

from collections import deque


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def search(self, node, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.key == key:
            return node

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            return self._search(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            return self._search(node.right, key)

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            node.left = self._insert(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            node.right = self._insert(node.right, key)

        return node

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return None

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            node.left = self._delete(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            node.right = self._delete(node.right, key)
        # 삭제할 노드를 찾은 경우
        else:
            # 왼쪽 자식이 없는 경우
            if node.left is None:
                return node.right
            # 오른쪽 자식이 없는 경우
            elif node.right is None:
                return node.left
            # 왼쪽과 오른쪽 자식 모두 있는 경우
            node.key = self._get_min(node.right)
            node.right = self._delete(node.right, node.key)

        return node

    def _get_min(self, node):
        key = node.key
        while node.left:
            key = node.left.key
            node = node.left
        return key

    def preorder(self):
        self._preorder(self.root)

    def _preorder(self, node):
        if node:
            print(node.key, end=' ')
            self._preorder(node.left)
            self._preorder(node.right)

    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.key, end=' ')
            self._inorder(node.right)

    def postorder(self):
        self._postorder(self.root)

    def _postorder(self, node):
        if node:
            self._postorder(node.left)
            self._postorder(node.right)
            print(node.key, end=' ')

    def levelorder(self):
        return self._levelorder(self.root)

    def _levelorder(self, node):
        if node is None:
            return

        result = []

        queue = deque()
        queue.append((0, node))  # (level, node)

        while queue:
            level, node = queue.popleft()
            if node:
                result.append((level, node.key))
                queue.append((level + 1, node.left))
                queue.append((level + 1, node.right))

        for level, key in result:
            print(f"level: {level}, key: {key}")

    def to_list(self):
        return self._to_list(self.root)

    def _to_list(self, node):
        if node is None:
            return []
        return self._to_list(node.left) + [node.key] + self._to_list(
            node.right)


arr = [7, 4, 5, 9, 6, 3, 2, 8]
bst = BinarySearchTree()
for x in arr:
    bst.insert(x)
print('전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(7)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(4)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(3)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

print(bst.to_list())

전위 순회: 7 4 3 2 5 6 9 8 
중위 순회: 2 3 4 5 6 7 8 9 
후위 순회: 2 3 6 5 4 8 9 7 
[레벨 순회]
level: 0, key: 7
level: 1, key: 4
level: 1, key: 9
level: 2, key: 3
level: 2, key: 5
level: 2, key: 8
level: 3, key: 2
level: 3, key: 6

전위 순회: 8 4 3 2 5 6 9 
중위 순회: 2 3 4 5 6 8 9 
후위 순회: 2 3 6 5 4 9 8 
[레벨 순회]
level: 0, key: 8
level: 1, key: 4
level: 1, key: 9
level: 2, key: 3
level: 2, key: 5
level: 3, key: 2
level: 3, key: 6

전위 순회: 8 5 3 2 6 9 
중위 순회: 2 3 5 6 8 9 
후위 순회: 2 3 6 5 9 8 
[레벨 순회]
level: 0, key: 8
level: 1, key: 5
level: 1, key: 9
level: 2, key: 3
level: 2, key: 6
level: 3, key: 2

전위 순회: 8 5 2 6 9 
중위 순회: 2 5 6 8 9 
후위 순회: 2 6 5 9 8 
[레벨 순회]
level: 0, key: 8
level: 1, key: 5
level: 1, key: 9
level: 2, key: 2
level: 2, key: 6
[2, 5, 6, 8, 9]

힙(Heap)

• 우선순위 큐(priority queue) 구현 목적으로 사용된다.

class Heap(object):
    def __init__(self):
        # 첫번째 원소는 사용하지 않음
        self.arr = [None]

    # 원소 삽입(push)
    def push(self, x):
        # 마지막 위치에 원소를 삽입
        self.arr.append(x)
        # 첫 원소인 경우 종료
        if len(self.arr) == 2:
            return
        # 값의 크기를 비교하며 부모를 타고 올라감
        i = len(self.arr) - 1
        while True:
            parent = i // 2
            # 작은 값을 부모 쪽으로 계속 이동
            if 1 <= parent and self.arr[parent] > self.arr[i]:
                self.arr[parent], self.arr[i] = self.arr[i], self.arr[parent]
                i = parent
            else:
                break

    # 원소 추출(pop)
    def pop(self):
        # 마지막 원소
        i = len(self.arr) - 1
        # 남은 원소가 없다면 종료
        if i < 1:
            return None
        # 루트 원소와 마지막 원소를 교체하여, 마지막 원소 추출
        self.arr[1], self.arr[i] = self.arr[i], self.arr[1]
        result = self.arr.pop()
        # 루트(root)에서부터 원소 정렬
        self.heapify()
        return result

    # 루트(root)에서부터 자식 방향으로 내려가며 재정렬
    def heapify(self):
        # 남은 원소가 1개 이하라면 종료
        if len(self.arr) <= 2:
            return
        # 루트 원소
        i = 1
        while True:
            # 왼쪽 자식
            child = 2 * i
            # 왼쪽 자식과 오른쪽 자식 중 더 작은 것을 선택
            if child + 1 < len(self.arr):
                if self.arr[child] > self.arr[child + 1]:
                    child += 1
            # 더 이상 자식이 없거나, 적절한 위치를 찾은 경우
            if child >= len(self.arr) or self.arr[child] > self.arr[i]:
                break
            # 원소를 교체하며, 자식 방향으로 내려가기
            self.arr[i], self.arr[child] = self.arr[child], self.arr[i]
            i = child

arr = [9, 1, 5, 4, 3, 8, 7]
heap = Heap()

for x in arr:
    heap.push(x)

while True:
    x = heap.pop()
    if x == None:
        break
    print(x, end=" ")

1 3 4 5 7 8 9 

import random
import time


# N개의 무작위 데이터 생성
arr = []
n = 100000
for _ in range(n):
	arr.append(random.randint(0, 1000000))

# 시간 측정 시작
start_time = time.time()

# 힙에 모든 원소 삽입
heap = Heap()
for x in arr:
	heap.push(x)

# 힙에서 모든 원소 추출
result = []
while True:
	x = heap.pop()
	if x == None:
		break
	result.append(x)

# 시간 측정 종료
print(f"Elapsed time: {time.time() - start_time} seconds.")

# 오름차순 정렬 여부 확인
ascending = True
for i in range(n - 1):
	if result[i] > result[i + 1]:
		ascending = False
print("Sorted:", ascending)

# 가장 작은 5개 원소와 가장 큰 5개 원소 출력
print(result[:5])
print(result[-5:])

Elapsed time: 2.883451223373413 seconds.
Sorted: True
[5, 49, 64, 69, 77]
[999955, 999959, 999970, 999971, 999994]