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. 부분 순서(partial order) i) 이행적(transitive), 비반사적(irreflexive)인 선행관계일때, 관계 R은 부분 순서라고 한다. ii) 집합S, 관계R에서 S의 원소 i, j, k : ①R은 S에서 이행적이라면 -> iRi&iRk이면 iRk가 성립 ②비반사적일때->모든 i가 iRi가 성립하지않음 iii) 이행적이면서 대칭적(symmertric)이라면 부분 순서 성립x: 이 관계는 반사적이고 반사적이면 부분 순서가 성립x iv) DAG(Directed Acyclic Graph): 비반사적 그래프는 싸이클이 없고 이를 DAG라 한다. 2. 위상 순서(topological order) i) 정의: 방향그래프에서 정점 i가 선행자이면 i > j 순서를 가진 순차리스트..

실습 - 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. 그래프를 인접 리스트로 표현 import java.util.Stack; class Graph{ Node header[] = new Node[10]; boolean visited[] = new boolean[10]; public void Graph(){ for(int i=0; i

1. 그래프 순회란? : 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점을 방문하는 것 2. 그래프 순회의 종류 a. DFS(깊이 우선 탐색) i) 동작: 정점 i 방문 -> 인접한 정점 중 아직 방문하지 않은 정점을 스택(stack)에 저장 -> 스택에서 정점 삭제 후 새로운 i 설정 -> 공백 시 연산 종료 ii) 정점 방문 여부를 배열로 표현: visited[i] = { true or false} iii) 알고리즘 DFS(i) // i=시작 정점 for(i

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; } /..