CS

▶보이어무어(Boyer - Moore) ⦁ 문자열 매칭이 마지막에 틀릴 가능성이 높다는 특징을 이용한다.⦁ 검색할 패턴의 길이가 길고 텍스트 길이가 길 때 효율적이다.⦁ 전체 문자열과 패턴을 비교 시 문자열의 뒷부분부터 비교하고 다르면 일정 길이만큼 이동한다.⦁ 불일치 문자 규칙과 좋은 접미사 규칙을 사용한다.    불일치 문자 규칙(Bad Character Rule): 패턴의 불일치 문자가 텍스트에 존재하는 경우, 패턴을 오른쪽으로 이동시켜서 불일치 문자가 패턴 내에서 가장 오른쪽에 위치하도록 한다.좋은 접미사 규칙(Good Suffix Rule): 패턴의 일치 접미사가 이미 확인된 경우, 패턴을 이동하여 이미 일치한 접미사가 다른 위치에서 다시 일치하도록 한다.    예제1     예제2  예제3  ..

8, 7, 9, 3, 6, 4, 5, 12 데이터를 삽입  1. 7 삽입  2. 9 삽입  3. 3 삽입  4. 6 삽입  5. 4 삽입  6. 5 삽입 7. 12 삽입(결과)    50 20 10 30 80 40 35 25 데이터를 삽입 1. 20 삽입 2. 10 삽입 3. 30 삽입 4. 80 삽입 5. 40 삽입 6. 35 삽입 7. 25 삽입(결과) 20 15 3 12 5 11 6 40 25 18 데이터를 삽입 1.15 삽입  2. 3 삽입 3. 12 삽입 4. 5 삽입 5. 11 삽입  6. 6 삽입   7. 40 삽입 8. 25 삽입 9. 18 삽입(결과)8 18 5 15 17 25 40 80 데이터를 삽입  1. 18 삽입  2. 5 삽입   3. 15 삽입  4. 17 삽입  5. 25 삽..

23 50 72 17 12 20 60 데이터 삽입 결과 8 9 10 2 1 5 3 6 4 7 11 12 데이터 삽입 결과 20 12 10 7 3 1 데이터 삽입 결과

▶ 해쉬 테이블이란? 해쉬 테이블이란 key 와 value 로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있는 자료구조이다. ▶ 해쉬 테이블의 구조 해쉬 테이블의 구조는 다음과 같다. F(key) → HashCode → Index → Value 즉 key 값을 해시 함수에 넣어 해쉬코드를 얻은 다음 특정 계산에 의해 배열의 Index 값을 얻고 그 배열에 저장한다. 다음 그림에서는 각 알파벳을 아스키코드로 변환한 다음 그 숫자들을 모두 더해 hashcode 로 나타낸다. sung : s(115) + u(117) + n(110) + g(103) = 445 jin : j(106) + i(105) + n(110) = 321 hee : h(104) + e(101) + e(101) = 306 min ..

▶ AVL 트리 란? - 이진 탐색 트리의 한 종류 - 스스로 균형을 잡는 트리 - balance factor 를 통해 균형 유지 ▶ 노드의 balance factor 란? - 임의의 노드 x 에 대해서 왼쪽 서브 트리의 높이와 오른쪽 서브트리의 높이의 차 이다. - 균형 인수(balance factor)의 절댓값이 크면 클수록 그만큼 트리의 균형이 무너진 상태이다. ▶ AVL 트리의 특징 - 트리의 모든 노드들은 아래와 같은 특징을 갖는다 BF(x) ∈ { -1,0,1 } - AVL 트리는 균형 인수의 절댓값이 2 이상인 경우 균형을 잡기 위한 트리의 재조정을 진행한다. 예를 들어 아래와 같은 이진 트리가 있을 때 노드 50 은 왼쪽 서브 트리의 높이가 1 이고 오른쪽 서브 트리의 높이가 2 이기 때문..

이진 트리에 데이터의 저장 규칙을 더해놓은 것이 이진 탐색 트리이다. 이진 탐색 트리가 되기 위한 조건을 나열해보면 · 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. · 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다. · 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 아래 그림은 위의 조건을 만족하는 트리의 예이다. 왼쪽 자식 노드의 키 9 이므로 오른쪽 자식 노드로 이동 그 위치에 저장

지금까지 배운 탐색에는 순차 탐색, 이진 탐색이 있다. 순차 탐색 - 정렬되지 않은 대상을 기반으로 하는 탐색 이진 탐색 - 정렬된 대상을 기반으로 하는 탐색 이 중에서 이진 탐색은 중앙에 위치한 데이터를 탐색한 후 이를 기준으로 탐색 대상을 반으로 줄여나가면서 탐색을 진행하는 알고리즘이다. 찾는 대상이 맨 앞에 있던 뒤에 있던 무조건 중앙부터 반씩 줄여가면서 탐색을 진행하는데 이러한 부분에서 효율이 떨어지는 경향이 있다. 이를 개선한 알고리즘이 보간 탐색이다. 보간 탐색은 오름차순으로 정렬된 배열에서 찾고자하는 데이터가 앞에 있으면 앞쪽에서 탐색을 시작한다. 만약 다음 배열에서 key = 25 를 탐색한다고 가정하면 탐색 위치 = low + (key-array[low])/(array[high]-arra..

퀵 정렬은 배열에서 하나의 요소를 선택하여 기준(pivot)으로 삼는다. 그리고 배열의 왼쪽 부분과 오른쪽 부분에서 인덱스 값을 탐색하며 기준보다 크거나 작으면 그 두 수를 서로 교환하는 방식이다. ▼퀵 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void Swap(int arr[], int idx1, int idx2) { int temp = arr[idx1]; arr[idx1]=arr[idx2]; arr[idx2]=temp; } public static void QuickSort(int arr[], int left, int right) { if(left

병합 정렬이란 하나의 리스트를 두 개의 균등한 크기로 분할하는데 더 이상 분할되지 않을 때까지 한다. 그 다음 분할된 리스트 2개를 비교하여 정렬한 다음 하나의 리스트로 병합하여 정렬하는 방식이다. 예를 들어 {8, 2, 3, 7, 1, 5, 4, 6} 이라는 배열이 있을 때 다음 그림과 같은 과정을 통해 정렬된다. ▼ 병합 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void MergeSort(int arr[],int left, int right) { int mid; if(left