1. 쉘 정렬: 원소 비교 연산과 먼 거리의 이동을 줄이기 위해 서브리스트로 나누어 삽입 정렬을 반복 수행 2. 방법: 정렬에서 사용할 간격(interval) 결정 -> 첫번째 interval에 따라 서브리스트로 분할 -> 각 서브리스트에 대해 삽입 정렬 수행 -> ... -> 리스트 전체에 대해 삽입 정렬 수행(마지막 interval = 1) - 시간 복잡도: O(n^1.25) ---------------- 그림 설명 ---------- 3. ShellSort Algorithm shellSort(a[]) interval 1) do{ interval

1. 히프 정렬: 최대 히프를 이용한 정렬 기법 2. 방법: - 정렬할 원소를 모두 공백 히프에 삽입 - 루트 노드(가장 큰 원소)를 삭제하여 리스트 뒤 삽입 - 삽입된 원소를 제외한 나머지 원소들에 대해 반복 수행 - 시간 복잡도: O(nlogn) 3. HeapSort Algorithm heapSort(a[]) n

1. 퀵 정렬: 분할 정복(divide and conquer) 정렬 방법 중 하나 - 방법: 배열 a[m:n]의 한 원소를 pivot으로 선정 -> pivot 기준으로 두개의 파티션으로 분할(왼쪽: 작은 값 원소들, 오른쪽: 큰 값의 원소들) - 시간 복잡도: O(nlogn) - QuickSort Algorithm quickSort(a[], m, n) // 배열 a의 부분 배열 a[m:n]을 오름차순 정렬 if(m>=n) then return; // 정렬 원소 수가 0이거나 1일때는 복귀 p = partition(a,m,n) // p는 파티션이 끝난 뒤 사용된 pivot 인덱스 quickSort(a[], m, p-1); quickSort(a[], p+1, n); ※ patition 알고리즘: 부분 배열 ..

실습 - 1: 이진 탐색트리 만들기 메소드 역할 BinaryTree copy(BinaryTree btree) 매개 변수로 받은 btree를 복사 boolean equal(BinaryTree btree, BinaryTree ctree) 매개변수로 받은 btree와 ctree가 같은지 확인 BinaryTree swap(BinaryTree btree) btree를 swap boolean isLeaf() 리프노드인지 확인하는 함수 int size() 이진 트리의 노드의 개수를 구하는 함수 int height() 이진 트리의 높이를 구하는 함수 int numLeaves() 터미널 노드의 개수를 확인하는 함수 void printNode(BinaryTree T) 이진트리T 출력 BinaryTree insertKey(..

1. 개요 a. 런(run): 원소들이 정렬되어 있는 순서 순차(ordered sequence) b. 합병 정렬: k개의 런(run)이 나뉘어진 n개이 언소들을 하나의 순서 순처로 합병하는 방식 -> 각 런은 key값에 따라 오름차순 정렬되어 있음 -> k개의 원소 중 가장 작은 키 값을 가진 원소를 선택: k-1번 비교 -> 선택트리 자료구조 이용 시 비교 회수 줄일 수 있음 2. 종류 a. 승리 트리(winner tree): 완전 이진트리 - 각 단말 노드는 런의 최소 키 값의 원소를 나타냄 - 내부 노드는 두 자식 중 가장 작은 키 값을 가진 원소로 나타남 - 구축과정: 가장 작은 키 값을 가진 원소가 승자, 트리에서 가장 작은 키 값을 가진 노드가 루트노드임으로 승자가됨 - 표현: 순차표현이 유리..

1. 히프(Heap) a. 정의: 각 노드의 키 값이 자식의 키 값보다 작지않은 완전 이진트리이다. b. 종류: 최대 히프(Max heap) - 각 노드의 키 값 > 그 자식 키 값 최소 히프(Min heap) - 각 노드의 키 값 < 그 자식 키 값 c. 특징: 최소 히프의 루트 = 트리에서 가장 작은 키 값, 최대 히프의 루트 = 트리에서 가장 큰 키 값 d. 연산 알고리즘: H ∈ Heap; e ∈ Element; createHeap() := create an empty heap; //공백 히프 생성 insertHeap(H, e) := insert a new item e into H // 새로운 원소를 히프에 삽입 isEmpty(H) := if the heap H is empty then retur..

특징: 임의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조 정의: 모든 원소는 상이한 키를 가짐 + 왼쪽 키 공백일 시 실패로 종료 -> 루트키가 x이면 성공으로 종료 - 키 값 x < 루트 키 일때, 왼쪽 서브트리만 탐색, 또는 반대로 - 알고리즘 public BinaryTree find(String x) { BinaryTree T = btree; int result; while (T != null) { // 비교를 해서 data보다 작음으로 왼쪽 링크를 쫒아감. if ((result = x.compareTo((String) T.data)) < 0) { // 왼쪽 링크 쫓아감 T=T.llink; } /..

순회(traversal): 이진 트리에서 각 노드를 빠짐없이 모두 방문하는 방법 n개의 노드 구성 이진트리 순회 방법 가지 수: n ! 3가지 순회 방법 a. 중위 순회(Inorder) - left -> root -> right(왼쪽 부터 노드를 읽음) // 알고리즘 public void inorder(BinaryTree btree) { if (btree.data == null) return; inorder(btree.ltree); System.out.print(btree.data+" "); // 루트 노드 방문 inorder(btree.rtree); } // End of inorder => 중위 순회 결과: 8,4,9,2,10,5,11,1,6,3,12,7 b. 전위 순회(Preorder) - root ..

트리(Tree): 계층형 자료구조 - 하나의 node = 그 자체로 트리 = root - 트리의 기본 성질: 노드가 N개인 트리는 항상 N - 1개의 링크를 가짐 * node: 데이터 필드 + 링크 필드 * 노드의 차수(degree): 한 노드가 가진 서브 트리의 수(=각 노드의 가지 수) * 노드의 부모 및 자식 * 트리의 차수: 노드들 차수 중 최대 차수 * 노드의 레벨: root = level 0, 트리의 특정 깊이 * 노드의 높이 또는 깊이: 루트 도달하기 위해 거쳐하는 간선 수 ex. I의 깊이= 2, L의 깊이=3 이진 트리(Binary Tree): node의 유한 집합 - 각 노드는 최대 2개의 자식을 가짐( 왼, 오 중 하나가 공백도 허용) - 리프 노드(leaf node): 둘다 공백일 ..