우선순위 큐우선순위 큐에서는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐 ADT객체: n개의 element형의 우선 순위를 가진 요소들의 모임연산: create() ::= 우선순위 큐를 생성한다. init(q) := 우선순위 큐 q를 초기화 한다. is_empty(q) ::= 우선순위 큐 q가 비어있는지를 검사한다. is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사한다. insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가한다. delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다. find(q) ::= 우선순위가 가장 높은 요소를 반환한다. 우선순위..
CS/자료구조
해싱해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.해시테이블: 키에 대한 연산에 의해 직접 접근이 가능한 구조해싱: 해시테이블을 이용한 탐색 이상적인 해싱 알고리즘add(key, value): index 실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 키당 해시테이블에서 하나의 공간을 할당할 수가 없다.mod를 사용하자h(k) = k mod M 충돌과 오버플로우충돌: 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상오버플로우 발생: 충돌이 발생하고, 해시 주소에 더 이상 빈 버킷이 남아 있지 않으면 발생해결법:개방 주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장체이닝: 해시 테이블의 하나의 위치가 여러 개의 항목을 ..
순차탐색int seq_search(int key, int low, int high){ int i; list[high + 1] = key; for (i = low; list[i] != key; i++) //키 값을 찾으면 종료 ; if (i == (high + 1)) return -1; // 탐색 실패 else return i; // 탐색 성공} 이진탐색정렬된 배열의 탐색에 적합함배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.search_binary(list, low, high): middle list[middle]) return list[middle + 1]부터..
정렬대상을 크기순으로 오름차순이나 내림차순으로 나열하는 선택 정렬 알고리즘selection_sort(A, n):for i 삽입 정렬 알고리즘insertion_sort(A, n):for i = 0 and A[j] > key do A[j + 1] 버블 정렬 알고리즘BubbleSort(A, n):for i 합병 정렬 알고리즘merge_sort(list, left, right):if left merge(list, left, mid, last):i 기수 정렬 알고리즘RadixSort(list, n):for d
그래프그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다.대표적인 예는 지하철 노선도가 있다. 개인적으로 대단하다고 생각하고 있다. 그래프의 정의와 용어정점(vertex): 위치라는 개념. (node라고도 부름)간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch라고도 부름)인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의..
트리트리는 계층적인 자료를 표현하는데 적합한 자료구조이다. 트리의 용어노드(node) : 트리를 구성하는 기본 원소노드 (root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드형제 노드(siblings node): 같은 부모 노드를 갖는 노드들리프 노드(leaf node/leaf): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서길이(length): 출발 노드에서 도착 노드까지 거치는 간선의 개수..
