'프로그래밍/자료구조' 카테고리의 글 목록

프로그래밍/자료구조

Emong's Factory

[자료 구조][알고리즘] 선택 트리(selection tree) - 승자 트리(winner tree),패자 트리(loser tree)

2018.12.11

선택 트리(selection tree) 하나의 순서 순차(ordered sequence)로 합병 될 런(run)이라 부르는 k개의 순서 순차가 있다고 가정하자. 각 런은 key라고 하는 지정된 필드에 따라 비감소 순서로 정렬된 약간의 레코드들로 구성된다. 선택 트리(selection tree) 자료 구조를 이용하면, 다음으로 가장 작은 레코드를 발겨하는데 필요한 비교 횟수를 줄일 수 있다. 선택 트리에는 승자 트리(winner tree)와 패자 트리(loser tree) 두 종류가 있다. 승자 트리(winner tree) 승자 트리는 각 노드가 2개의 자식 노드 중 더 작은 노드를 나타내는 완전 이진 트리이다. 그러므로 루트 노드는 트리에서 가장 작은 노드를 나타낸다. 각 리프들은 각 런에 첫번째 값이다..

[자료 구조][알고리즘] 이원 탐색 트리(binary search tree)

2018.12.11

이원 탐색 트리(binary search tree) 이진 트리로서 공백일 수 있다. 만약 공백이 아니라면 다음 성질을 만족한다. 1) 모둔 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다. 2) 왼쪽 서브트리에 있는 키들은(만약 있다면) 그 루트의 키보다 작다. 3) 오른쪽 서브트리에 있는 키들을(만약 있다면) 그 루트의 키보다 크다. 4) 왼쪽과 오른쪽 서브트리도 모두 이원 탐색 트리이다. 첫 번째 트리가 이진 탐색 트리가 아닌 이유는 10이 15보다 작음 에도 오른쪽 자식에 위치해 있기 때문이다. 이진 탐색 트리는 정렬된 트리이다. 이원 탐색 트리의 탐색 키 값이 k인 원소를 탐색한다고 가정하자. 탐색은 루트에서부터 시작하는데 만약 루트가 NULL이면 탐색 트리는 원소를 갖지 않으므로 ..

[자료구조][알고리즘] 히프(heap) - 최대 히프(max heap), 최소 히프(min heap)

2018.12.11

히프(heap) 히프는 우선순위 큐(priority queue)를 구현하는 데 자주 사용된다. 우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다. 히프 또한, 완전 이진 트리(complete binary tree) 이다. 히프에는 최대 히프와 최소 히프가 있다. 최대(최소)트리[max(min) tree)]는 각 노드의 키 값이( 자식이 있다면) 그 자식의 키값보다 작지(크지) 않은 트리이다. 최대 히프(max heap)는 최대 트리이면서 완전 이진 트리이다. 최소 히프(min heap)는 최소 트리이면서 완전 이진 트리이다. 최대 히프에서의 삽입 새 노드에서 시작해서 루트 쪽으로 올라가는(bubblin..

[자료 구조][C언어] 이진 트리 순회(traversal) - 중위(inorder), 전위(preorder),후위(postorder) 순회

2018.12.10

이진 트리 순회 중위 순회(inorder traversal) 1) 더 이상 진행할 수 없을 때까지 왼쪽 방향으로 이동하여 내려간다. 2) 그 노드를 '방문'하고 오른쪽 자식 노드로 이동한 뒤 계속한다. 3) 이때 오른쪽으로 이동할 수 없을 때에는 한 노드 뒤로 되돌아간다. void inorder(treePointer ptr) { /*중위 트리 순회*/ if (ptr) { inorder(ptr->leftChild); printf("%d", ptr->data); //왼쪽에서 리턴될때 프린트 inorder(ptr->rightChild); } } inorder 처리 과정 반복 중위 순회(iterInorder) void iterinorder(treePointer node) { int top = -1; /*스택 초..

[자료 구조][알고리즘] 트리(tree)

2018.12.10

트리트리는 다음과 같은 하나 이상의 노드의 유한 집합이다.1) 루트라 불리는 특별히 지정된 노드가 있다.2) 나머지 노드는 n>=0 disjoint set T1,...,Tn으로 분할한다. 여기서 각각의 노드는 트리이고, T1,...,Tn은 루트의 하위 트리라고 불린다. - 노드(node) : 한 정보 아이템에 다른 노드로 뻗어진 가지를 합친 것을 의미한다.- 차수(degree) : 한 노드의 서브트리의 수- 리프 (leaf) : 차수가 0인 노드 , 단말 노드(terminal node)라고도 한다. - 현 노드위 상위 노드를 부모(parent)라 하고 부모 하위 노드를 자식(child)이라고 하며 이웃한 노드를 자매(sibilings) 노드라고 한다.- 트리의 차수(degree of a tree) : 그..

