뇌를자극하는알고리즘4 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 다음