사진과 음악을 좋아하는 개발자 지망생의 블로그

1) 힙 (Heap) - 이진 트리의 한 종류 (이진 힙, binary heap) - 루트 (root) 노드가 언제나 최대값/최소값을 가짐 → 최대 힙(max heap), 최소 힙(min heap) - 완전 이진 트리여야 함 - 이진 탐색 트리와 조금 다른 특징을 가짐 → 서브트리보다 항상 큰 키를 갖고으며 위로 올라갈수록 큰 값을 가지지만, 왼쪽 서브트리와 오른쪽 서브트리 간 관계가 정의 되어있지 않다 2) 최대 힙(Max Heap)의 추상적 자료구조 ①연산의 정의 - __init__() : 빈 최대 힙 생성 - insert(item) : 새로운 원소를 삽입 - remove() : 최대 원소 (root node)를 반환과 동시에 해당 노드 삭제 ② 데이터 표현의 설계 - 노드번호 m을 기준으로 왼쪽 자..

1) 이진 트리(Binary Tree) ① 기본 이진 트리 - 모든 노드의 차수(degree)가 2 이하인 트리 - 트리는 child노드를 갖고 그 child 노드들로부터 부분트리를 가질 수 있기 때문에 본질적으로 재귀적인 성질이 있다. → 추가적으로 재귀적인 성질을 완성하기 위해 '빈트리도 이진트리이다'(터미널 조건)라는 정의도 필요하다. - 왼쪽 그림과 같이 한쪽으로 치우쳐진 트리도 이진 트리이다 (이진 트리 조건 충족) - 다만, 우리가 접하는 이진 트리는 한쪽으로 치우쳐진 트리보단 보통, 균형을 이룬(한쪽으로 치우쳐지지 않은) 트리가 더 많다. ② 포화 이진 트리 (Full Binary Tree) - 모든 리프 노드를 제외한 모든 레벨에서 노드들이 2개의 자식을 갖는 트리 - 높이가 n → 노드의..

1) 트리(Tree) - 정점(node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조 2) 트리 관련 용어 - 정점(node) : 데이터를 담고 있는 요소 - 간선(edge) : 노드와 노드를 잇는 연결선 - 뿌리(root) : 최상위 노드로 자식 노드만 가질 수 있는 노드 - 잎(leaf) : 최하위 노드로 자식 노드를 가질 수 없는 노드 - 부모(parent) : 연결된 두 노드 중 뿌리(root)에 가까운 노드 - 자식(child) : 연결된 두 노드 중 잎(leaf)에 가까운 노드 - 형제(sibling) : 같은 부모를 가진 노드 - 조상(ancestor) : 뿌리 방향으로 가며 만나는 노드들 - 후송(descendant) : 잎 방향으로 가며 만나는 노드들 - 수준(le..

1) 우선순위 큐 - 큐(Queue)가 FIFO(선입선출) 방식을 따르지 않고 원소들의 갖고 있는 우선순위에 따라 나오는 자료구조 - 대표적인 예로 '운영체제의 CPU 스케쥴러'가 있다 - 우선순위 큐는 두가지 방식으로 구현 가능하다 Enqueue 시 우선순위를 유지하도록 한다 Dequeue 시 우선순위가 높은 것을 선택하도록 한다 → 위 두가지 방식 중 'Enqueue 시 우선순위를 유지' 가 미세하게 유리하다. 왜냐하면 Dequeue 시 우선순위가 높은 것을 선택하도록 할 경우 모든 데이터에 대하여 다 살펴봐야하기 때문에 큐의 길이가 길어질 경우 시간적으로 불리하다. - 우선순위 큐는 선형 배열(Array, list)과 연결 리스트(linked list)를 이용하여 구현 가능하다 → 시간 소요 측면에..

1) 환형 큐(Circular Queue) - 컴퓨터 시스템 내에서 이용할 수 있는 자원이 한정적 → 큐의 길이를 한정하여 사용 - 배열로 큐 구현 시 길이에 비례한 시간복잡도를 가진 연산이 있음 - 위 두 문제 포함 큐 구현시 발생하는 문제들을 보완하기 위해 환형 큐(Circular Queue)를 사용 - 환형 큐(Circular Queue) → 정해진 개수의 저장 공간을 돌려가며 이 - Fornt : dequeue가 이뤄지는 index / rear : enqueue가 발생 index * 초기 상태 : front == rear 2) 환형 큐 자료구조 구현 ① 배열로 구현한 환형 큐 → front와 rear를 적절히 계산하여 배열을 환형으로 재활용 ② 배열로 구현한 환형 큐 연산 class Circula..

1) 큐(Queue) - 한쪽 끝에서 삽입이 이루어지고(인큐, Enqueue) 다른 한쪽에선 삭제 연산(디큐, Dequeue)만 이뤄지는 선형의 자료 구조 - 선입선출(FIFO, First In, First Out) 특징을 가지는 선형 자료구조 ex) 대기열 2) 큐(Queue) 자료구조 구현 ① 배열(array, list)을 이용하여 구현 → Python List 와 method들을 이용 class ArrayQueue : def size(self) :# 현재 큐에 들어 있는 데이터 원소의 수 return len(self.data) def isEmpty(self) :# 현재 큐가 비어 있는지를 판단 return self.size() == 0 def enqueue(self, item) :# 데이터 원소 i..

1) 스택(Stack) - 자료(Data element)를 단방향을 보관할 수 있는 (선형) 구조 - 단방향이므로 자료를 넣고(Push) 꺼낼 때(Pop) 한 쪽으로만 수행해야하는 제약이 있음 => 후입선출(LIFO) ※ Stack에서 발생하는 오류 - 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 → Stack Underflow - 꽉 찬 스택에 데이터 원소를 넣으려 할 때 → Stack Overflow 2) 스택의 추상적 자료구조 구현 ① 배열(array, list)을 이용하여 구현 → Python List 와 method들을 이용 class ArrayStack : def size(self) :# 현재 스택에 들어 있는 데이터 원소의 수 return len(self.data) def isEmpty(..

3) 양방향(Doubly) 연결 리스트 ① 양방향 연결 리스트 정의 - 단반향 리스트와 달리 앞과 뒤(양방향)으로 리스트 접근이 가능하다 def __init__(self, item) : self.data = item self.prev = None self.next = None - 삽입 및 정렬 연산에서 head 및 tail에서 연산할 시 리스트 처음과 끝에 Dummy Node를 둠으로써 양방향 연결 리스트를 형성한다 def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None self.head.next = self.tail# Doubly self.tail.prev = self..