자료구조48 [백준][C++] 16719번: ZOAC <186> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 와 이번문제 나는 어려웠다. 단순하게 A부터 찾아서 추가하는 식으로 해결하기도 어렵다. 왜냐하면 문자는 중복이 가능하기 때문이다. A가 2개 이상이라면 어디부터 시작해야 할까? 이또한 문제이다... 따라서 나는 다음과 같은 알고리즘으로 문제를 해결해 나갔다. (다른분의 풀이를.. Algorithm/백준 2022. 2. 14. [자료구조] 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. [서평] 쉽게 배우는 알고리즘 저의 돈으로 직접사서 직접 완독해본후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할것이며, 단점은 단점대로 언급할 것 입니다. 쉽게 배우는 알고리즘 저자 : 문병로 출판 : 한빛아카데미 발매 : 2018.01.20 2021/03/25 ~ 2021/05/12 1) 책의 표지 2) 단원별 구성 3) 읽은소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 이 책을 읽기 전에 필요한 수준/ 지식은? => 이책은 알고리즘을 깊게 설명해주는 책 이다. 기본적인 자료구조에 대한 충분한 이해가 필요하다. 더 나아가 이미 알고리즘을 어느정도 접해본 분이라면 더욱 배워갈점이 많은 책 이다. Q 이 책을 읽어야 할 필요성, 어디에 도움이 될까? => 단순 코딩테스.. Life/Book Record 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. 이전 1 2 3 4 다음
