Social Developer

어제보다 한 걸음 더

CS/Data Structure

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository 이진탐색트리(Binary Search Tree) 이진 탐색(Binary Search) + 연결리스트(LinkedList) 이진 탐색 탐색에 소요되는 시간복잡도 $$ O(log_2N) $$ 연결리스트 삽입, 삭제의 시간복잡도 O(1) but 탐색하는 시간 복잡도 O(N) 이 2가지를 합해 장점을 모두 얻는 것이 이진탐색트리이다. 이진탐색트리의 특징 각 노드의 자식이 2개 이하(이진 트리) 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 중위순회(in-order) 방식(왼쪽 - 루트 - 오른쪽) 구조 -> 정렬된 순서를 읽을 수 있음 중복값 노드는 존재하지 않음 중복이 ..

2021. 4. 20.

CS/Data Structure

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository 우선순위 큐(Priority Queue), 힙(Heap) 우선순위 큐(Priority Queue) 우선순위의 개념을 큐에 도입한 자료구조 우선순위 큐를 위해 Heap 자료구조가 만들어졌다. 데이터들이 우선순위를 가지고 있음. 우선순위가 높은 데이터가 먼저 나감 언제 사용할까? 시뮬레이션 시스템 작업 스케줄링 수치해석 계산 네트워크 트래픽 제어 ex) 컴퓨터에서는 우선순위 개념이 종종 필요할 때가 있다. 예를 들면, 운영 시스템에서 시스템 프로세스는 응용 프로세스보다 더 높은 우선순위를 갖는다. 따라서 자료구조에서도 이러한 우선순위를 지원하는 것이 필요하다. 출처: https://lip..

2021. 4. 20.

CS/Data Structure

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다. jisikTank CS지식 Git Repository 트리(Tree) 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조 1개 이상의 노드를 갖는 집합으로 다음의 조건 만족한다. 루트(root) 노드가 존재 트리의 부분트리(Sub Tree) 또한 트리 구조를 따름 사이클(cycle)이 존재하지 않음 트리(Tree)의 활용 폴더 구조 DBMS 검색 엔진 ... Union&Find -> 사이클 판별 문제 최소 신장 트리(Minimum Spanning Tree) 최소공통조상(Lowest Common Ancestor) 트리(Tree)의 용어 루트 노드(Root Node) 트리의 최상위 노드. 유일하다. 깊이(Depth) 루트 노드에서 해당..

2021. 4. 17.