A seeker after truth

* 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 1. 그래프 ADT(비방향성 그래프) 그래프는 그래프의 위치, 즉 정점(vertex)과 간선(edge)에 저장된 원소들의 모임이다. 각 vertex 객체 u는 다음과 같은 연산을 지원한다. - operator*(): u와 연관된 요소 반환 - incidentEdge(): u에 연결된 간선들의 간선 리스트 반환 - isAdjacentTo(v): u, v가 인접한지 테스트 각 edge 객체 e는 다음과 같은 연산을 지원한다. - operator*() - endVertices: e의 끝 정점을 포함하는 정점 리스트 반환 - opposite..

* 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 1. 이진 탐색 트리 아래 코드의 BinaryTree는 저번에 구현한 LinkedBinaryTree를 말한다. 2. AVL tree 극단적인 경우 이진 탐색 트리가 한쪽으로만 n개의 노드가 일렬로 늘어선 형태가 된다. 그러면 실행 시간이 O(n)이 되어 O(log n) 실행시간을 달성했다고 보기 어렵다. 이런 한계를 극복하기 위해 나온 것이 AVL tree다. 개념은 이 링크를 통해 공부하면 좋다. -> https://ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/ 이..

보호되어 있는 글입니다.

* 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 여기서 외부노드 = 자식 없는 노드 = leaf node 내부 노드. removeAboveExternal 메서드의 경우 아래 그림을 보면서 이해하면 쉽다. 여기서 sib가 곧 z다.

* 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 1. STL Queue / 큐 인터페이스 구현 STL vector를 기반으로 구현되어 있으며, STL vector와 같이 클래스 큐는 std 네임스페이스에 속하므로, 아래 코드의 두번째 줄처럼 해야 한다. 아래 코드는 한 예로 float의 큐를 선언한 것이다. #include using std::queue; queue myQueue; size, empty, push, pop, front, back 인터페이스를 가지고 있다. stl 말고 비공식적인 클래스로서 queue의 인터페이스를 구현해보면 아래와 같다. template class ..

* 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 1. STL을 사용할 경우 스택 객체를 선언하기 위해선 먼저 stack이라 불리는 정의 파일을 먼저 포함해야 한다. STL벡터 클래스와 마찬가지로 스택 클래스도 std네임스페이스에 포함되기 때문에, "std::stack"으로 사용하던지 using 문을 사용해야 한다. 스택 클래스는 개별 원소의 클래스를 사용할 수 있는 템플릿으로 만들어졌다. #include using std::stack stack myStack; 스택에 포함된 원소의 타입을 스택의 기본 타입이라 한다. STL 스택 역시 STL 벡터처럼 새 원소가 삽입되면 동적으로 자..