sm-stack의 개발 이야기

힙은 우선 순위가 존재하는 데이터를 처리하기 위한 큐 구조 중 하나이다. 우선순위가 높은 자료부터 꺼내서 빠르게 처리하기 위해 만들어졌다. 우선 순위가 있는 데이터의 예로는 대표적으로 OS에서 프로세스의 처리 과정이 있다. 우리가 사용하는 Windows, Linux 등 모든 OS에서는 프로세스의 우선순위를 부여할 수 있는 기능이 존재한다. 만약 CPU를 많이 차지하고, 처리하는데에 오래 걸리는 작업이 있다면 우선순위를 낮춰서 CPU가 한가할 때 작업을 처리할 수 있도록 한다. 우리가 힙이라고 부를 수 있는 구조의 조건으로는 두 가지가 있다. 1) 노드(node)들이 완전 이진 트리 구조를 가져야 한다. 2) 노드들이 우선순위에 따라 오름/내림차순으로 배열되어 있어야 한다. 1)의 완전 이진 트리 구조는 ..

개발 Recording/Python 2022. 6. 7. 21:41

파이썬에 내장된 배열리스트는 사용자 경험에 최적화되어 있는 편이라, 연결리스트의 대부분의 기능들이 포함되어 있다. 그러나 하부가 배열로 구성되어 있기 때문에, 우리에게 드러나진 않지만 시간 복잡도 및 작업 부담 측면에서 여러 가지 비효율이 존재한다. (ex. 배열 중간에 있는 원소의 삽입 및 삭제에서 원소들을 하나씩 옮겨줘야 하기 때문에 작업 부담이 커짐) 파이썬에서도 연결리스트를 구현할 수 있다. 우선 다음과 같이 class를 사용하여 연결리스트에 사용될 노드 객체를 정의한다. class ListNode: def __init__(self, newItem, nextNode): self.item = newItem self.next = nextNode 이후 이 ListNode 객체를 이용하여 연결리스트를 구..

개발 Recording/Python 2022. 6. 7. 12:46