Algorithm 공부자료/기본 알고리즘 정리
-
알고리즘 기초 04) 힙 (Heap) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 12. 01:14
사전 개념 : 우선순위 큐 (Priority Queue) 자료 구조 우선 순위의 개념을 queue에 도입한 자료 구조이다. 데이터들이 우선 순위를 갖고 있으며, 우선 순위가 높은 데이터가 먼저 빠져나간다. 대표적인 사용처 : 시뮬레이션 시스템, 네트워크 트래픽 제어, CPU scheduling, 수치 해석적인 계산 등 구현 : list (array), linked list, heap 등으로 구현이 가능하며, 이 중 heap으로 구현하는 것이 가장 효율적이다. 개념 complete binary tree의 일종으로 우선순위 큐의 구현을 위해서 만들어진 자료 구조이다. 시간 복잡도 : O(logN) 여러 개의 값들 중에서 max 혹은 min value를 빠르게 탐색하기 위해서 만들어졌다. 중복된 값을 허용하지..
-
알고리즘 기초 03) 트리 (tree) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 12. 00:56
개념 node와 node를 연결하는 edge로 구성된 자료구조이다. 비선형 자료구조의 일종으로 계층 구조를 이룬다. tree 표현에 사용되는 용어 degree : 차수, 특정 노드의 자식 노드 수 height : 높이, root node에서 최하위 노드까지의 길이 level : 레벨, 각 층의 번호 - root node : level 1 tree vs graph : tree는 graph의 한 종류로써, cycle이 없는 일종의 connected graph이다. 대표적인 사용처 : 각종 탐색 Binary Tree (이진 트리) 최대 2개의 자식 노드를 갖는 트리 종류 1) Complete binary tree (완전 이진 트리) 2) Full binary tree (포화 이진 트리) 3) Skewed bi..
-
알고리즘 기초 02) 큐 (Queue) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 10. 02:07
개념 First In First Out (FIFO) 구조를 따르는 자료구조. 즉, 삽입하는 쪽과 삭제하는 쪽이 서로 반대에 위치 해 있다. 삽입하는 쪽 : rear 삭제하는 쪽 : front 라고 표현함. 삽입 연산을 enqueue, 삭제 연산을 dequeue라고 부름. overflow : queue의 용량이 다 차서 더 이상 enqueue할 수 없는 상태 underflow : queue에 data가 없어서 dequeue할 data가 없는 상태 대표적인 사용처 : CPU scheduling, data buffer, 대기 행렬 정리, 인쇄 작업 대기 목록, 자원을 공유하는 대부분의 경우 등 단점 : 데이터 삽입 후 계속 항목을 삭제 하다보면, 어느 순간 rear pointer와 front pointer가 ..
-
알고리즘 기초 01) 스택 (Stack) 자료 구조Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 10. 01:46
개념Last In First Out (LIFO) 형식을 따르는 자료구조. 즉, 가장 최근에 추가된 항목이 가장 먼저 제거될 항목일시적으로 data를 저장하기 위해서 사용한다. 대표적인 사용처 : 인터럽트의 처리, 수식의 계산, 서브 루틴의 복귀 번지 저장, 부트 프로그램 호출, 지역 변수 저장, 임시 데이터 백업 등 단점 : LIFO로 인한 우선순위 문제가 발생할 수 있다. 새로운 입력이 들어오면, botton에 있는 데이터는 계속 bottom에 있게된다. 연산pop : stack 가장 위의 항목을 제거한다.push : 인자를 stack 가장 위에 추가한다.peek : 제거하지는 않으면서, stack 가장 위의 항목을 출력한다.indexOf : 인자가 stack에 존재 하는지, 존재 한다면 stack의 ..