자료구조론47 [자료구조] 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. [서평] C++로 쉽게 풀어쓴 자료구조 저의 돈으로 직접사서 직접 완독해본후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할것이며, 단점은 단점대로 언급할 것 입니다. C++로 쉽게 풀어쓴 자료구조 저자 : 천인국, 최영규 출판 : 생능출판사 발매 : 2016.08.09 2021/02/18 ~ 2021/03/15 1) 책의 표지 2) 단원별 요약 3) 단원별 리뷰 4) 읽은소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 이 책을 읽기 전에 필요한 수준/ 지식은? => 이책은 C++을 이미 충분히 숙지한 사람을 대상으로한 자료구조 기본서 이다. 기본 문법사항들은 알고있어야 한다. Q 이 책을 읽어야 할 필요성, 어디에 도움이 될까? => 자료구조의 필요성을 모르는 분들도 은근 블로그 글.. Life/Book Record 2022. 1. 22. [자료구조] 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. [자료구조] 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. [알고리즘] next_permutation : 다음 순열 next_permutation (다음 순열 구하기) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ▶ 우선 순열의 특징을 먼저 살펴봅시다! A라는 집합의 원소가 [1, 2, 3, 4] 라고 해보자. A의 순열은 다음과 같다. 1 2 3 4 (오름차순) : 첫 순열 1 2 4 3 1 3 2 4 1 3 4 2 ... 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 ... 4 3 2 1 (내림차순) :마지막 순열 오름차순으로 시작했던 순열이, 최종적으로 내림차순으로 배열되어 끝나게 된다. 총 N! 개의 서로 다른 순열이 있다. 1 2 로 시작하는 순열인 1 2 ? ? 의 마지막 순열의(내림차순) 다음 순열을 어떻게 구할까? 1 2 ? ? 의 마지막 순열은 1 2 4 .. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Two Pointers Algorithm : 투포인터 알고리즘 Two Pointers Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 투 포인터 알고리즘은 기본적으로 1차원 배열상에서 배열을 가리키는 포인터 2개를 이용하는 방법 입니다! (포인터 라고 해서 C의 그 포인터를 사용한다는 것 이 아닌, 배열의 어느 한칸을 가리키는 용도로 사용하는 것을 의미합니다) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 대표적인 문제로 백준의 2003번이 있습니다. 이 설명을 보기전 문제를 먼.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘 Sweeping Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다. 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다. 이처럼 알고리즘의 구조 자체는 간단합니다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 대표적인 문제로 백준의 선 긋기 문제가 있습니다. 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Counting inversions Counting inversions " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 예를들어 배열A에 1, 2, 3, ... n 의 수가 무작위 순서로 들어있다고 해보자. 이 수들에서 2개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는지를 구해보자. 예를 들어 A {2, 3, 6, 4, 1, 7}이 있을때, 크기가 역전된 쌍은 (2, 1), (3, 1), (6, 4), (6, 1), (4, 1) 이 있다. 따라서 Inversion 된 쌍의 수는 5개 이다. 이런 Inversion된 쌍의 수를 어떻게 구해야 할까? 직관적으로 떠오르는 직접다 for문 돌면서 확인하는 방식은 O(n^2)이 걸릴것이 눈에 훤하다... 이럴때 Merge.. Algorithm/PS 알고리즘 정리 2022. 1. 21. 이전 1 2 3 4 다음
