코린이의 개발 일지

안녕하세요 폴라민입니다. 오늘은 자료구조로 스택을 구현하는 내용을 가지고 왔습니다. 저도 스택을 직접 구현해보는 것은 이번 자료구조 수업을 들으면서 처음 해봤습니다. 매번 리스트, 벡터 등등 자료구조를 가져다 쓰기만 해봤죠. 막상 구현하려고 하면 막막하지만 개념만 잘 이해하고 있으면 그리 어렵지 않아요! 그럼 시작해 보겠습니다. # include # include #defineMAX_STACK_SIZE 100 #define True 1 #define False 0 typedef char Element; typedef int Bool; typedef struct{ Element stackArr[MAX_STACK_SIZE]; int top; } Stack; Stack *Create(void) { Stack ..

힙이란? → 이진트리의 한 종류 (이진 힙 - binary heap 이라고도 부른다.) 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙 (max heap) 최소 힙 (min heap) 완전 이진트리여야 함 → 재귀적으로도 정의 된다. (어느 노드를 루트로 하는 서브트리도 모두 최대 힙) → 왼쪽과 오른쪽 자식을 비교하는 기준은 없다. 이러한 개념을 바탕으로 힙 연산을 코드 구현 해보자. 먼저 연산을 정의하자면 init() - 빈 최대 힙을 생성 insert(item) - 새로운 원소를 삽입 remove() - 최대 원소 (root node) 를 반환 (그리고 동시에 이 노드를 삭제) 배열을 이용한 이진 트리의 표현 노드 번호 m을 기준으로 왼쪽 자식의 번호 : 2*m 오른쪽 자식의..

우선 이진 탐색 트리란, 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 (단, 중복되는 데이터 원소는 없는 것으로 가정) 1. 정렬된 배열을 이용한 이진 탐색과 이진 탐색 트리의 비교 이진 탐색 트리의 장점 데이터 원소의 추가, 삭제가 용이 이진 탐색 트리의 단점 공간 소요가 크다 항상 O(logn)의 탐색 복잡도를 가지는 것이 아니다. 2. 이진 탐색 트리의 추상적 자료구조 데이터 표현 - 각 노드는 (key, value) 의 쌍으로 키를 이용해서 검색 가능 보다 복잡한 데이터 레코드로 확장 가능 연산의 정의 insert (key, data) - 트리에 주어진 데이터 원소를 추가 r..

이진 트리의 추상적 자료구조 연산의 정의 size() - 현재 트리에 포함되어 있는 노드의 수를 구함 depth() - 현재 트리의 깊이를 구함 순회(travelsal) 우선 size와 depth를 구현하는 이진트리 코드를 작성해 보겠습니다. class Node: def __init__(self, item): self.data = item self.left = None self.right = None def size(self): l = self.left.size() if self.left else 0 r = self.right.size() if self.right else 0 return l + r + 1 def depth(self): l = self.left.depth() if self.left els..