혼자공부하기

일반 큐의 문제점

일반적인 큐는 배열로 일직선으로 구현되어짐. 그리고 선입 선출이라 맨앞에 데이터가 빠져나가면 한칸씩 앞으로 당겨야되기때문에 성능적으로 좋지 않음

원형 큐

말그대로 큐를 선형이 아닌 원형으로 생각하여 구현 하는 것이다.

• enqueue() : 원소 뒤에서 삽입
• dequeue() : 원소 앞에서 삭제
• isEmpty() : 공간 확인
• getSize() : 사이즈 반환

lastOp 변수를 사용하여 큐의 공간 전부를 사용할 수 있게 한다. (즉 원형 큐 문제점 해결방안)

쉽게 이야기하면 마지막 연산을 기록해두는 변수이다.

삽입이 마지막이면 push, 삭제가 마지막이면 pop로 설정하여 front == rear 일때 lastOp가 push이면 포화, lastOp가 pop이면 공백

하지만 큐의 삽입 삭제 연산이 느려짐...

스테이블 정렬(안정정렬)은 정렬되지 않은 데이터들중 같은 데이터가 있을 때 정렬하면서 그 순서가 변하지 않는 것을 의미

언스테이블 정렬은 반대로 순서가 변하는 것을 의미

Stable Sort

• 삽입정렬
• 합병정렬
• 거품정렬
• 계수정렬

Unstable Sort

• 선택정렬
• 힙정렬
• 퀵정렬
• 쉘정렬

package test;

public class 삽입 {
	
	
	
	private static int arr[] = {4,9,7,1,5};
	public static void main(String[] args) {
		
		for(int i=1; i<5; i++) {
			int val = arr[i];
			for(int j= i-1; j>=0; j--) {
				if(arr[j+1] < arr[j]) {
					arr[j+1] = arr[j];
				} else {
					break;
				}
				arr[j] = val;
			}
			print();
		}
		
	}
	
	
	public static void print() {
		for(int i=0; i<5; i++) {
			System.out.print(arr[i]);
		}
		System.out.println();
	}
}

 B-tree와 각 노드에 데이터가 저장이 되지만 B+tree의 경우엔 인덱스노드와 리프노드가 분리되어서 존재한다. 그리고, 리프노드는 서로 연결되어 있어서 임의접근과 순차접근모드 성능이 우수하다.

공통점

• 모든 leaf의 depth가 같다
• 각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.
• search가 비슷하다.
• add시 overflow가 발생하면 split 한다
• delete 시 underflow가 발생하면 redistribution하거나 merge 한다.

차이점

• B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다.
• B+tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+tree에서는 data는 오직 leaf에만 존재한다.
• B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.
• B+ tree는 leaf node 끼리 linked list로 연결되어 있다.

B+tree의 장점

• 블럭사이즈(노드사이즈) 를 더 많이 이용할수잇다 ( 키값에 대한 harddisk 엑세스 주소가 없기 때문에 )
• leaf node 끼리 linked list로 연결되어있어서 시퀀셜한 레인지 탐색에 매우 유리하다 

B + Tree 의 단점

• B Tree의 경우 best case에는 루트에서 끝날수 있지만, B+ Tree의 경우 무조껀 leaf노드까지 가야한다.

출처: https://wangin9.tistory.com/entry/B-tree-B-tree [잉구블로그]

• AVL트리는 더욱 엄격한 균형을 이루고 있기 때문에 Red-Black 트리보다 더 빠른 조회를 제공
• Red-Black 트리는 상대적으로 느슨한 균형으로 인해 회전이 거의 이루어지지 않기 때문에 AVL트리보다 빠르게 삽입 및 제거 작업을 수행
• AVL트리는 각 노드에 대해 BF를 저장하므로 노드 당 int 저장이 필요
  Red-Black 트리는 노드당 1비트의 정보만 필요합니다. (플래그 반전만 시키면 됨)
• Red-Black 트리는 맵, C++의 멀티캐스트, Java treeMap 등 대부분의 언어 라이브러리에서 사용, AVL트리는 더 빠른 검색이 필요한 데이터베이스에서 사용

출처 : https://velog.io/@agugu95/%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B7%A0%ED%98%95-RED-BALCKAVL

선택정렬(SelectionSort)

선택정렬 예시

해싱(Hashing)

• 해싱은 데이터를 해싱 함수에 의해 주소로 변환해 해당 주소 위치에 데이터를 저장하는 방식입니다.(key-value 방식)
• 데이터 검색시 빠르게 찾을 수 있는 장점이 있는 반면, 해시 테이블 용량 부족으로 오버플로우가 발생 가능합니다.

용어 정리

• 해시 함수 : 데이터를 키로 변환하는 함수
• 홈 주소 : 해시 함수로 변환된 키 값의 주소
• 해시 테이블 : 해시 함수가 키 값 변환시 참조하는 테이블
• 버킷 : 하나의 주소를 갖는 구역, 버킷의 크기는 레코드 몇개 들어갈 수 있는가를 의미
• 슬롯 : 하나의 데이터를 저장할 수 있는 공간, 하나의 버킷안에 여러개의 슬롯을 가짐
• 충돌 : 다른 데이터가 같은 키를 가지는 충돌 현상
• 동의어 : 동일한 홈 주소로 인하여 충돌이 일어난 레코드들의 집합
• 오버플로우 : 하나의 홈 주소의 버킷이 가득 차서 레코드를 저장할 슬롯이 없는 상태

해시 함수 종류

• 제산함수

• 중간제곱함수

• 접지함수

• 숫자분석함수

오버플로우 처리 방법

• 선형조사법 : 오버플로우가 발생 시 다음 버킷에 빈 슬롯이 있으면 저장하는 방법
• 이차조사법 : 선형조사법의 편향을 방지하기 위해 오버플로우 발생시 n^2의 +-씩으로 검사하여 저장하는 방법
• 재해싱 : 여러 개의 해시함수를 사용하는 방법
• 임의 조사법

최소비용 신장트리

- 최저의 비용을 갖는 신장트리

- Kruskal, Prim, Sollin 알고리즘이 있습니다.

갈망법(Greedy method)

신장트리 제한 조건

Kruskal 알고리즘

Prim 알고리즘

탐색 알고리즘에 DFS와 BFS가 있습니다.

DFS(Depth First Search)

위의 트리를 탐색하는 순서는 A->B->D->E->C->F->G 순으로 탐색을 합니다.

DFS 구현은 스택을 사용하여 가능하기에, 주로 재귀함수를 사용합니다. 장점은 마지막 방문한 노드의 데이터만 저장하면 되기에 공간이 절약됩니다. 단점은 노드의 깊이가 깊으면 성능이 떨어지고 최단경로가 된다는 보장이 없습니다.

BFS(Breath First Search)