승1's B(log n)

알고리즘에서 엄청나게 유명한 하노이의 탑 문제이다. 엄청나게 유명한 것에 비해서 난이도가...그렇게 높진 않고 랭크도 높아서 조금 의아. 암튼 입력과 출력은 이래야 된다. 구현은 C++로 해보았다. 재귀함수 형식으로 구현하면 쉽게 풀린다. #include #include using namespace std; void HanoiTower(int num, int from, int by, int to){//from에 있던 num개의 원반을 by를 거쳐 to로 이동시키는 함수 if (num == 1){//이동해야 할 원반의 수가 1개인 경우 그냥 옮기면 됨. 그리고 탈출 조건이 됨. printf("%d %d\n", from, to); } else{ HanoiTower(num-1, from, to, by); pr..

마지막 과제는 바로 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..