자료구조8 Function Pointer란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 우리는 앞서 C0 memory model에서 두가지의 memory를 살펴보았다. -Local memories 와 allocated memories 하지만 실제 컴퓨터에는 하나의 memory만 존재한다. 따라서 local 과 allocated memory는 이 큰 하나의 memory에 두가지 segments일 뿐이다. Allocated memory가 있는 segment를 우리는 heap이라고 부른다. local memory가 있는 segment를 우리는 stack이라고 부른다. -function call에 따라 이 stack은 커지기도, 작아지기도 한다. stack은 점점 커지고 heap이 점점 커져서 .. 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 - 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. Linked Lists란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 학과 수업시간에 배운 내용을 그때그때 정리하고자 한다. 시험에도 도움이 되고 나중에 이후 무언가를 준비할때도 도움이 될듯하다 (절대 시험을 너무 망쳐서 강제로 복습하는게 아니다) Linked Lists Linked list 의 가장 큰 특징은 pointer를 통해서 다음 요소를 access할 수 있다는 것이며 각 element 를 node라고 부른다. 위 그림에서 파란색 상자 하나가 node인것이다. 위 구조에서 보듯이 next가 또다른 같은 구조의 node를 가리키고 있기 때문에 recursive하다는 특징을 가지고 있다. 코드로 구현하면 아래와 같다. typedef struct linked_node.. 2022. 10. 22. 이전 1 2 다음
