본문 바로가기
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 -.. 더보기
04-4 큐의 응용 컴퓨터의 여러 분야에서 발생한 순서대로 문제를 해결해야 하는 경우 큐를 사용한다. 운영체제에서 실행을 요청한 작업들을 순서대로 처리하기 위해서 버퍼 큐와 프로세스 스케줄링 큐를 사용하고, 산업공학 등의 분야에서는 최적의 시스템을 설계ㅖ하기 위한 시물레이션에서 대기 행렬 큐를 사용한다. ※ 운영체제의 작업 큐 - 각기 다른 속도로 실행되는 작업 처리 기간을 조화시키기 위해 사용. ex) 인쇄작업에 버퍼 큐를 이용해 CPU에 비해 느린 인쇄 작업이 진행중일 때 기다리지않고 다음 데이터를 버퍼 큐에 삽 입하여 버퍼큐에 있는 데이터를 순서대로 출력하게 한다. - CUP를 사용하고자 하는 프로세스들에 대한 CPU 사용 스케줄을 관리하기 위해 스케줄링 큐를 사용 준비 큐와 대기 큐로 구성되어 있음 사용하고자 하는 .. 더보기
04-3 큐의 구현(연결 자료구조 방식을 이용한 큐) ※ 순차 자료구조 방식의 단점 사용 크기가 제한되어 있다.(큐의 크기를 마음대로 변경할 수 없다) 원소가 없어도 항상 처음 크기를 유지해야 된다(메모리 낭비가 생긴다) 이러한 문제를 해결하기 위해 연결 자료구조 방식을 이용하여 크기에 제한없는 연결 큐를 구현해 보자. ※ 연결 큐 연결 큐의 초기 상태(공백 큐)에서 front와 rear는 null이다. front는 첫번째 노드를 가르키고(Linked List에서의 head) rear는 마지막 노드를 가르킨다(Linked List에서의 tail) ※ 연결 큐 구현 소스 Interface public interface Queue { boolean isEmpty(); void enQueue(String item); String deQueue(); void de.. 더보기
04-2 큐의 구현(순차 자료구조를 이용한 큐) ※ 큐의 구현 배열을 사용하는 순차 자료구조 방식과 참조변수를 사용하는 연결 자료구조 방식이 있다. 초기 큐를 생성하면 rear와 front는 모두 -1이다. rear와 front 가 같으면 큐에는 값이 없는상태이다. 생성, 공백 큐 검사, 삽입, 삭제, 검색기능이 있다. ※ 선형 큐 구현 소스(순차 자료구조를 이용해 구현) Interface public interface Queue { boolean isEmpty(); boolean isFull(); void enQueue(char item); char deQueue(); void delete(); char peek(); } ArrayQueue public class ArrayQueue implements Queue { private int rear; .. 더보기
04-1 큐(Queue) ※ 큐란? 스택과 다르게 한쪽에선 삽입연산이 일어나고 한쪽에서는 삭제연산이 일어나는 선입선출(FIFO, First In First Out)의 자료구조. 한쪽은 프론트(front)로 정하여 삭제연산만 수행하고 한쪽은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한한다. 큐에서 이루어 지는 삽입연산을 enQueue라 하고 삭제연산을 deQueue라 한다. ※ 선형큐와 원형 큐 선형 큐는 우리가 생각하는 일반적인 큐(바로 위의 그림)이며 원형 큐는 선형큐를 말아논것과 같은 개념이다. 물리적인 형태는 같지만 코딩을 통해 원형의 형태의 개념으로 구현할 수 있다. 원형큐의 장점과 각각의 차이점은 04-2에 있으니 기억이 나지 않으면 가서 확인하자. ※ 연결 큐와 덱 연결 큐와 덱 모두 연결 자료구조를 사용해 .. 더보기
03-4 스택의 응용 ※ 역순 문자열 만들기스택에 한 문자 단위로 잘라서 push했다가 pop을하면 문자열을 역으로 만들 수 있다. ※ 시스템 스택 프로그램 간의 호출과 복귀에 따른 수행 순서를 보면, 호출한 순서와 복귀하는 순서는 반대가 되어 가장 나중에 호출된 함수가 가정 먼저 실행을 완료하고 복귀한다. 따라서 함수의 호출과 복귀 순서는 스택의 LIFO 구조를 응용하여 관리하는데, 이때 사용하는 스택을 시스템 스택(System Stack)이라 한다. 함수나 서브프로그램이 호출되면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프래임에 저장하여 시스템 스택에 삽입(push)한다. 시스템 스택의 top은 현재 실행중인 함수의 스택 프레임이 된다. 그리고 함수가 종료되면 top의 스택.. 더보기

티스토리툴바