전체 글533 [자료구조] 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리 (Binary Search Tree) 특정 키 값에 해당하는 노드를 빠르게 찾는 것이 주된 기능 효율적인 자료 검색이 목적 조건 모든 노드는 유일한 키를 가짐(중복x) 왼쪽 서브트리 노드들 키 값 루트 노드 키 값 왼쪽, 오른쪽 서브트리 = 이진 탐색 트리 => 왼쪽 서브트리 키 중위 순회(InOrder) 방식으로 나열하면 키 값 크기대로 나열됨 1. 검색 연산 입력 값 현재 노드 값 : 오른쪽 서브트리로 이동 입력 값 = 현재 노드 값 : 검색 완료! 2. 삽입 연산 입력 값 현재 노드 값 : 오른쪽 서브트리로 이동.. 2020. 9. 15. [자료구조] 히프 (Heap) 히프 (Heap) 루트 노드가 언제나 그 트리의 최대값 혹은 최소값을 가지는 완전 이진 트리 최대 트리 : 노드의 키 값이 자식 노드 키 값보다 크거나 같음 최소 트리 : 노드의 키 값이 자식 노드 키 값보다 작거나 같음 힙 최초 구성 시 시간 복잡도 : O($n log {n}$) 우선순위 큐를 만드는데 사용! 트리의 최대값, 혹은 최소값을 반환하는 것이 주된 기능 1. 최대 히프 (Max Heap) 완전 이진 트리 & 최대 트리 부모 노드 키값 >= 자식 노드 키값 루트 노드 : 최대값 언제나 최대값이 반환됨 2. 최소 트리 (Min Heap) 완전 이진 트리 & 최소 트리 부모 노드 키값 2020. 9. 15. [자료구조] 이진 트리 순회(Traversal) 트리 순회(Traversal) 트리의 모든 노드를 한 번씩 방문하는 것을 의미 재귀 함수로 구현할 수 있다. 1. 전위 순회 (Preorder Traversal) 현재 노드를 먼저 방문 현재 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 public static void preorder(int index, int tree[]) { if(index < tree.length) { System.out.println(tree[index]);//현재 노드 출력 preorder(index*2,tree); preorder(index*2+1,tree); } } 결과 : 1 2 4 5 3 6 7 2. 중위 순회 (Inorder Traversal) 현재 노드를 중간에 방문 왼쪽 서브트리 방문 -.. 2020. 9. 15. [운영체제] 프로세스 동기화 ※출처 : TOPCIT 에센스 프로세스 동기화 2개 이상의 프로세스가 동시에 처리 중인 동일한 자료에 접근하여 변경하거나, 자료 조작 순서가 실행된 결과에 영향을 줄 때를 경합상태 (Race Condition) 이라고 한다. 경합 상태에서는 하나의 프로세스만 자료를 조작하도록 보호해야함 -> 프로세스 동기화 임계구역 (Critical Section) 다른 프로세스와 공유하는 자료를 변경하는 작업을 수행 한 번에 1개의 프로세스만이 접근 가능한 영역 do { entry section critical section //임계구역 exit section remainder section //잔류구역 }while(TRUE); 임계구역 문제 해결 방안의 3가지 조건 조건 설명 상호배제 (Mutual Exclu.. 2020. 9. 14. 이전 1 ··· 104 105 106 107 108 109 110 ··· 134 다음
