전체 글29 Hash Dictionary란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 우리는 이전에 hash dictionary library를 살펴본 적이 있다. 이 library는 generic한가? -Generic Libraries란 1) client가 data type을 선택할 수 있어야 하고 2) 같은 application안에서 다른 data type에 따라 multiple instances 가 가능해야 한다. Hash Dictionary를 살펴보면 // typedef ___ * entry; // typedef ___ key; 를 통해 우리는 client가 data type을 선택할 수 있음을 확인할 수 있다. 그러나 같은 application안에서 multiple instan.. 2022. 11. 13. Generic Pointers란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 우리는 이전에 stack을 만들었는데 element type을 바꾸려면 우리는 매번 기존 stack을 copy해서 새로 만들어야 한다. 이건 상당히 힘들고 귀찮은 일이다! stack은 일반적으로 generic data structures라고 할 수 있다. - element type과 상관없이 항상 같은 방식으로 operate하며 element를 변경하지 않는다. 만약 stack을 generic library로 나타낼 수 있다면 다양한 element type에 따라 매번 stack을 새로 만들지 않아도 된다. -generic library : 어떤 type의 element에도 사용될 수 있는 single.. 2022. 11. 13. Amortized Analysis를 통해 Unbounded Arrays를 알아보자 * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. Text file에 있는 모든 단어들을 array와 유사한 데이터 구조에 넣는다고 가정했을때 우리는 몇개의 단어가 그 파일에 있는지 알 수 없다. 이에 따라 우리가 생각할 수 있는 것은 unbounded array이다. Array의 element를 access하는 것은 O(1)이며 우리는 적당한 size의 array를 가져야 한다. 이러한 unbounded array를 어떻게 만들 수 있을까? 이전에 우리는 linked list 를 통해 SSA type struct를 구성할 수 있었다. struct ssa_header{ int length; string[] data; } element를 추가해가며 un.. 2022. 11. 4. Amortized Analysis - Amortized cost란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 오늘은 Amortized Cost를 구하는 Amortized Analysis를 알아보도록 하겠다. 가상의 예를 들어보겠다. 우리가 스타트업 가게를 차렸다고 가정하자. 새로운 고객이 서비스를 사용할때마다 counter가 올라가고(binary counter) 그에 따라 $1불씩 전기회사에 비용을 지불한다. 이때 이 지출비용을 커버하기 위해 각 고객별로 얼마를 받아야할까? 첫 8명의 고객을 받았을때 지출이 얼마나 되는지 살펴보자 이때 cost는 flip하게 되는 bit의 개수를 의미한다. counter User # Cost 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 2 2 0 0.. 2022. 11. 1. 이전 1 2 3 4 5 6 7 8 다음
