Code IT/Data-Structure11 [자료구조] Topological Sort 위상 정렬 위상정렬 : 유향 그래프 (방향이 있는 그래프) 의 vertex를 edge들의 방향을 거스르지 않도록 나열하는 정렬 1. DFS와 Queue이용하여 DFS 한 값을 LIFO로 뽑아내는 방법 2. 진입 차수가 0인 vertex를 차례대로 삭제하며 Stack에 넣고 FIFO로 뽑아내는 방법 이 있는데, 나는 2를 사용했고, while 루프의 첫 for루프는 점들을 다 돌면서 진입 차수 indegree값이 0인 점을 보면 삭제 - list에 추가 하고 - 해당 점의 indegree를 -1 로 설정 두번째 for루프는 list에 추가된 점들이 가리키는 edge들(점들이 가지고 있는 변?)을 삭제한다. 점들이 가리키고 있는 점들의 indegree 값은 -1 해주면 되는 것 import java.io.*; .. 2021. 4. 3. [자료구조] Hashing 해싱 해싱 Hashing : 키 변환을 통해 원하는 레코드에 직접 접근할 수 있도록하는 자료구조 해싱 함수 : 레코드의 키 값을 이용해 레코드를 저장할 주소를 산출할 수 있는 일종의 식 - 제산법, 기수 변환법, 접는 법, 계수 분석법, 제곱법 등등 홈 주소 : 해싱 함수를 통해 계산되어 나온 주소 값 버킷 : 하나의 주소를 가지며, 한 개 이상의 레코드를 저장할 수 있는 공간 슬롯 : 한 개의 레코드를 저장할 수 있는 공간. 한 버킷 안에 여러 개의 슬롯이 있는 것 충돌 : 해싱 함수에 의해 계산된 홈 주소가 같은 경우에 벌어지는 현상 해싱 자료구조를 ArrayList로 구현 1. HashNode public class HashNode { int element; HashNode next; HashNode.. 2021. 4. 3. [자료구조] Binary Tree 이진 트리, Binary Search Tree 이진 탐색 트리 이진 트리 binary tree : 모든 노드들의 자식 노드가 두 개 이하인 트리. - 완전 이진 트리 complete binary tree : leaf node를 제외한 나머지 노드가 두 개의 자식 노드를 가지고 있는 상태의 이진 트리. - 포화 이진 트리 full binary tree : 모든 노드가 채워진 트리. (모든 층에 가능한 노드 수대로 노드가 다 채워진 이진 트리) 이진 탐색 트리 binary search tree : 삽입, 삭제 연산을 보다 효과적으로 작업하기 위해 만든 이진 트리. ( 왼쪽자식 < 부모 < 오른쪽 자식 ) 대로 크기가 정렬되어 있는 이진 트리. - 균형잡힌 이진 탐색 트리 balanced binary search tree : BST의 시간 복잡도를 개선, 높이를 유지.. 2021. 4. 3. [자료구조] Heap 힙 Heap : 최대 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진 트리 기반 자료구조. max heap : 부모노드는 자식노드보다 크다. min heap : 부모노드는 자식노드보다 작다. 최대 힙 구현하기 1.MaxHeap public class MaxHeap { public int[] elements; public int size; public int capacity; public MaxHeap CreateHeap(int capacity) { // 새로운 capacity의 힙 생성 MaxHeap mh = new MaxHeap(); mh.capacity = capacity; mh.size = 0; mh.elements = new int[mh.capacity + 1]; return mh;.. 2021. 4. 3. 이전 1 2 3 다음
