CS/Data Structure (2021-1)30 [자료구조] The Halting Problem (정지 문제) 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 1. Halting Problem이란? 어떤 프로그램이 어떠한 입력값을 받았을 때 종료되는지 아닌지를 돌려보기 "전에" 알 수 있는가? 당연히 프로그램을 돌려봐서 끝난다면 끝난다는 것 을 알수 있지만, 우리는 프로그램을 돌리기 전에 먼저 알고싶다! 코드를 작성하다보면 컴파일에러도 잡아주고, 문법에러도 잡아준다, 어찌 저찌 잘 해보면 실행전에 종료되는지의 유무를 알수 있지 않을까? 1 - 1) 문제의 목적 세상엔 컴퓨터로 풀기 쉬운 문제가 있고, 풀기 어려운 문제가 있다. 그런데 세상엔 컴퓨터로 풀 수 없는 문제도 있다. 정지 문제는 컴퓨터로 풀 수 없는 문제들 중 하나이다... CS/Data Structure (2021-1) 2023. 3. 5. [자료구조] Priority Queue, Dijkstra 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번시간에는 우선순위 큐 (priority queue)에 대하여 배웠다. 일반적인 queue는 후입 선출의 과정, 즉 먼저 들어간 원소가 먼저 나오는 방식이지만 우선순위 큐는 각 원소마다 우선순위가 정해져서, 우선순위가 높은 원소부터 먼저 나오는 방시이다. Priority Queue " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 Queue 이긴 한데, 원소들이 우선순위를 갖고있다. 우선순위가 높은 원소가 먼저 나온다. 가능한 배열 구현 종류 - Sorted by priority : 빠른 삭제연산, 하지만 삽입이 느리다. - Unsorted .. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] 2-3-4 Tree, Red-Black Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 2-3 Tree의 확장 버전인 2-3-4 Tree에 대하여 배웠으며, 이를 Red-Black Tree로 표현하여 보았다. 2-3 Tree가 궁금하다면 이전 글을 먼저 확인해보길 권장한다. [자료구조] AVL Tree, 2-3 Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 AVL-Tree에 대하여 배웠다. AVL-Tree 는 BS blogshine.tistory.com 2-3-4 Tree " data-ke-type="html"> HTML 삽입 미리보기할 .. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] AVL Tree, 2-3 Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 AVL-Tree에 대하여 배웠다. AVL-Tree 는 BST가 최악의 경우 linked-list 처럼 이어저 O(n)의 시간복잡도의 성능을 보여준다는 단점을 보완하는 tree이다. AVL-Tree의 직관적 이해 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 다음 그림을 통해 AVL-Tree가 어떻게 보정 작업을 하는지 살펴보자. 왼쪽의 경우 root 노드인 6을 기준으로 왼쪽으로 node들이 치우쳐 있는 모습을 볼 수 있다. 이 tree의 H(높이)는 4에 해당한다. 이를 AVL-Tree의 정의에 부합하도록 보정 작업을 해주면.. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] Binary Search Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 이진탐색트리 에 대하여 배우는 시간이였다. 이진탐색의 방식으로 만들어진 트리라고 생각하면 쉽다. 크게 Search, Insert, Delete 3가지 기능이 필요한데 Delete의 경우 삭제할 Node의 자식이 몇명인지에 따라 case가 나뉜다. 우선 Skip List에 대하여 간단하게 살펴보자. Skip List " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 Skip LIst란 여러 node를 건너뛸 수 있는 Linked List를 말한다. 이를 활용하여 중간 지점으로 건너 뛸 수 있다면, 이진탐색의 방식을 Linked Li.. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] Linked List 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 연결리스트(Linked List)에 대하여 배웠다. 사실 연결리스트만 해도 내가 직접 구현해본 경험이 이미 여러번 있고 쉬운내용이라 이해하는데 어렵지 않았다. 윤성우 열혈, C++로쉽게풀어쓴 자료구조, 알고리즘책 등등 이미 많은 책에서 자주 접했던 내용이다. 구현부분은 조금 대충한 느낌이 있는데... 예전 글에서 더 정성스럽게 구현한 경험이 있으니... 이 글에서는 돌아갈정도만 구현하는걸로.... Linked List " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 연결리스트 란 노드를 data 와 다음 노드를 가리킬 포인터로 .. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] Equivalence Relation 출처: https://privatedevelopnote.tistory.com/81 [개인노트] 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 Equivalence Relation(동치관계) 에 대하여 배웠다. 이산수학에 나오는 내용으로 그레프 이론과 연계되는 것 같다. 우선 relation에 대하여 알아본 후, Equivalence Relation에 대하여 알아보자. Relation " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 relation이란 다음과 같다. 이를 좀더 해석해보면 Relation이란 한 집합 위에서 정의되는 관계를 말한다. 처음들어서는 명확하지 않.. CS/Data Structure (2021-1) 2022. 1. 24. [자료구조] Stack, Queue 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. Stack " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 Insert / Delete만 제공한다. search가 없다. push를 통해 data를 추가하고, pop을 통해 data를 삭제한다. 마지막에 추가한(push) data가 먼저 삭제되기때문에 Last in First out 줄여서 LIFO 라고도 부른다. Push와 Pop모두 상수시간안에 진행된다. O(1) ▶ stack을 구현할때는 다음에 넣을 자리를 가리키는 stack pointer가 하나 필요하다. 위의 사진에서 예를들어 2를 막 push한 상황이라면 2의 위를 stack po.. CS/Data Structure (2021-1) 2022. 1. 24. [자료구조] String Matching 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. String Matching " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 string에서 내가 원하는 문자열을 찾는 방법을 말한다. 예를 들어 abababcabcabcdabccbaabdabcabcdabcd 라는 Text가 있다고 해보자. 우리는 이중에서 abcabcd 라는 pattern을 찾아야 한다. 수업시간에는 총 3가지 알고리즘을 알려주셨다. 1) Naive 2) DFA (Deterministic Finite Automaton) 3) KMP (Knuth, Morris, Pratt) 이중 가장 빠른 알고리즘은 KMP 알고리즘 이며, 만.. CS/Data Structure (2021-1) 2022. 1. 24. [자료구조] 배열의 성능 분석 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 배열의 성능 분석 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 배열의 정의부터 살펴보고 시작하자. Array: 동일한 type이 연속된 주소에 저장된다. 같은 배열이라도 값이 한쪽에 모여있을 수 도 있고, 산발적으로 흩어져 있을 수 도 있다. 또 값들이 순서대로 정렬되어 있을 수도 있고 그렇지 않을 수도 있다. 이러한 특성들이 배열의 성능에 큰 영향을 미친다고 한다. 또한 값을 Array에 넣는 방식에 따라서 Search, Insert, Delete의 성능이 달라진다. ● Packed vs Unpacked 원소들이 저장될때 배열의 한.. CS/Data Structure (2021-1) 2022. 1. 24. [자료구조] Merge Sort 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 원래 Merget Sort를 증명하려면 Merge의 정확성 부터 증명한 후, 다시 Merge sort를 증명해야하는데, 수업시간에는 Merge의 정확성은 타당하다는 가정 하에 증명해 주셨다. Merge의 정확성 까지 보일필요는 없을거라 하셨다. Recursive Merge Sort 의 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 int MergeSort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] MergeSort(b, h); // b의 왼쪽 절반 정렬 Merge.. CS/Data Structure (2021-1) 2022. 1. 23. [자료구조] Selection Sort 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 선택정렬에 대하여 증명하였다. 알고리즘에 관한 증명들을 먼저 알려주시고 있는데, 이후에 연결리스트나, 스택 등을 설명해주신다 하셨다. Sorting의 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 선택정렬을 증명하기에 앞서서, 우선 정렬 자체를 어떻게 증명할것인가? 에 대하여 답해보고 시작해보자. ▶ 입력으로는 a[0], a[1], ..., a[n-1] 의 집합이 들어온다. ▶ Sorting이 완료된 후 다음이 만족되어야 한다. sorting이 끝난후 배열에 저장된 값을 b[0], b[1], ..., b[n-1] 이라고 하자. - 조건.. CS/Data Structure (2021-1) 2022. 1. 22. 이전 1 2 3 다음
