1. 배열 기반 큐 특징 배열 기반이기 때문에 큐의 크기가 고정적임 큐 구조의 제일 앞쪽과 제일 뒤쪽을 나타내는 인덱스가 필요함(front, rear) 삽입과 삭제시 연산이 복잡함 2. 배열 기반 큐 구현 public class Queue { int front, rear, size; int capacity; int array[]; public Queue(int capacity) { this.capacity = capacity; front = this.size = 0; rear = capacity - 1; array = new int[this.capacity]; } // 큐가 가득찼는지 검사 boolean isFull(Queue queue) { return (queue.size == queue.capaci..

1. 배열 기반 스택 특징 스택의 담을 수 있는 크기가 고정적임 최상위를 나타내는 변수(top)를 이용하여 삽입과 제거 연산을 수행함 2. 배열 기반 구현 public class StackAsArray { static final int MAX = 1000; int top; int a[] = new int[MAX]; boolean isEmpty() { return (top=(MAX-1)) { System.out.println("Stack Overflow"); return false; } else { a[++top] = x; System.out.println(x + " pushed into stack"); return true; } } int pop() { if(top

1. 원형 연결 리스트(Circular Linked List) 원형 연결리스트는 기본적인 연결리스트에서 마지막 노드의 next 포인터가 리스트 맨 앞의 노드를 가리키는 리스트입니다. 일반적인 연결리스트는 head 포인터를 이용하여 리스트의 맨 앞에 노드를 추가하고, 맨 뒤의 노드의 next 포인터는 null을 가리킴 원형 연결리스트는 tail 포인터를 이용하여 리스트의 맨 뒤를 가리킬 수 있고, tail.next 포인터를 이용하여 리스트의 맨 앞의 노드를 가리킬 수 있음 2. 원형 연결 리스트의 추가, push 리스트의 tail 포인터를 이용하여 push 메서드 수행시 리스트의 맨 뒤에 노드를 추가합니다. 원형 연결 리스트의 push 수행 과정 newNode.next = tail.next tail.nex..

학습목표 1. 여러 종류의 정렬에 대한 시간복잡도를 요약 stable은 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는지를 의미합니다. In-place는 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬하는 방법입니다. In-place의 반대인 Out-of-place는 모든 데이터를 자료 구조의 복사본에 옮긴 후 순서대로 배열하여 정렬하는 방법입니다. Best는 정렬을 수행할 때 최선의 경우에 해당됩니다. 예를 들어 오름차순으로 정렬하는 경우의 최선의 경우는 이미 오름차순으로 정렬되어 있는 경우입니다. Avg는 정렬을 수행할 때 평균적인 경우에 해당됩니다. 평균적인 경우는 보통 수들이 불규칙하게 섞여 있는 경우에 해당됩니다. Worst는 정렬을 수행할 때 최악의 경우에 해당됩니다. 예를 ..

학습목표 1. 기수 정렬이 무엇인지 학습 2. 기수 정렬의 수행과정을 학습 3. 기수 정렬을 구현 4. 기수 정렬의 시간복잡도에 대해서 학습 1. 기수 정렬(Radix Sort)란 무엇인가? 기수 정렬은 우편번호, 자리수 등의 기준을 만들어 기준에 따라 숫자를 분류하여 정렬하는 방법입니다. 예를 들어, 4자리 숫자를 일의 자리의 숫자, 십의 자리의 숫자, 백의 자리의 숫자, 천의 자리의 숫자에 따라 분류하여 정렬할 수 있습니다. 2. 기수 정렬의 수행 과정 기수 정렬의 수행 과정은 다음과 같습니다. 0~9까지의 Bucket(Queue 구조) 리스트를 준비합니다. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 추가합니다. 0부터 차례대로 버킷에서 데이터를 가져옵니다. (..

학습목표 1. 분할 정복 방법에 대해서 학습 2. 퀵 정렬의 과정을 학습 3. 퀵 정렬의 예제를 학습 4. 퀵 정렬의 Java 언어 기반 구현 5. 퀵 정렬의 특징에 대해서 학습 6. 퀵 정렬의 시간복잡도에 대해서 학습 1. 퀵 정렬(Quick Sort)이란 무엇인가? 퀵 정렬은 리스트 안의 하나의 요소를 피벗(pivot)이라는 것을 정하여 피벗을 기준으로 왼쪽 부분 리스트, 오른쪽 부분 리스트로 분할하고 순환 호출을 이용하여 부분 리스트들을 정렬하는 알고리즘입니다. 퀵 정렬은 분할 정복(divide and conquer) 알고리즘의 하나로써, 평균적으로 매우 빠른 수행 속도를 가지는 정렬 방법입니다. 분할 정복 알고리즘이란 하나의 커다란 문제를 2개의 작은 문제로 분할(divide)하고 각각의 문제를 ..