삽입 정렬 기준이 되는 키 값의 앞쪽 자료들과 비교하여 자신의 위치를 찾아 삽입하여 정렬하는 방법이다. 기준 키는 삽입 될때마다 하나씩 뒤로 해당되며 옆칸의 데이터와 비교하여 자신의 자리를 찾는다. 선택 정렬 전체 데이터를 탐색하고 최솟값을 찾아 첫번째 위치에 놓는다. 그렇게 다음 최솟값을 찾고 두번째 위치에 놓는 방법을 반복하여 정렬한다. 버블 정렬 인접한 데이터와 비교하여 위치가 맞지 않을 경우 서로 자리를 교환하는 방법이다. 단계 수행 중 자리 교환이 더 이상 발생하지 않으면 정렬이 완료된다. 퀵 정렬 분할 정복 알고리즘중 하나로 평균적으로 매우 빠른 속도의 정렬 시간을 자랑한다. 리스트 내의 한 요소를 피벗(pivot)이라고 잡고, 피벗보다 작은 요소는 왼쪽으로, 큰요소는 오른쪽으로 이동한다. 피..

해싱이란 다른 레코드 참조 없이 특정 키 변환에 의하여 원하는 레코드에 접근할 수 있도록 구성하는 것을 의미한다. 해싱의 특징 1. 기억장소의 낭비가 심하기 때문에 많은 기억 공간을 요구한다. 2. 검색 방법 중에서 속도가 가장 빠르다 3. 계산에 의해 산출하므로 주소 산출에 시간이 오래 걸린다. 직접 접근 방식 (Direct Access Method) 해싱 방법에 의해서 만들어지는 파일을 직접 파일(Direct File)이라고 한다. 레코드를 식별하기 위한 키 값과 레코드 주소 사이 관계를 예측한다. 해시 테이블 레코드를 1개 이상 보관할 수 있는 기억 공간으로 보조 기억장치나 주기억 장치에 구성할 수 있다. 키 값을 가지면 해시 함수들을 통해 버켓의 실제 주소를 얻을 수 있고, 이를 통해 키만을 가지..

N 대 M 대응 구조로 노드와 선분으로 구성되어있다. 트리와 다른점은 서로 사이클이 형성되는 경우를 그래프라고 표현한다. 주로 최단 거리 탐색, 전자 회로 분석, 통계학과 같은 분야에서 사용된다. 비방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph) 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라 하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph 라고 한다. 그래프 탐색 너비 우선 탐색 (BFS) : 시작점에서 시작하여, 연결된 정점 끝까지 내려간다. 끝나는 지점을 만나게 되면 다시 되돌아와 그 옆부터 끝까지 검색한다. 밑 까지 검색하다 다시 되돌아가야 하니 stack과 같은 자료구조를 사용하면 된다. 깊..

트리는 1대 N 또는 1대 1 대응 구조로 노드와 선분으로 구성되어 있다. 또한 노드 사이 연결관계가 계급적인 구조로 뻗어나간 정점들이 다른 정점들과 연결되지 않는다. 트리의 구성요소 노드 - 기본 구성요소인 각 점들 근 노드 - 가장 상위에 위치한 노드 레벨 - 근노드를 기준으로 특정 노드까지의 경로 길이를 말함 깊이 - 트리의 최대 레벨 차수 - 특정 노드 밑에 자식 노드의 개수를 말한다. 이진 트리 모든 노드의 차수가 2 이하인 트리로 구성되어 있으며, 트리의 전체 노드 수는 최대 $2^(k+1)$이다. 포화 이진 트리 모든 노드의 레벨이 같으며 2개의 자식을 가진다. 이진 트리로서 가장 많은 노드를 가진 트리이기도 하다. 완전 이진 트리 완전 이진트리는 포화 이진트리에서 오른쪽으로 하나씩 제거하여..

배열 가장 간단한 구조로, 각 요소들은 인덱스 값을 같이 표현한다. 배열을 이루는 각 자료들을 배열 요소라 하고, 배열된 순서대로 위치를 저장한다. 기록 밀도가 1이지만 삽입가 삭제가 어렵고 종속적인 것이 단점이다. 찾고자 하는 인덱스를 찾기 위해서는 인덱스 번호만 알면 되기에 바로 찾을 수 있지만, 데이터를 삭제하거나 삽입 할땐 그 뒤의 요소들이 모두 시프트 되기 때문에 오래걸린다. 연결 리스트 자료를 구성할 때 포인터를 포함해서 자료를 구성하는 형태로 포인터를 이용하여 다음 자료를 찾는다. 노드의 삽입과 삭제를 할때 변경하고 포인터 위치만 바꾸어 주기 때문에 속도가 빠르지만, 정보를 검색할때 포인터를 여러번 타고 들어가야 하기 때문에 느려진다. 단일 연결 리스트 단일 연결 리스트는 노드마다 1개의 링..

스택 삽입, 삭제가 한쪽 끝에서 이루어지는 데이터 구조로 가장 먼저 들어간 데이터가 제일 마지막에 나온다. 함수 호출시 복귀 번지를 저장하거나 인터럽트 분기시 복귀 주소를 저장하는데 주로 사용하며, push연산과 pop연산으로 데이터를 삽입/삭제 한다. 큐 한쪽 방향으로 입력, 다른 한쪽 방향에서는 출력만 하는 구조이다. 먼저 입력된 자료가 제일 먼저 나오는 선입선출 구조이며 스케줄링, 일괄 처리 등에 사용된다.