우당탕탕 코딩도전기

강의 내용 정리(Weighted graph, shortest path algorithm, minimum spanning tree)

숙제 12-1 연습문제 교재 p.461 (1) 교재에 있는 그래프에 대하여 정점 3에서 출발하여 너비 우선 탐색을 한 경우의 방문 순서를 쓰세요. 3 1 4 0 2 5 6 7 8 9 (3) 정점 3에서 출발하여 깊이 우선 탐색을 한 경우의 방문 순서를 쓰세요. 3 4 2 1 0 5 6 7 8 9 숙제 12-2 위와 같이 그래프가 주어졌을 때, V(정점집합), E(간선집합)을 쓰세요. V = {A, B, C, D}, E = {(A, B), (B, D), (C, D)} •Adjacent list(인접 리스트)를 쓰세요. A -> B B -> D C -> D D •Topological sort(위상 정렬)하여 정점을 나열하세요. A - B - C - D C - A - B - D •위상 정렬 알고리즘 pseud..

1. 교재 MaxHeap 예시 코드 변경한 코드 #include using namespace std; #define MAX_ELEMENT 200 class HeapNode { int key; public: HeapNode(int k = 0) : key(k) {} void setKey(int k) { key = k; } int getKey() { return key; } void display() { cout getParent(i).getKey()) { node[i] = getParent(i); i /= 2; } node[i].setKey(key); } HeapNode remove() { if (isEmpty()) return HeapNode(); HeapNode item = node[1]; HeapNod..

1. 첨부의 코드를 이해하고, 첨부 코드를 이용해 BinSrchTree 클래스의 search 함수를 구현하세요(주석 표기된 부분). BinaryNode* BinSrchTree::search(BinaryNode* n, int key) { if (n == NULL) return NULL; if (key == n -> getData()) return n; else if (key getData()) return search(n->getLeft(), key); else return search(n->getRight(), key); } 2. 1번을 수행한 뒤, 교재 9장 프로그래밍 프로젝트 1번 중 하나인 getHeight 함수(트리의 높이를 구하는 함수)를 구현하세요. 트리의 높이에 대한 정의는 교재의..

문제 원판이 4개일 때 하노이탑 풀이 과정 서술하기 코드 #include using namespace std; void hanoiTower(int n, char from, char tmp, char to) { if (n == 1) cout

1. Solve the exercise problem 14 of the chapter 7. 문제 14번: 합병정렬 알고리즘에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2nlgn이 됨을 증명하시오. 합병정렬에서 주어진 배열의 크기가 n이라고 하면, 배열을 반으로 나누는 과정에서 각각의 하위 배열에 n/2개씩 원소가 들어간다. 각각의 하위 배열에 대하여 현재 배열과 하위 배열의 정렬을 수행하고, 이를 합병하는 과정에서 새로운 배열을 생성하여 정렬된 레코드를 저장한다. 이때, 새로운 배열의 크기는 두 하위 배열의 크기를 합친 것과 같기 때문에, 각 하위 배열의 크기가 n/2인 경우, 새로운 배열에는 n개의 레코드가 저장된다. 각각의 하위 배열에 대해 정렬하는 과정에서도 각 레코드..

문제 1. 클래스 설계 노드 클래스를 단순하게 만들고 연결 관계를 포함한 노드 처리 연산을 리스트 클래스에서 구현하는 방법과 노드 클래스에서 가능한 많은 기능을 구현하고 리스트 클래스에서 이들을 사용하는 방법의 차이점은 이렇게 정리할 수 있다. 첫 번째 방법은 리스트 클래스의 구현을 간단하게 할 수 있다. 노드 클래스는 단순해져서 가독성이 높아지며, 노드 처리 연산의 구현에 대한 책임이 리스트 클래스로 넘어가므로 유지보수성이 좋아진다. 또한, 리스트 클래스에 다양한 기능을 추가하기도 쉬우므로, 유연성이 높아진다는 장점이 있다. 반면에 두 번째 방법은, 노드 클래스에서 다양한 기능을 지원할 수 있다는 점에서 첫 번째 방법과 다르다. 이는 노드 클래스의 객체를 만들 때 필요한 정보가 적어지므로 객체 생성에 ..

문제 1. Describe linear median finding algorithm. Show that its time complexity is Θ(n). Linear median finding 알고리즘은 intelligent quick sort의 다른 이름으로, quick sort에서 사용되는 기준점(pivot) 값을 애초에 median, 즉 중앙값으로 설정하여 더 용이하게 숫자를 비교할 수 있도록 만든 알고리즘이다. 여기서 중앙값이란 데이터 개수를 딱 절반으로 나누는 수를 의미한다. 이 중앙값과 n개의 숫자를 비교하여 숫자가 중앙값보다 작으면 앞으로, 크면 뒤로 보내는 알고리즘을 loop를 통하여 반복한다. 중앙값이 데이터의 가장 크거나 작은 값인 경우 데이터의 각 요소를 모든 요소와 비교해야하기 때..