CS/Data Structure (2021-1)30 [자료구조] Binary Search 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 글은 다들 아는 이진탐색에 대한 증명을 배웠다. 사실 이진 탐색 알고리즘 자체는 직관적이고, 이해하기가 쉽다. 문제는 이 당연한 것을 증명하려고 따지다 보니까 머리가 터지는 기분(살아있음에 감사함을)이 들었다. 이런거 증명해서 어디다 쓰지? 라고 생각할수도 있지만, 이런건 학생 신분일때 한번은 해봐야 향후 나의 발전에 큰 도움이 될거라 믿어의심치 않는다. Binary Search 의 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이진탐색의 코드를 확인해 보자. 아 그리고 이진탐색은 항상 sorting되어있어야만 한다. int.. CS/Data Structure (2021-1) 2022. 1. 22. [자료구조] 수학적 귀납법 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 다들 아는 일반적인 수학적 귀납법 설명하려고 이글 쓰는것이 아닙니다. 사실 귀납법 자체는 고등학교만 정상적으로 나왔으면 다 아는내용이다. 문제는 다음 2가지 측면에서 교수님의 가르침에 큰 놀라움을 얻었기에 이를 공유하고자 글을 써본 것 이다. 1) P(n-1)을 왜 참이라고 가정하는가? 참인지는 어찌알지?? 2) 귀납법을 통해 재귀함수를 어떻게 인식해야 하는가? 수학적 귀납법 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ● 수학적 귀납법의 기본형 (1) Base: P(1)이 참이고 (2) Step: P(n-1) -> p(n) 이 참이라면 .. CS/Data Structure (2021-1) 2022. 1. 22. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 14장, 탐색 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 14장 탐색 탐색은 하나 이상의 field로 구성된 record의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이런 레코드의 집합을 table이라고 부른다. 레코드들은 각각 고유한 키값을 갖는데, 이를 탐색키(search key) 라고 부른다. 자료 검색은 테이블에서 해당 탐색키를 찾는 것 이다. C++로 쉽게 풀어쓴 자료구조 (14장, 탐색) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 키와 값을 가진 요소 (key, value)의 집합 연산: - create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성. .. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 13장, 정렬 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 13장 정렬 정렬이란 물건을 크기순으로 오름차순이나, 내림차순으로 나열하는 것 을 의미한다. 일반적으로 정렬시켜야할 대상을 레코드(record)라고 불린다. 레코드는 다시 field라고 하는 보다 작은 단위로 나누어 진다. 여러 필드중 레코드들을 구분해주는 역할을 key가 한다. 선택 정렬 (selection sort) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 정렬되지 않은 숫자가 모여 있는 리스트 B 와 정렬이 완료된 숫자들이 들어가는 리스트 A 가 있다고 하자. A{ } : B{5, 3, 8, 1, 2, 7} 선택 정렬은 B의 리스트에서 가장 작은 숫자를 선택.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 12장, 가중치 그래프 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 이번 12장 책 코드에 중간중간 오류코드들이 보인다... 이해를 조금 방해하는 수준이다. 1) 12장. 가중치 그래프(Weighted Graph) 가중치 그래프는 이전에 만들었던 AdjMatGraph class를 상속하여 사용한다. 이전에 사용했던 인접행렬에서는 간선이 있으면 1 없으면 0을 행렬에 저장했지만, 이번에는 가중치값을 행렬에 저장하였다. 일정 범위를 두고 그 범위 안의 값이면 간선이 있고, 이를 벗어나는경우는 간선이 없다고 여긴다. WGraph.h #pragma once #include "AdjMatGraph.h" const int inf = 100; class WGraph : public Ad.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 11장, 그래프 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 11장. 그래프(Graph) Graph의 ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 정점의 집합과 간선의 집합 연산: - creat(): 그래프를 생성한다. - isEmpty(): 그래프가 비어있는지 확인한다. - insertVertex(v): 그래프에 정점 v를 삽입한다. - insertEdge(u, v): 그래프에 간선 (u, v)를 삽입한다. - deleteVertex(v): 그래프의 정점 v를 삭제한다. - deleteDdge(u, v): 그래프의 간선(u, v)를 삭제한다. - adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 10장, 힙 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 10장. 힙(Heap) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 큰(or작은) 이진트리 를 말한다. A가 B의 부모 노드라고 가정하면, key(A) >= key(B) 인경우가 최대 힙이 되며, key(A) HTML 삽입 미리보기할 수 없는 소스 insert(key) heapSize HTML 삽입 미리보기할 수 없는 소스 void heapSort(int a[], int n) { MaxHeap h; for (int i = 0; i = 0.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9-1 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 프로그래밍 프로젝트 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1) 9.2절에서 이진 탐색 트리의 탐색 연산을 트리 클래스에서 구현했고 노드 클래스에서도 구현해 보았다. 트리의 각 노드들을 모두 자신을 루트로 하는 서브트리를 대표한다고 보면 많은 트리의 연산들을 노드에서 구현할 수 있다. 8장의 프로그램 8.1과 프로그램 8.2를 수정하여 BinaryTree 클래스에서 구현했던 다음 멤버함수들을 BinaryNode 클래스에서 구현해라. void BinaryNode::inorder(); void BinaryNode::preorder(); void BinaryNode::po.. CS/Data Structure (2021-1) 2022. 1. 15. 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++로 쉽게 풀어쓴 자료구조 : 8장, 트리 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 8장. 트리 대부분의 교제에서 가르치는 트리중 대표가 아마 이진트리 일 것 이다. 이진트리의 정의를 간략히 살펴보자! 1) 공집합이거나 2) 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 정의된다. 이진트리의 서브트리들은 모두 이진트리여야 한다. 정의 8.1 299페이지 Binary Tree 의 ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 노드와 간선의 집합. 노드는 공집합이거나 공집합이 아니라면 루트노드와 양쪽 서브트리로 구성된다. 모든 서브트리는 이진트리여야 한다. 연산: - create(): 이진트리를 생성한다. - is.. 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. 이전 1 2 3 다음
