컴퓨터공학/알고리즘8 9장 그래프 *그래프의 첫 단원에는 대개 쾨니히스베르크의 다리라고 해서, 7개의 다리를 한 번씩만 건너서 모든 섬을 찍는 법은? 같은 인트로로 시작한다.*그러나 수학자 오일러는 그런 방법이 없다고 단언했다. 왜 그랬을까?*한붓그리기는 연결되어 있는 선이 홀수개인 점이 아예 없거나, 두개만 있는 도형에서만 가능하다.*그래프란 정점의 집합을 V, 간선의 집합을 E, 그리고 그래프를 G라고 했을때 G = (V,E)이다.*간선으로 연결된 두 점을 인접(adjacent)하다고 표현한다.*사이클(cycle)이란 어느 한 정점을 두 번 이상 거치도록 되어 있는 경우이다.*정점 사이의 인접 관계를 나타내는 방법은 인접행렬과 인접리스트, 두 가지 방법이 있다.*인접행렬은 정점의 개수X정점의 개수의 행렬을 만들어 두 정점이 인접한 경.. 2018. 10. 22. 8장 해쉬 *해쉬(hash)의 사전적 의미는 "잘게 자른 고기를 양파나 감자와 같은 다른 재료와 함께 튀겨 한 덩어리로 만든 요리", 여기서는 데이터를 입력받으면 해시함수를 통해 다른 형태로 데이터를 얻는다 정도 생각하자.*데이터를 담을 테이블을 미리 크게 확보한 후, 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것, 이것이 해시 테이블의 기본 개념이다. 여러 해시함수를 살펴보자.1.나눗셈법-해시함수 중에서도 가장 간단한 방법이다. 입력값을 테이블 크기로 나누고, 그 나머지를 인덱스로 활용하는 방법이다. -2의 제곱수 사이에 있는 소수를 테이블 크기로 활용했을때 가장 성능이 좋다.예제를 보자. typedef struct tagNode{ KeyType Key; ValueType V.. 2018. 10. 21. 7장 우선순위 큐와 힙 *우선순위 큐는 새 요소에 우선순위를 부여해서 큐에 삽입하고 가장 높은 우선순위를 갖는 요소부터 빠져나오도록 한다. *힙이란 힙 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리이다. ->완전 이진 트리란 가장 높은 높이의 원소들을 제외하고 왼,오른 자식들이 모두 채워져 있는 트리를 말한다. -힙 순서 속성이란, 모든 노드는 부모 노드보다 큰 값을 가진다. (루트는 예외) *힙의 루트노드는 최소값 노드라는걸 항상 보장한다. Heap의 삽입 연산의 순서를 알아보자. 1.힙의 최고 깊이의 가장 우측에 새 노드를 우선 삽입한다.(완전이진트리 유지) 2.삽입한 노드가 부모노드보다 작아질 때 까지 부모노드와 계속 교환해나간다. void HEAP_Inser(Heap *heap , Eleme.. 2018. 10. 21. 6장 탐색 순차탐색 *순차탐색은 정렬되지 않은 데이터 집합 속에서 원하는 데이터를 찾거나, 구현이 간단해서 데이터의 크기가 적은 곳에서 자주 쓰인다. *자기구성순차탐색이란 자주 사용되는 항목을 데이터의 앞 쪽에 배치하여 탐색 효율을 높인다. -전진 이동법: 탐색이 되면 가장 앞에(헤드에) 위치시킨다. -전위법:탐색된 항목을 바로 이전 항목과 교환한다. ->점진적으로 자주 탐색되는 항목은 앞쪽으로 모이게 된다. -계수법:원소별 탐색 횟수를 저장해놓고, 탐색 횟수별로 원소의 위치를 재구성하는 방식이다. 이진탐색 *탐색 범위를 1/2씩 줄여나가는 방식이다. *단, 미리 정렬되어 있어야한다. 탐색과정 1.데이터 집합의 중앙에 있는 요소를 고른다. 2.중앙 요소의 값과 찾고자 하는 값을 비교한다. 3.목표값이 더 크면 오른.. 2018. 10. 18. 5장 정렬 *버블정렬은 한 번 수행할 때 마다 가장 큰 수가 가장 오른쪽으로 차곡차곡 쌓인다.(오름차순으로 정렬시) *버블정렬의 일반화식은 n(n-1)/2 이므로, O(n^2) 이다.void BubbleSort (int DataSet[] , int Length){ int i = 0; int j = 0; int temp = 0; for ( i = 0 ; i DataSet[j+1]) { temp = DataSet[j+1]; DataSet[j+1] = DataSet[j]; DataSet[j] = temp; } } } } *삽입정렬과 버블정렬의 성능은 동일하다. 다만 삽입정렬.. 2018. 10. 15. 4장 트리 *완전이진트리란 차수가 2개이며 왼쪽에서부터 차곡차곡 자식을 가지고 있는 트리를 말한다.*전위순회:루트-왼자식-오른자식 순*중위순회:왼자식-루트-오른자식 순*후위순회:왼자식-오른자식-루트 순*후위순회를 응용하여 트리를 삭제할 수 있다.*분리집합이란 교집합이 존재하지 않는 두 집합을 말한다. 목적은 해당 원소가 그 집합에 속해있는지만 알아보는 것이다. 예를 들어 서점 판매관리 프로그램을 예를 들어보면 기본 자료구조가 가격과 ISBN을 가지고 있다고 가정해보자. 이 때 한시적으로 할인 행사를 진행하려고 하는데 할인행사를 할 때마다 가격을 내리고, 다시 원래 가격으로 돌려놓기가 꽤나 부담스럽다. 이 때 자료구조에 영향을 미치지 않고, 할인행사 집합과, 일반판매 집합을 분리할 수 있다. 따라서 할인행사 집합에 .. 2018. 10. 15. 3장 큐 *큐는 밀려드는 데이터를 순차적으로 처리하기 위해 고안됨 *순환 큐는 배열의 원소를 삽입,삭제할때 발생하는 땡기거나 밀어야 하는 비용을 없애고자 전단과 후단이라는 논리적인 개념을 도입한 큐 *실제 순환큐의 크기는 +1 하여 만들고, 비어있을때는 전단과 후단의 위치가 같고, 가득 찼을때는 후단이 전단보다 -1 작은 값을 가진다.*순환큐의 삽입은 현재 후단의 위치에 삽입 후 ++한다. (++한 위치가 capacitiy와 같다면 배열의 처음으로 후단을 옮긴다.)*순환큐의 삭제는 현재 전단의 위치를 ++증가시킨다.(덮어쓴다는 의미이다. ++한 위치가 capacity라면 배열의 처음으로 전단을 옮긴다.)*이 순환큐에서는 포화상태를 확인할 때 1. 전단이 앞 후단이 뒤일 경우 그 차이가 capacity인지 확인하는.. 2018. 10. 14. 2장 스택 1.다음과 같은 스택에서 70을 제거하려면 제거 pop연산을 모두 몇 번 수행해야 할까? ->100,90,80,70 총 네번 2.우리가 앞에서 만들어본 예제는 배열 기반 스택을 다음과 같은 구조체로 표현했다.Typedef struct tagArrayStack{ int Capacity; int Top; Node* nodes; } ArrayStack; 다음 AS_Push()함수를 스택 용량이 모두 소진될 때 현재 용량의 30%를 늘릴 수 있도록 개선하시오. Void AS_Push(ArrayStack* stack , ElementType Data){ //스택의 용량이 가득 찼으면 if( Stack->Top == Stack->Capacity) { ArrayStack *temp = new ArrayStack();.. 2018. 10. 14. 이전 1 다음