승1's B(log n)

1) DFS(Depth-First Search) 깊이우선탐색 깊이우선탐색은 캐쥬얼하게 말하자면 깊이 들어갈 수 있을 만틈 들어갔다가 더 이상 들어갈 수 없을 때 뒤로 빠져나와 다른 길로 깊이 들어갔다 나왔다 하는 것을 반복하는 방법이라고 할 수 있다. 말로만 들어서는 어려우니 그림을 보면서 이해해보자. 우선 노드의 인덱스가 0부터 7까지 존재하는 그래프를 생각해보자. 각각의 노드들은 서로 다른 노드들과 연결되어 있는데, 이해의 편의를 위해서 가운데처럼 Adjacency List로 만들어보았다. 인덱스가 0인 노드는 인덱스가 1과 2인 노드들과 연결되어 있고, 인덱스가 1인 노드는 인덱스가 0, 3, 4인 노드들과 연결되어 있다. LIFO(Last In First Out)구조인 스택을 이용하면 DFS를 이..

최대공배수(Least Common Multiple)를 구하기 위해서는 우선 최대공약수(Great Common Divisior를 구하는 법에 대해서 알 필요가 있다. 1) 최대공약수 구하기 최대공약수를 구하는 법은 유클리드 호제법을 이용하면 된다. 유클리드 호제법은 a와 b의 최대공약수를 구할 때 사용이 되는데, a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다는 공식이다. 이를 코드로 표현해보면 int GCD(int a, int b){ if(a % b == 0) return b; else return GCD(b, a % b); } 이렇게 나타낼 수 있다. 2) 최소공배수 구하기 최대공약수를 구했다면 최소공배수를 구하는 일은 식은 죽 먹기다. 마찬가지로 유클리도 호제법에 의하면 최소공..

마지막 과제는 바로 Search Tree를 구현하는 것이었다. 일반적인 BST와 AVL Tree들을 구현해서 실행시간을 비교하고 레포트까지 작성하는 것이 과제였다. 사실 이번 과제는 교재(Data Structures&Algorithms in C++ 2nd Edition by Michael T.Goodrich, Roberto Tamissa, David M.Mount)에서 많은 도움을 얻었다. 교수님께서도 그래도 된다고 하시기도 하셨고, 스켈레톤 코드도 상당 부분 유사했다. 그러나 완전히 동일하지는 않았고 어느 정도 응용을 했어야 했다. 주어진 파일은 6개로, AVL Tree 구현에 사용되는 파일 두 개, BST 구현에 사용되는 파일 두 개, 메인 파일 한 개, AVL과 BST의 기초가 되는 Linked B..

세번째 과제는 바로 Hash Map을 응용하여 문장에서 단어의 빈도수를 파악하는 프로그램을 제작하는 것이었다. 특이 사항은 모든 단어를 소문자로 바꿔서 생각하고, non-alphabetic 글자들을 무시하도록 하는 것이다. 더불어 non-alphabetic한 글자들이 들어가있을 경우 그것을 delimiter로 사용하여 글자를 분리시킨다. 예컨대, "I'm"은 "i" + "m"으로 각각 취급한다. 주어진 파일은 총 9개. 이 중에서 map.txx 파일과 wordfrequency.cpp 파일을 수정 및 구현하여 제출하도록 되어있었다. 1-1) 구현해야 하는 함수들 - map.txx // destructor template HashMap::~HashMap() { // ToDo } template HashMap..

두번째 과제는 Doubly Linked List를 응용하여 간단한 문서편집기를 만드는 것이었다. 주어진 파일은 총 다섯개로, doublylinkedlist.h, doublylinkedlist.txx, main.cpp, texteditor.cpp, texteditor.h가 주어졌고 이중에서 doublylinkedlist.txx 파일과 texteditor.cpp 파일을 수정하여 제출해야 했다. 1-1) 구현해야 하는 함수들 - doublylinkedklist.txx class Iterator : public Iterator_Base { public: Iterator(NodeType * startNode = 0) : Iterator_Base(startNode) {} Iterator& operator++(); ..

해당 과제에서는 다항식 ADT(Abstract Data Type)를 사용해서 다항식 계산기를 만드는 것을 목표로 한다. 1) polynomial.h 구현해야 하는 함수들 : Polynomial (const Polynomial& source) : copy constructor • ~Polynomial() : destructor • Polynomial& operator= (const Polynomial& source): Assignment operator • Polynomial operator+ (const Polynomial& source) : Sum of polynomials • Polynomialoperator- (const Polynomial& source): Subtraction of polynom..