일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 이종호
- 호키도키
- queue
- data structure
- IOS
- 계명대
- SWIFT
- react
- 리액트 예제
- TDD
- javascript
- 자바스크립트 자료구조
- 자바스크립트
- 리액트
- 스위프트
- HTML
- hokidoki
- 스벨트
- hokeys
- 호키스
- 개발
- 자료구조
- 개발자
- Svelte
- 자스민
- 계명대 이종호
- 비동기
- jest
- 힛잇
- Hitit
- Today
- Total
목록자료구조 (19)
Dog foot print
지난번 해시테이블 포스팅도 그렇고 이번 트리도 그렇고 꽤나 양이 방대해서 그런지 시리즈로 포스팅을 하고 있다. 나도 몰랐고 처음 해보는 자료구조들이라서 그런지 예제도 이해하는데 오래 걸리고 이를 토대로 다시 정리하는 것도 생각보다 오래 걸린다. ㅜ.ㅜ 으쌰 으쌰해야겠다. tree의 표현 방법 트리를 만드는 방법은 배열 혹은 연결리스트로 만드는 방법이 있다. 배열로 표현하는 방법은 다음과 같다. 임의의 노드 A의 부모노드 인덱스 . : 해당 노드의 인덱스 i / 2; 임의의 노드 A의 왼쪽 자식노드 인덱스. : 해당 노드의 인덱스 i * 2; 임의의 노드 A의 오른쪽 자식노드 인덱스. : 해당 노드의 인덱스 ( i * 2 ) +1 배열로 트리를 만들게 되면 배열의 0번째 방은 사용하지 않는다. 그리고 배열..
포스팅 전 주저리 : 알바하고 있는 곳에 전임자가 매니저로 왔다... 가뜩이나 사람들 자꾸 나가서 짜증난데 내가 정말 싫어하는 부류인 예의도 싸가지도 없는 놈이 매니저로 오다니 ㅜ.ㅜ 빨리 그만두라는 신의 계시인 것인가 ... ? 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로 쓰게 숫자형태로 변환한다고 생각하면 된다. 그런데 여기에는 큰 문제가 있다...
자바스크립트 이외에 언어에서 연결리스트가 가지는 이점은 배열처럼 고정된 크기를 가지는게 아니라 동적으로 크기를 조정 할 수 있는 것이 장점이다. 그렇다면 단순연결리스트와 원형연결리스트 보다 이중연결리스트가 가지는 이점은 무엇일까 ? 이중연결리스트란 ? 기존에 만들었던 연결리스트들은 모두 한 방향으로 이루어져 있다. 그런데 이중연결리스트는 L link 와 R link를 가지고 있어 해당 노드에서 전, 후 노드에 접근 하는 것이 가능케 된다. 이로인해서 헤드가 마지막에 연결되어있는 노드를 O(1) 의 복잡도를 가지고 찾을 수 있다. 멤버변수 class nodeType{ constructor(item){ this.data = item; this.lLink = null; this.rLink = null; } 이..
지난번 만들어 보았던 단순연결리스트는 마지막 node 가 null을 가리키고 있는 형태를 하고 있는데 오늘 만들어볼 원형 연결리스트는 마지막 노드가 항상 Head 노드를 가리키고 있어 노드의 링크를 타고 다시 처음으로 갈 수 있다는 이점이 있다. // 아직 원형연결리스트가 단순연결리스트보다 더 좋은 이점을 찾지를 못 찾겠다. 루프를 만들어 내부에 뭐가 있는지 순차적으로 감시하기에는 좋을 듯 하다. 원형연결리스트 필요한 멤버 변수 처음 만들어지는 head는 data로 head가 들어간다. constructor(item){ this.data = item; this.link = null; } 필요한 메서드 insertFirstNode(item) // node를 생성하고 head바로 앞에 넣는다. insertL..
javascript의 배열은 array-list라는 것의 형태를 띄고 있어 배열의 크기 존재하지 않는다. 그런데 c 같은 언어들은 배열의 크기가 존재하기에 한 배열을 유한하게 밖에 사용 할 수 없다. 그래서 개발자들은 노드리스트라는 개념을 만들어 각각의 구조체들로 서로를 연결하는 것을 만들었다. 연결리스트에는 단순 연결리스트, 이중연결리스트, 원형연결리스트가 있으며 이 연결리스트들을 이용하여 스택, 큐, 트리등 다양한 자료구조를 만들 수 있다. node 란 node란 data필드와 link필드를 가지고 있는 일종의 구조체로 link를 통해서는 다음 연결된 노드에 접근 할 수 있다. simple linked-list는 처음 노드를 header라고 하며 마지막 노드의 link는 항상 null이다. 연결리스트..
이전까지 stack, sicle queue, queue 를 만들었지만 전부 다 단방향에서 아이템을 꺼내와야 하는 불편함이 있었다. 그러나 원형 큐의 아종인 덱이라는 녀석은 앞과 뒤 모든 방향에서 데이터를 추가 및 삭제 할 수 있는데 오늘은 이 녀석을 만들어 볼 예정이다. 덱 Deck 덱은 원형 큐와 마찬가지로 배열에 빈 공간이 있다면 데이터를 추가 할 수 있는 구조를 하고 있어 원형 큐와 마찬가지로 덱 또한 원형 구조를 하고 있다. 덱의 멤버변수 constructor(size){ this.maxQueueSize = size; this.array = []; this.front = 0; this.rear = 0; } 원형 큐와 동일한 front , rear를 가지고 있다. 덱의 메서드 __주의__ addRe..