CS/자료구조

힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 예를 들어 {2, 8, 5, 3, 9, 1} 배열은 다음과 같은 힙 정렬의 과정으로 오름차순 정렬할 수 있다. ▼ 힙 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void HeapSort(int arr[], int n) { heapify(arr, n); for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i); } } public static void heapify(int arr[..

삽입 정렬이란 배열의 두 번째 인덱스부터 시작하여 그 앞의 인덱스가 클 경우 그 인덱스가 위치한 곳에 삽입하여 정렬하는 방식이다. 정렬 과정을 보면 다음과 같다. ▼삽입 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void InsertionSort(int arr[], int n) { int i,j; int data=0; for(i=1;i=0;j--) { if(arr[j]>data) { arr[j+1]=arr[j]; arr[j]=data; } else break; } } } public static void main(String[] args){ int arr[] = {5, 2, 6, 3, 1, 4}; Insert..

선택 정렬이란 주어진 배열에서 최솟값을 찾고 배열의 맨 앞에 위치한 값과 교체한 후 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체해 나가는 방식이다. 정렬 과정을 보면 다음과 같다. ▼선택 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void SelectionSort(int arr[], int n) { int index=0; int min=0; int j,i; for(i=0;i

버블 정렬이란 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 예를 들어 3, 2, 4, 1 이 순서대로 저장되어 있을 때 다음 배열을 오름차순으로 정렬하는 과정을 그림으로 나타내었다. 다음 그림처럼 맨 앞에서부터 맨 끝까지 정렬의 과정이 진행되었다고 해서 정렬이 완료되는 것이 아니라 다시 숫자를 비교하여 정렬을 완료될 때까지 과정을 반복해야 한다. ▼버블 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void BubbleSort(int arr[], int n) { int temp; for(int i=0;i

우선순위 큐 - 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 우선순위 큐의 구현 방법 ● 배열을 기반으로 구현하는 방법 ● 연결 리스트를 기반으로 구현하는 방법 ● 힙을 이용하는 방법 우선순위 큐의 시간 복잡도 여기서 힙이란 ? 힙은 완전 이진트리를 말하며 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야 한다. 위 트리처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙이라 한다. 반면 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 최소 힙이라 한다. ▼ 힙에서의 데이터 저장 과정 ▼ 힙에서의 데이터 삭제 과정

1. Root 2. Left 3. Right 결과 : 1 2 4 5 3 1. Left 2. Root 3. Right 결과 : 4 2 5 1 3 1. Left 2. Right 3. Root 결과 : 4 5 2 3 1

노드 : node 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소 간선 : edge 노드와 노드를 연결하는 연결선 루트 노드 : root node 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드 : terminal node 아래에 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드 내부 노드 : internal node 단말 노드를 제외한 모든 노드로 A, B 와 같은 노드 다음 그림과 같이 트리는 작은 트리로 구성된다. 이 때 작은 트리는 서브트리라 부른다. 또 서브트리는 서브트리로 나뉠 수 있다. 이진트리가 되기 위한 두 조건 ● 루트 노드를 중심으로 두개의 서브 트리로 나뉘어진다. ● 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다. 트리에서는 각 ..

큐란 가장 먼저 들어간 것이 가장 먼저 나오는 특성을 가진 자료구조를 말한다. 다음 그림처럼 먼저 들어간 Data는 나올 때 가장 먼저 나온다. 이러한 구조를 First In First Out(FIFO) 또는 Last In Last Out(LILO) 라 한다. 큐의 ADT는 다음과 같은 연산들을 정의한다. - 큐에 데이터를 넣는 연산 enqueue - 큐에서 데이터를 꺼내는 연산 dequeue ● enqueue 연산 방식 다음 그림은 길이가 4인 배열 대상의 enqueue 연산을 보이며 여기서 F는 Front 를 의미하고 R은 Rear 를 의미하는데 새 데이터는 Rear 부분에 저장되고 R은 그 다음 칸을 가리키게 된다. ● 일반적이지 않은 dequeue 방식 위 그림에서 보이는 방식은 dequeue 연..

전위 표기법(PreFix) : +AB 중위 표기법(InFix) : A+B 후위 표기법(PostFix) : AB+ 다음과 같이 Infix 로 표기된 수식을 Prefix 로 변환하시오. X = A / B * ( C + D ) + E 항상 식에서 우선순위의 계산 먼저 시작한다. (괄호 > 곱셈,나눗셈 > 덧셈,뺄셈 순으로) 다음과 같이 Infix 로 표기된 수식을 Postfix 로 변환하시오. X = A / B * ( C + D ) + E 다음과 같이 Postfix 로 표기된 수식을 Infix 로 변환하시오. A B C - / D E F + * + 후위 표기법을 중위 표기법으로 변환할 때는 (피연산자 피연산자 연산자) 인지 확인 후 정리해야한다. 다음과 같이 Prefix 로 표기된 수식을 Infix 로 변환하..