플밍 is 뭔들/자료구조 썸네일형 리스트형 07-1 선택 정렬 ※ 선택 정렬(Selection Sort) - 원소중 가장 작은 원소를 찾아 선택하여 첫번 째 원소와 교환한다. 그리고 두번째 작은 원소를 찾아 두번 째 자리의 원소와 교환한다. 이런식으로 길이 n인 배열의 n-1자리의 원소와 n번째 원소의 값을 비교하여 정렬하기를 반복한다. ※ 구현 Main public class Main { public static void main(String[] args) { int a[] = {69,10,30,2,16,8,31,22}; SelectionSrot ss = new SelectionSrot(); System.out.println("\n정렬할 원소 : "); for(int i =0; i 더보기 06-4 신장 트리와 최소 비용 신장 트리 ※ 신장트리(Spanning Tree) - 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 - 연결 그래프에서 순회를 하면 n-1개의 간선을 이동하면서 모든 정점을 방문하게 되므로 신장 트리를 생성하게 된다. 너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장트리, 깊이 우선 탐색을 이용해 생성된 깊이 우선 신장 트리라고 한다. - 신장 트리는 최소의 간선을 이용하여 모든 정점을 연결한 그래프가 된다. 이러한 신장트리는 최소의 도로를 이용한 도로망 건설이나 최소의 네트워크선을 이용하여야 하는 통신망 설계 등에 응용된다. ※ Kruskal 알고리즘1 - 가중치가 높은 간선을 내림차순으로 정렬하여 연결이 끊기지 않도록 하면서 가중치가 가장 높은 간선을 하나씩 삭제해 나간.. 더보기 06-3 그래프의 순회 ※ 순회 종류 깊이 우선 탐색 너비 우선 탐색 ※ 깊이 우선 탐색(DFS, Depth Frist Search) - 한 방향으로 갈 수 있을 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선을 탐색을 계속 하므로써 모든 정점을 방문 순회하는 법. - 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 후입 선출 구조의 스택을 사용한다. ※ 너비 우선 탐색(BFS, Breadth First Search) - 시작 정점으로 부터 인접한 정점을 모두 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례대로 방문하는 방법 - 인접한 정점들에 대해 차례로 다시 .. 더보기 06-2 그래프의 구현 ※ 그래프의 구현 - 그래프를 구현하기 위해서는 정점에 대한 집합과 정점에 부속된 간선의 집합을 표현해야 한다. 순차 자료구조 방식을 이용하는 2차원 배열의 인접행렬 방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있다. 만들고자 하는 그래프의 특성과 필요한 연산에 따라 적당한 표현 방법을 만들자. ※ 순차 자료구조 방식을 이용한 그래프의 구현 : 인접 행렬 - 두 정점이 인접하면 1 인접하지 않으면 0으로 표현 - n개의 정점을 가지는 그래프를 n * n 의 인접 행렬로 표현하면 간선의 개수에 상관없이 n*n의 메모리를 사용하기 때문에 간선이 적은 경우엔 메모리 낭비가 일어날 수 있다. ※ 연결 자료구조 방식을 이용한 그래프의 구현 : 인접 리스트 - 각 노드의 정점을 저장하는 .. 더보기 06-1 그래프의 구조 ※ 그래프란? - 연결되어있는 원소간의 관계를 표현하는 자료구조. - 그래프는 연결할 객체를 나타내는 정점(vector)과 객체를 연결하는 간선(edge)의 집합으로 구성된다. 그래프는 G = (V,E)로 정의하는데 V는 그래프에 있는 정점들의집합, E는 정점을 연결하는 간선들의 집합을 의미한다. ※ 그래프의 종류 무방향 그래프 (방향이 없는 그래프, 간선을 (A,B) 로 표현 ) 방향 그래프 (방향을 가진 그래프, 간선을 로 표현) 완전 그래프 (한 정점에서 모든 정점과 연결 되어 있는 구조, 간선의 수는 방향 그래프 n(n-1) 무방향 그래프 n(n-1)/2 개를 갖는다.) 부분 그래프 (원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프) 가중 그래프 (정점을 연결하는 간선에 가중치를 할.. 더보기 05-7 힙의 구현 Main public class Main { public static void main(String[] args) { int n, item; MaxHeap h = new MaxHeap(); h.insertHeap(13); h.insertHeap(8); h.insertHeap(10); h.insertHeap(15); h.insertHeap(20); h.insertHeap(19); h.insertHeap(30); h.printHeap(); n=h.getHeapSize(); for(int i=1; i heap[idx/2]){ temp = heap[idx/2]; heap[idx/2] = heap[idx]; heap[idx] = temp; idx = idx/2; } } public void printHeap(){.. 더보기 05-6 힙 ※ 힙(heap) - 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이가장 작은 노드를 찾기 위해 만든 자료구조. - 키값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap) : 부모 노드의 키값 >= 자식노드의 키값 - 키값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap) : 부모 노드의 키값 더보기 05-5 이진 탐색 트리 구현 BinarySearchTree public class BinarySearchTree { private Node root; public BinarySearchTree() { // TODO Auto-generated constructor stub root=null; } public void insertBST(char data){ Node newNode = new Node(); newNode.data = data; if(root ==null){ root = newNode; }else{ Node temp = root; while(temp != null){ if(newNode.data > temp.data){ if(temp.right == null){ temp.right = newNode; return; }els.. 더보기 05-4 이진 탐색 트리 ※ 이진 탐색 트리(Binary Search Tree) 란? - 이진 트리는 트리를 효율적으로 사용하기 위해 일정한 형태로 정의한 것. 탐색을 위한 자료구조로 이진 트리를 사용할 때 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것이 이진 탐색 트리 ※ 이진 탐색 트리의 정의 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.(즉 작은건 왼쪽에 붙인다.) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.(즉 큰건 오른쪽에 붙인다.) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다. ※ 이진 탐색 트리의 탐색 연산 - 이진 탐색 트리 탐색은 3가지 경우로 나눌 수 있다. 키값 = 루트노드의 키값 : 탐색 성공 키값 < 루트노드의.. 더보기 05-3 이진 트리의 구현 및 순회 ※ 순차 자료구조 방식을 이용한 이진 트리 구현 - 노드번호를 배열의 인덱스로 사용하여 1차원 배열로 표현한다. 아래 그림에서 보듯 완전 이진 트리나 포화 이진트리가 아니면 메모리의 낭비가 생긴다. **인덱스 규칙 (i = 인덱스, n= 노드의 수) 노드 i의 부모 노드 = i/2 (단 i>1) 노드 i의 왼쪽 자식 노드 = i*2 (단 i*2 더보기 05-2 이진 트리 ※ 이진 트리(Binary Tree) 모든 노드의 차수를 2 이하로 정의하여 전체 트리의 차수가 2 이하가 되도록 만든것. 이진 트리의 서브 트리들 역시 모두 이진 트리이다. 특정 노드를 기준으로 했을 때 왼쪽 트리 부분을 왼쪽 서브트리라고 하며 오른쪽 트리 부분을 오른쪽 서브트리라 한다. ※ 이진 트리의 특성 n개의 노드를 가진 이진 트리는 항상 (n-1)개의 Edge를 갖는다. 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1) -1)개가 된다. ※ 이진 트리의 분류 - 포화 이진 트리(Full Binary Tree) 모든 레벨에 노드가 꽉 차소 포화 상태인 이진 트리 (2^(h+1)-1)개의 최대 노드수를 갖는 이진 트리 루트를 1번으로 하고.. 더보기 05-1 트리 리스트와 스택, 큐는 선의 형태로 나열되어 있는 구조를 가진 선형 자료구조(Linear Data Structure)였다. 선형이 아닌 자료구조를 비선형 자료구조라고 하는데, 트리(tree)는 비선형 자료구조 중에서 자료들 간의 계층관계를 가진 계층형 자료구조(Hierarchical Data Structure)다. ※ 트리의 구조 Root - 트리의 시작점 ex)A Node - 트리를 구성하는 원소, 자료 ex)A,B,C.....M Edge - 간선이라고도 하며 Node와 Node를 연결하는 선 Level - 트리의 특정 깊이를 가지는 Node의 집합 Degree - 차수라고도 하며 한 노드가 가지는 서브 트리의 수, 자식노드의 수 ex) 노드B의 차수는 2, 노드 D의 차수는 3이다 Leaf Node -.. 더보기 이전 1 2 3 4 다음
