cpp44 C++로 쉽게 풀어쓴 자료구조 : 9장, 이진 탐색 트리 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 9장. 이진 탐색 트리 이진 탐색 트리는 이진트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 구조이다. 1) 모든 노드는 유일한 키를 갖는다. 2) 왼쪽 서브트리의 키들은 루트의 키보다 작다. 3) 오른쪽 서브트리의 키들은 루트의 티보다 크다. 4) 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. 정의 9.1 245페이지 Binary Search Tree ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: Binary Search Tree의 특성을 만족하는 이진트리: 어떤 node x의 왼쪽 서브트리의 key들은 x의 key보다 작고, 오른쪽의 .. CS/Data Structure (2021-1) 2022. 1. 15. C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 8 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 프로그래밍 프로젝트 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 (1) 이진트리가 완전 이진트리인지를 검사하는 연산 (2) 임의의 node의 레벨을 구하는 연산을 구현한다, 만약 node가 트리 안에 있지 않으면 0을 반환한다. (3) 이진트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이의 차이가 2보다 작으면 이 트리를 균형잡혀있다라고 한다. 현재 이진트리가 균형 잡혀 있는지를 검사하는 다음 연산을 구현한다. (4) 이진트리에서 경로의 길이를 루트에서부터 모든 자식 노드까지의 경로의 길이의 합이라고 하자. 경로의 길이를 구하는 연산을 구현한다 (5) 이진트리를.. CS/Data Structure (2021-1) 2022. 1. 14. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 7장, 순환 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 7장. 순환 이번장은 재귀, 순환에 대하여 배웠다. 사실 재귀는 친숙하면서도 새로운 개념이다. 이전에도 재귀를 사용해 미로 찾기, 하노이탑 등등 몇가지 문제들을 접한적이 있는데, 이번시간에도 다시 점검한다는생각으로 배웠다. 간단하게 미로찾기 코드정도만 올려야 겠다. 교제와 다른 방식으로 구현한 미로찾기 #include #include using namespace std; const int N = 8; const int PATHWAY = 0; const int WALL = 1; const int BLOCKED = 2; const int PATH = 3; int maze[N][N] = { {0,0,0,0,.. CS/Data Structure (2021-1) 2022. 1. 14. [자료구조] C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 5 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. DFS를 활용한 미로찾기 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 헤더파일에서는 using namespace std를 사용하지 않았습니다. 메인에서만 사용하였습니다. 헤더에서 이를 선언해버리면 이를 include하는 다른 소스파일에서까지 using namespace std가 적용되기때문에 헤더파일에서는 std::를 다 적어줬습니다. Location2D.h #pragma once struct Location2D { int _row; int _col; Location2D(int row = 0, int col = 0) : _row(row), _col(col) {} bool .. CS/Data Structure (2021-1) 2022. 1. 14. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 5장, Linked List 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 5장. 연결리스트 연결리스트의 개념 자체는 어렵지는 않다. Node마다 데이터를 저장하는 곳과, 다음 node를 가리킬 포인터변수가 있으며, 이를 필요할때마다 추가하면서 기차처럼 이어가는 형태이다. 열혈 자료구조에서도 C로 여러번 구현한 내용이다. Node class안에 Student 객체를 포함시키는 일반적인 방법이 난 가장먼저 떠올랐다. 다음처럼 말이다. class Node { Student st; // 데이터 필드 Node* link; // 링크 필드 public: ... }; 열혈 자료구조를 공부할때 이런 형태로 많이 구현해봤기 때문이다. 하지만 C++의 장점을 활용하는 코드가 나의 머리를 강타.. CS/Data Structure (2021-1) 2022. 1. 14. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 4장, Queue 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 4장. queue. deque Queue의 ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음 연산: - enqueue(e): 주어진 요소 e를 큐의 맨 뒤에 추가한다. - dequeue(): 큐가 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다. - isEmpty(): queue가 비어있는지의 유무를 bool값으로 반환 - isFull(): queue가 가득 차있는지의 유무를 bool값으로 반환 - peek(): queue가 비어있지 않으면 맨 앞의 요소를 확인해본다. - size(): queue의.. CS/Data Structure (2021-1) 2022. 1. 14. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 3장, stack 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 3장. stack stack의 ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모음 연산: - push(x): 주어진 인자 x를 stack의 맨위에 추가한다. - pop(): stack이 비어있지 않으면 맨 위의 요소를 삭제하고 반환한다. - isEmpty(): stack이 비어있는지의 유무를 bool값으로 반환 - isFull(): stack이 가득 차있는지의 유무를 bool값으로 반환 - peek(): stack이 비어있지 않으면 맨 위의 요소를 확인해본다. - size(): stack내의 모든 요.. CS/Data Structure (2021-1) 2022. 1. 14. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 2장, 배열과 클래스 응용 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 2장. 배열과 클래스의 응용 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 단원에서는 배열과 class에 대한 간단한 복습시간이였다. 간단하게 연습문제 푼 부분만 코드를 적고 넘어가겠다. 프로그래밍 프로젝트 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ● 다항식 클래스의 C++ 구현 (1) 두 다항식 a와 b의 뺄셈을 구하는 멤버 함수 sub를 구현하라 (2) 두 닿항식의 곱셈을 구하는 멤버 함수 mult를 구현하라 (3) 다항식의 연산결과 최고차항의 계수가 0으로 변할 수 있다. 현재 다항식의 계수를 분석해 최고차항의 계수가 0이 .. CS/Data Structure (2021-1) 2022. 1. 14. 이전 1 2 3 4 다음