본문 바로가기

교육후 개인공부/알고리즘6

[알고리즘] 이진트리, 이진탐색트리 이진트리 BT, binary tree -각각의 노드의 자식 노드 수가 2개 이하로 구성되어 있는 트리 -정이진트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미한다. 완전이진트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미한다. 변질이진트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미한다. 포화이진트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미한다. 균형이진트리(balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리이다. map, set을 구성하는 레드블랙트리는 균형이진트리 중 하나이다. 이진탐색.. 2024. 1. 28.
[알고리즘] 그래프, 정점, 간선, 가중치, 트리 그래프 -정점과 간선으로 이루어진 집합들 정점(vertex) -노드라고도 부른다. 점이라고 생각하면된다. -그래프를 형성하는 기본단위이다. 간선(edge) -정점을 잇는 선을 의미한다. -관계, 경로 등이 될수있다. -단방향간선, 양방향간선이 있다. -indegree(들어오는간선), outdegree(에서 출발하는 간선, 나가는간선) 가중치 -정점과 정점 사이에 드는 비용 -시간이던, 돈이던, 트리 -나무를 뒤집은 구조를 가지고 있는 자료구조이다. -edge로 연결된 node의 집합이다. -자식노드와 부모노드로 이루어진 계층적인 구조를 가진다. -무방향그래프(방향성 없다) -사이클이 없는 자료구조 -트리는 그래프의 일종이다. -vertex -1 = edge -트리내의 어떤 노드와 노드까지의 경로는 반드시.. 2024. 1. 28.
[알고리즘] 큐(queue) 큐(queue) -리스트의 일종으로 끝부분으로 데이터가 삽입되고 앞부분에서는 데이터가 삭제되는 자료구조다. -선입선출 First-in First-out , FIFO -삽입하는 동작이 enqueue(인큐), 삭제하는 동작이 dequeue(데큐) 인큐는 큐의 끝부분에서 추가(push), 데큐는 큐의 앞부분에서 삭제(shift) -큐의 앞부분에 있는 요소를 확인할수 있는 기능을 피크(peek)라고 한다. function Queue(){ this.dataStore = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.back = back; this.toString = toString; this.empty = empty; } .. 2024. 1. 28.
[알고리즘] 스택 Stack 스택 Stack - 프링글스 과자통을 생각하자!!!!!! - 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질을 가졌다. 그런 자료구조이다 후입선출 last-in, first-out LIFO - push로 추가, pop으로 제거 - pop으로도 스택의 top에 있는 요소를 확인할수있지만, pop은 스택에서 영구적으로 요소를 꺼낸다. peek을 이용하면 top에 있는 요소를 제거하지 않고 내용만 확인할수있다. - 탑 요소의 위치와 새 요소를 추가할 위치는 top변수를 이용해 관리한다. - clear 프로퍼티는 스택의 모든 요소를 삭제한다. -length 프로퍼티는 스택에 포함된 요소의 수를 저장한다. -재귀, 진법변환, 회문 등에 이용된다. function Stack(){ this.dataStor.. 2024. 1. 28.

티스토리툴바