Dog foot print

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

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

지난번 해시테이블 포스팅도 그렇고 이번 트리도 그렇고 꽤나 양이 방대해서 그런지 시리즈로 포스팅을 하고 있다. 나도 몰랐고 처음 해보는 자료구조들이라서 그런지 예제도 이해하는데 오래 걸리고 이를 토대로 다시 정리하는 것도 생각보다 오래 걸린다. ㅜ.ㅜ 으쌰 으쌰해야겠다. tree의 표현 방법 트리를 만드는 방법은 배열 혹은 연결리스트로 만드는 방법이 있다. 배열로 표현하는 방법은 다음과 같다. 임의의 노드 A의 부모노드 인덱스 . : 해당 노드의 인덱스 i / 2; 임의의 노드 A의 왼쪽 자식노드 인덱스. : 해당 노드의 인덱스 i * 2; 임의의 노드 A의 오른쪽 자식노드 인덱스. : 해당 노드의 인덱스 ( i * 2 ) +1 배열로 트리를 만들게 되면 배열의 0번째 방은 사용하지 않는다. 그리고 배열..

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

어제 선형탐사 방식을 통하여 해시값 충돌시 해시값을 유효범위까지 늘려 충돌을 우회했다. 그러나 open adress방식을 사용하면 유효범위가 유한하기 때문에 언젠가 충돌이 일어날 수 있었다. 그렇기에 이번에는 chaining 방식을 통해 조금 더 유연한 hash table을 만들어 보겠다. Seperate Chaining Seperate chaining 은 배열에 연결리스트를 넣어서 유한하던 저장공간문제를 해결하는 방식이다. 다만 메모리문제와 탐색시 최악의 시간 복잡도가 O(n)이 된다는 단점도 가지고 있다. Double Linked List function Dictionary(key,value){ return { llink : null, key : key, value : value, rlink : nu..

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로 쓰게 숫자형태로 변환한다고 생각하면 된다. 그런데 여기에는 큰 문제가 있다...

포스팅 전 주저리 : 여자친구가 어제 아이패드 프로 1세대 중고를 구입했다. 구성도 알차게 있었는데, 내가 사용하는 6세대보다 훨씬 좋아보인다 ㅜ.ㅜ 나도 열심히 공부하고 돈 벌어서 모든 애플제품을 프로로 구입하는 프로앱등이가 될거다. ! 빠샤 삽입정렬이란 ? 배열의 1번째 index부터 배열을 순회하며 자신보다 높은 데이터 앞에 해당 key의 데이터를 넣는 정렬 알고리즘이다. 시간 복잡도는 O(n2) 이며 안정 정렬 알고리즘이다. 삽입정렬이 일어날 때 내부 1. 빨간글씨 key의 아이템이 전과 key 의 전 아이템과 비교한다. 2. key의 아이템이 작다면 왼쪽 방의 아이템들과 비교해서 작을때까지 배열을 이동하여 key의 아이템을 삽입한다. 1번째 인덱스 value = 2; [6,2,4,7,5,2] /..