오늘도 삽질

노트정리/알고리즘

균형나무와 외부 탐색법

2-3-4 트리는 모든 중간 노드들의 자식수가 2,3,4이면서 모든 단말 노드가 같은 레벨에 있는 나무입니다.2-3-4 나무 특징- 2-3 나무를 확장 하여 다양한 나무를 만들수 있다.- 데이터베이스에서 사용하는 색인구조의 형태- 한 노드에 있을 수 있는 값의 수가 많다면 나무의 높이 감소.- 나무의 높이가 감소하면 할수록 검색 향상됨.2-3-4 나무의 삽입- 단말 노드에서 이루어집니다. 삽입할 노드를 찾는동안 4-노드를 만나면 분할합니다.2-3-4 나무의 삭제- 먼저 삭제할 값을 포함한 노드를 찾아야 한다.- 그 노드가 단말 노드가 아니면 그값과 그것의 중위 순위상에서 바로 앞 값을 교환함. (이 값은 항상 단말 노드에 있음) n개의 노드로 구성된 2-3-4 나무가 있을때 나무의 높이 = 최대 logn..

노트정리/알고리즘

탐색 알고리즘 - 다양한 탐색법

컴퓨터의 기억공간 내에 저장한 특정 항목의 위치를 찾거나 자료가 집합 내에 없을 경우에는 특정한 메시지를 출력하여 주는운영 방법을 탐색이라고 합니다. 컴퓨터를 이용하는 최고의 목적은 정보를 저장하고 정리한 후 탐색하는 것이죠. 탐색에 들어가기전알아야할 용어들이 있습니다. 기본적인 용어는키 : 키는 파일 내의 레코드를 다른 레코드와 구별할 수 있는 항목기본키 : 특별히 각 레코드를 완전히 구분할 수 있는 검색키레코드 : 1개 이상의 항목들을 서로 관련 있는 것끼리 짝을 지어 모은 형태딕셔너리 : 검색이라는 자료 처리를 하기 위하여 키와 레코드 및 기본 연산들을 자료 구조 형태로 표현해 놓은 것심벌 테이블 : 프로그램에 대한 딕셔너리로 자료 구조에 대한 모든 명세들을 가지고 있으며 보통 이름과 값으 쌍으로 ..

노트정리/알고리즘

정렬 알고리즘 - 외부 정렬

외부 정렬주기억장치의 용량이 적기 때문에 자료의 양이 많은 대형 파일은 한 번에 내부 정렬로 처리 하는 것이 힘듭니다.그래서 대형 파일을 여러 개의 부분 파일로 나누어 보조기억장치에 저장합니다. 그런 다음 각각의 부분 파일을 내부 정렬에의해 정렬하고 합병시켜 정렬하죠. 이와 같이 순차적접근 방식의 자기 테이프나 직접 적근 방식의 자기 디스크와 같은같은 보조기억장치를 이용하여 정렬하는 방식을 외부 정렬 이라 합니다.보조기억장치를 이용하는 외부 정렬 방법 중 가장 일반적인 방법은 합병 정렬입니다. 이 방법은 입력 파일을 몇 개의 부분 파일로분리하여 각각을 적절한 내부 정렬 방법으로 정렬한 다음 다시 보조기억공간에 저장한다. 이와 같이 정렬한 부분 파일을런이라고 합니다. 그 다음 먼저 만들어진 런들은 회전을 ..