자료구조C++프로그래밍 (자료구조 구현 소스코드)
홍봉희 | 부산대학교출판문화원
18,050원 | 20220831 | 9788973167524
SW 코딩 역량은 자료구조 구현 능력에 달려 있다. 어떤 자료구조를 사용하느냐에 따라 구현된 SW의 성능과 기능이 달라진다. SW 개발은 class와 함수를 만드는 것이다. main( ) 함수는 가능한 한 데이터 입력, insert, delete, search 등의 다른 함수 호출만 사용하는 것이 좋다. SW 코딩 능력은 class에 어떤 함수를 만들고 어떤 변수를 사용하여 알고리즘을 구현할 것에 대한 design choice를 잘하는 능력이다. 예를 들면 search 함수를 만들 때 class의 public member 함수로 만들 것인지 아니면 일반 함수로 만들 것인지를 선택(choice)해야 한다.
C++ 언어를 구사할 수 있어야 C++로 된 자료구조를 공부할 수 있다. 이 책은 C++를 사용하여 구현된 소스 코드를 포함하고 있다. 자료구조는 이론 과목이 아니므로 각 자료구조에 대하여 소스 코드를 사용하여 구현하고 test하는 실습으로 습득해야 한다. 추천하는 자료구조 학습 방법은 단순히 제시된 소스 코드를 보지 말고 필요한 소스 코드를 작성하는 연습을 반복하는 것이다. 그리고 제시된 소스 코드에 새로운 기능을 추가하거나 성능을 개선하는 소스 코드 변경 작업을 통하여 구현 능력을 향상하는 것이 바람직하다.
이 책에서는 자료구조에 대한 insert, delete, search 등을 처리하기 위하여 입력 데이터를 받아 해당 자료구조를 만드는 방법에 중점을 두었다. 구현하고자 하는 자료구조를 동작시키기 위해 화면에서 데이터를 임의로 입력받거나 난수를 생성하여 자동으로 해당 자료구조를 만드는 방법으로 실습하는 것이 효과적이다.
자료구조와 알고리즘은 별개의 다른 주제가 아니고 매우 밀접하여 거의 하나의 topic이라고 생각해야 한다. 예를 들면 2개의 linked list를 merge 하는 알고리즘의 구현은 singly linked list, circular linked list, head node가 있는 circular linked list 등에 따라 달라진다. 즉, class의 data member 변수를 어떻게 사용하느냐에 따라 구현 알고리즘이 복잡해질 수도 있고 간단해질 수도 있다. 따라서 자료구조의 설계, 자료구조의 data representation에 따라 알고리즘의 성능도 달라질 수 있다.
stack, queue, linked list, tree, hashing은 C++ STL에서 제공하므로 굳이 자료구조를 만들 필요가 없다고 오해할 수 있다. C++ STL을 사용하면 구현이 간단해질 수는 있으나 성능이 떨어질 수 있다. 응용에 따라 C++ STL을 가져다 사용하는 것이 좋을 수도 있고 직접 hash map, heap 등을 구현하여 사용하는 것이 더 우수할 수도 있다.
자료구조와 알고리즘 내용으로 이 책에서 다루지 못한 heap structure로서 leftist tree, binomial heaps, Fibonacci heaps와 search structures로서 AVL tree, 2-3 trees, 2-3-4 trees, red-black tree, B-tree, splay trees, digital search tree, trie를 학습하여 SW 코딩의 진정한 고수가 되기를 바란다.
