Dog foot print

시험 기간때문에 개인 프로젝트나, 포스팅이 전부 올 스탑이다. 적어도 이번 학기는 이런 상태가 지속 될 것 같아 걱정이다. 교수님이 주신 두번 째 과제는 max_heap_tree를 만들어 삭제와 삽입을 가능케 하는 것이다. 물론 배열이 아닌 연결리스트로 구현하라고 했기에 약간의 어려움이 존재하였다. max_heap_tree 는 가장 최대값을 우선순위로 하여, 삽입시 O(logn) , 삭제시 O(logn)의 시간 복잡도를 가지게 되는 자료구조입니다. max_heap_tree의 자세한 내용은 다음 링크 를 따라가셔서 확인하시도록 하세요. 데이터 구조체 heapType 제 heap_tree는 nodeType을 가지고 있는 rootNode 필드가 있고, 삽입시 마지막 레벨 - 1 중 아직 다 채워지지 않은 노드..

이번 주 목요일부터 자료구조(2)수업이 실습수업을 겸하면서 오랜만에 만져보는 C언어와 자주 쓰지 않는 비쥬얼스튜디오를 익혀야 할 필요가 생겼다. 교수님은 다음과 같은 텍스트파일의 숫자를 트리에 삽입 및 노드에 있는 모든 값들을 더해서 출력하기를 원하셨다. 다만 문제가 있었다. 트리라고는 말씀하셨는데, 완전이진트리인지, 힙 트리인지 , 이진탐색트리인지를 제대로 못 들은 것이다. 그래서 그냥 완전 이진트리를 사용해서 데이터를 삽입할 계획을 세웠다. 그런데 , 문제는 완전이진트리의 삽입이 다른 트리와 다르게 노드간 데이터를 비교하면서 맞는 위치에 삽입되는 형태가 아니라 노드가 삽입될때 부모노드의 왼쪽자식노드 , 오른쪽 자식노드를 채우고 , 마지막 레벨의 노드를 제외하고 모두 자식노드를 두개씩 가지고 있어야 한..

heap 이란 ? heap 은 우선순위 큐를 위해서 만들어진 트리자료구조이다. heap은 부모노드와 자식노드의 대소관계에 따라 최대힙(Max heap)과 최소힙(Min heap)으로 나뉜다. heap의 특징 heap은 완전이진트리의 형태이다. 완전이진트리 설명보러가기 heap은 트리내에서 중복된 값을 허용한다. heap은 느슨한 정렬(반 정렬) 상태를 가진다. 반 정렬 이라는 의미는 자식노드가 부모의 노드보다 무조건 크거나 작다. 그러나 전체트리를 볼 때는 가장 아래에 있는 노드가 가장 작거나 큰 값은 아니라는 의미이다. Max heap 최대 힙 최대힙은 다음과 조건을 항상 만족한다. 자식노드 value >= 부모노드 value Min heap 최소 힙 최소힙은 다음과 같 은 조건을 항상 만족한다. 자식..

해당 포스팅은 큐와 트리를 이해했다는 가정하에 작성되고 있습니다. 큐와 트리에 이해도가 없는 분들은 본 포스팅을 보기 전 큐와 트리에 대한 포스팅을 먼저 읽어주시기 바랍니다. 우선순위 큐란 ? 우선순위 큐는 일반적인 큐와 거의 동일하다. 큐는 해당자료구조에 들어온 순서대로 배출이 된다. 다만 우선순위 큐는 우선순위큐는 먼저나가는 순서를 들어온 순서 뿐만 아니라 다른 조건에 의하여 들어온 데이터에 우선순위를 부여해 순위에 맞게 배출한다. 어찌보면 일반적인 큐도 우선순위큐가 될 수 있는데 배출되는 순서를 해당 큐에 들어온 순서에 의거하여 우선순위를 부여하여 배출하기 때문이다. 우선순위 큐의 사용 예 우선순위 큐는 우리의 일상에서도 친근하게 사용되고 있다. 유니버셜 스튜디오랜드같은 해외 외국 놀이공원에서는 일..