[자료 구조][알고리즘] 히프정렬 (heap sort)

2018.12.10

히프정렬 (heap sort) 합병 정렬방식은 비록 최악의 경우 연산 시간과 평균 연산 시간 모두 O(nlogn)이지만, 정렬할 레코드 수에 비례하여 저장 공간이 추가로 필요하다. 히프 정렬(heap sort)은 일정한 양의 저장 공간만 추가적으로 필요한 동시에, 최악의 경우 평균 연산 시간이 O(n log n)이다. 하지만, 히프 정렬은 합병 정렬보다 약간 느리다. 히프 정렬의 핵심 알로리즘은 이름처럼 히프를 사용한다. 그중에서도 최대 히프 구조를 이용한다. 따라서, 최대 히프가 되도록 레코드를 재조정 후 루트를 하나씩 빼내면서 정렬을 하는 기법이다. 알로리즘을 정리하면, 1. 최대 히프 생성 2. 히프의 첫 번째 와 마지막 레코드 스와핑 3. 히프 크기 감소 및 재조정 4. n-1 반복 최대 히프 생..

[자료 구조][C언어] 합병 정렬(merge sort)

2018.12.10

합병 정렬(merge sort) 2개의 정렬된 리스트를 하나의 정렬된 리스트로 합병하여 정렬하는 정렬기법. while 루프를 반복할 때 마다 k는 1씩 증가. k의 총 증가량 n-1+1 for 명령문은 최대 n-i+1 레코드를 복사한다. 레코드 길이 s 가 1보다 클 때 배열 대신 연결 리스트를 이용하면 이들 n-l+1 레코드를 포함한 새로운 정렬된 연결 리스트를 얻을 수 있다. merge 함수에서 배열 mergedList 가 필요한 n-l+1 개의 레코드 공간이 필요 없게 된다. 대신 n-l+1 개의 링크에 대한 공간이 필요하다. void merge(element initList[], element mergedList[], int i, int m, int n) { int j, k, t; j = m + ..

[자료 구조][C언어] 퀵 정렬(Quick Sort)

2018.12.09

퀵 정렬(Quick Sort) 삽입 정렬은 아주 좋은 평균 정렬 성능을 가지는 정렬 알로리즘이다. 퀵 정렬은 피벗을 정하고 왼쪽과 오른쪽에서 각각 시작하여 왼쪽부터는 피벗이 크거나 같으면, 오른쪽에서는 피벗보다 작거나 같으면 두 값을 스왑 해주고, 오른쪽 값과 왼쪽값이 서로 교차할때 새로운 피벗을 설정하여 이 작업을 재귀적으로 실행하는 방법이다. pivot 26이라고 가정하면 26보다 37 크니 멈추고 19가 피벗보다 작으니 멈추면 둘이 교환한다. 그리고 61 과 15 가 되면 스왑하고 둘이 교차하여 피벗과 right를 스왑해준다. 이 과정을 반복한다. void quickSort(element a[], int left, int right) { int pivot, i, j; element temp; if ..

[자료 구조][C언어] 삽입 정렬(Insertion Sort)

2018.12.09

삽입 정렬(Insertion sort) 새로운 레코드를 i개의 정렬된 레코드 리스트에 끼워넣어 크기가 i+1로 정렬된 결과 레코드 리스트를 만드는 것이다. 즉, a[0]을 사용하면 리스트 끝 검사(즉, i key.key1) //자리바꿈 { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } void InsertSort_key2(array arr[], int n) //key2 값을 기준으로 { int i, j; array key; for (i = 1; i = 0 && arr[j].key2 > key.key2) { arr[j + 1] = arr[j]; j--; } arr[j +..

[자료 구조][C언어] 해싱(hashing)

2018.12.09

해싱(hashing)? 해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다. 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다. 슬롯이 한개일 경우 무조건 충돌이 일어나며 우리는 충돌은 피할 수 없으므로 최대한 적게 일어나는 쪽으로 설계 해야 한다. 슬롯이 한개일 경우에는 오버플로우와 충돌은 같다. Hashi..

Emong's Factory

티스토리툴바