포스팅 전 주저리 : 자스민도 슬슬 확장해보려는 마음이 생겨 에브리타임에 다시 가입했다. 그런데 수강신청기간이라 그런지 게시판은 수강신청에 대해서 활발하게 대화 중이였는데, 속이려는 놈, 동요하는 놈, 이상한 놈이 섞여서 혼돈의 도가니였다. 그중 가장 웃긴놈은 학교 근처에서 접속하면 3분 먼저 접속이 가능하다. 조금 더 접속이 잘된다. 이런 말 하는 놈이였는데 결국 못 참고 ppt로 헛 소문들 정리해줬다. tree에 삽입 2부에서 설명 했듯이 배열로 이진트리를 만들면 왼쪽 자식노드의 인덱스 번호는 부모노드의 인덱스 * 2 이며, 오른쪽 자식노드는 부모의 (인덱스 * 2) +1 의 인덱스 번호를 가진다. 그렇기에 이진탐색트리에 새롭게 삽입될 인덱스 번호를 삽입하는 일은 현재 노드의 데이터를 삽입하려는 데이..

포스팅 전 주저리 : 알바하고 있는 곳에 전임자가 매니저로 왔다... 가뜩이나 사람들 자꾸 나가서 짜증난데 내가 정말 싫어하는 부류인 예의도 싸가지도 없는 놈이 매니저로 오다니 ㅜ.ㅜ 빨리 그만두라는 신의 계시인 것인가 ... ? Tree 란 ? Tree란 조직도같이 하나의 루트(하나 밖에 없는 차상위)에서 하층구조들과 연결된 계층적 자료구조를 말한다. 대표적으로 인공지능 문제에서도 트리가 사용된다고 한다. Tree를 이루고 있는 것들 Node : 데이터를 담는 공간이다. Root Node : 최상위 노드로 부모없이 가장 높은 곳에 있는 노드를 말한다. Edge : 부모와 자식노드를 연결해주는 선 Childe Node : 부모가 있는 노드로 위에 3의 데이터를 가지고 있는 노드입장에서 1을 가진 노드와 ..

hash table에 대한 포스팅을 조금 더 찾아봤는데 충돌이 일어날 경우 open adress 방식이나, seperate Chaining 방식으로 해당 충돌을 우회 해야한다고 다들 적어놓았지만 충돌이 일어나 다른 곳에 저장한 후 해당 key로 어떻게 data를 찾는지는 나오지 않았다. 그래서 해시테이블을 직접 만들어 보면 어떨까 싶어 해시테이블 2부를 만들게 되었다. 원시적인 해시테이블 function HashTable(){ let array = []; let size = 20; return { hashFunc(key){ let hashValue = key.length % size; return hashValue; }, add(key,item){ if(array[this.hashFunc(key)] !=..

포스팅 전 주저리 : 오늘 너무 포식한 것 같다. 자스민 사람들 중 생일 맞은 분이 치킨 한 턱 쏘시고 다른 분이 아이스크림케잌까지 먹었다... 다이어트는 물건너 간 느낌이다. ㅋㅋㅋㅋ . HashTable 이란 ? 해쉬테이블은 value가 key와 매핑되어 O(1)의 시간 복잡도를 가지고 value를 서치할 수 있는 자료구조이다. Hash Function 이란 ? HashTable은 key를 이용해서 value를 서치한다. 그런데 이 key는 string 타입으로 되어있기 때문에 배열에서 해당 키를 사용하려면 number형태로 만들어 index 처럼 사용해야 한다. 쉽게 생각해서 해당 key(string)가 배열에 index로 쓰게 숫자형태로 변환한다고 생각하면 된다. 그런데 여기에는 큰 문제가 있다...