자료 구조 & 시간 복잡도

본 프로젝트는 다음을 다운 받아서 진행해주세요: https://drive.google.com/drive/folders/1cJ6I4YGufbOui4_oGdvWvs8hdtjKNt64?usp=drive_link

1. Queue

Queue는 놀이동산에서 기구를 타려고 줄서는 모습과 같습니다. 먼저 들어온 사람이 먼저 나가게 됩니다. (FIFO: first in, first out)

queue는 샌드위치 만드는 로봇에게 순서를 명령할 때 사용할 수 있습니다.

---

2. Stack

stack은 차곡 차곡 위로 쌓은 접시와 같습니다. 나중에 들어온 접시가 먼저 나가게 되죠. (LIFO: last in, first out)

stack은 브라우저에 뒤로가기를 누르는 효과에 사용됩니다.

---

Part One

Bare Minimum Requirements

stack과 queue의 자료구조를 다음 4가지 instatiation 스타일로 작성을 하세요. 시작하기 쉽게 함수형을 작성할 src/functional/queue.js and src/functional/stack.js에는 뼈대가 완성되어 있습니다. 거기서 부터 시작을 하세요.

• No arrays! Instead, use an object with numeric keys
• Pass all the tests (open SpecRunner.html in a browser to see which tests are passing)

---

---

Data Structure Specs

• Implement a stack with the following methods:
  • push(string) - Add a string to the top of the stack
  • pop() - Remove and return the string on the top of the stack
  • size() - Return the number of items on the stack
• Implement a queue with the following methods:
  • enqueue(string) - Add a string to the back of the queue
  • dequeue() - Remove and return the string at the front of the queue
  • size() - Return the number of items in the queue

---

Instantiation Styles

1. Functional instantiation: a simple "maker" pattern

• Do:
  • Work within the src/functional/ folder
  • Define all functions and properties within the maker function
• Don't:
  • Use the keyword new, the keyword this, or any prototypechains
  • Capitalize the maker function name
• Example: The provided classes Stack and Queue already follow this pattern

2. Functional instantiation with shared methods: same as step 1, but with shared methods

• Do:
  • Work within the src/functional-shared/ folder
  • Create an object that holds the methods that will be shared by all instances of * the class
  • Use the keyword this in your methods
  • Use _.extend to copy the methods onto the instance
• Don't:
  • Use the keyword new or prototype chains
• Example: functional instantiation example

3. Prototypal instantiation: using Object.create

• Do:
  • Work within the src/protoypal/ folder.
  • Use Object.create with the object from step 2 to create instances of your class
• Don't:
  • Use the keyword new
• Example: prototypal instantiation example
  • Pseudoclassical instantiation: create instances with the keyword new
• Do:
  • Work within the src/pseudoclassical/ folder
  • Capitalize your function name to indicate to others that it is intended to be run with the keyword new
  • Use the keyword new when instantiating your class
  • Use the keyword this in your constructor
• Don't:
  • Declare the instance explicitly
  • Return the instance explicitly
• Example: pseudoclassical instantiation example
  • Sprint Two: Data Structures

Part TWO

본 repo는 주로 Mocha test 툴을 사용합니다. SpecRunner.html에 보시면서 Spec폴더에 있는 파일들의 테스트가 어떻게 작성되고 결과로 나오는지 확인할 수 있습니다. 본 과정에서는 몇군데의 경우 Spec을 비어놓아 test가 되지 않게 한 부분을 만들어놨습니다. 찾아서 spec을 완성시켜주세요.

---

Bare Minimum Requirements

---

3. Linked List

Linked List는 dynamic data structure로 O(1)의 시간복잡도를 가진 넣기와 지우기 기능이 있습니다 (Array의 경우 O(n) 인것을 감안하면 빠르다는 것을 느낄 수 있을 것입니다). 대신, linked list는 index가 되어있지 않기 때문에, 처음부터 끝까지 검색해야 하는 경우 O(n)이 걸리게 됩니다.

Linked List는 여러장의 form으로 되어있고 한장이 끝나야 다음장이 진행되는 설문조사를 만들 때, 사용될 수 있습니다.

• A linkedList class, in functional style, with the following properties:
  • head property, a linkedListNode instance
  • tail property, a linkedListNode instance
  • addToTail() method, takes a value and adds it to the end of the list
  • removeHead() method, removes the first node from the list and returns its value
  • contains() method, returns boolean reflecting whether or not the passed-in value is in the linked list
  • What is the time complexity of the above functions?

---

4. Tree

Tree는 계층적 자료구조이며 node와 (만들 시) children으로 구성이 되어 있습니다. Children은 또 그 자체로 하나의 노드가 되어 children을 밑으로 만들 수 있게 됩니다. 자식이 자식을, 또 그 자식이 자식을... recursive한 구조 때문에 tree를 재귀형 자료구조라고도 합니다. A tree is a hierarchical data structure consisting of a node (potentially) with children. The children are trees unto themselves, that is, nodes with (potential) children. For this reason the tree is referred to as a recursive data structure.

Tree는 족보를 상상해볼 수 있습니다.

• A tree class, in functional with shared methods style, with the following properties:
  • children property, an array containing a number of subtrees
  • addChild() method, takes any value, sets that as the target of a node, and adds that node as a child of the tree
  • A .contains() method, takes any input and returns a boolean reflecting whether it can be found as the value of the target node or any descendant node
  • What is the time complexity of the above functions?

---

5. Graph

Graph는 node(verticies(꼭지점)이라고도 부름)들과 edge(arc(호)라고 부름)들이 연결된 모습으로 구성되어 있습니다. Tree와는 달리 계층적 구조가 아닙니다. Graph는 방향이 없을 수도 있습니다. 이 말은, 두 node사이의 관계가 대칭적일 수 있습니다. 그리고 방향을 가질 수도 있는데, 이 때는 edge로 연결되어 비대칭적인 관계를 가졌다는 것을 뜻합니다. 여러분은 undirected graph를 작성하게 될 것입니다.

Graph는 website 모음 또는 우리 모두가 사용하는 www(world wide web)을 상상할 수 있습니다.

• Implement a graph class, in pseudoclassical style, with the following properties: *It is an undirected graph. It does not have to be 'connected'.
  • An .addNode() method that takes a new node and adds it to the graph
  • A .contains() method that takes any node and returns a boolean reflecting whether it can be found in the graph
  • A .removeNode() method that takes any node and removes it from the graph, if present. All edges connected to that Node are removed as well.
  • An .addEdge() method that creates a edge (connection) between two nodes if they both are present within the graph
  • A .hasEdge() method that returns a boolean reflecting whether or not two nodes are connected
  • A .removeEdge() method that removes the connection between two nodes
  • A .forEachNode() method that traverses through the graph, calling a passed in function once on each node
  • What is the time complexity of the above functions?

---

6. Set

Set은 유일한 값을 특정한 순서 없이 가지고 있습니다.

Set은 복권당첨을 할 때 사용될 수 있습니다.

• A set class, in prototypal style, with the following properties:
  • An .add() method, takes any string and adds it to the set
  • A .contains() method, takes any string and returns a boolean reflecting whether it can be found in the set
  • A .remove() method, takes any string and removes it from the set, if present
  • What is the time complexity of the above functions?
  • Note: Sets should not use up any more space than necessary. Once a value is added to a set, adding it a second time should not increase the size of the set.
  • Note: Until the advanced section, your sets should handle only string values.
  • Note: This is a rather simple data structure. Take a look at the Wikipedia entry. Which native Javascript type fits the requirements best?

---

7. Hash Table

Hash Table(또는 Hash Maps)는 key와 value의 구조로 이루어져있습니다. 메모리에 최적화하기 위해 Hash Function을 사용하여 key를 메모리에 위치에 해당하는 값으로 바꾸는 방식을 사용합니다. Hash Table은 필요시 메모리를 늘리고, 가능하면 언제나 메모리를 최적화하려고 합니다.

Hash Table은 이메일의 구조를 상상해볼 수 있습니다.

• A hashTable class, in pseudoclassical style:

  • First: Play with each of the helper functions provided to get a sense of what they do.
  • You will use the provided hash function to convert any key into an array index. Try interacting with it from the console first.
  • A limitedArray helper has been provided for you, check out the source code for it in src/hashTableHelpers.js. Use it to store all inserted values rather than using a plain JavaScript array. The limitedArray, as you will see in the source code, provides get, set, and each methods which you should use in order to interact with it. Do not use the typical bracket notation for arrays when interacting with a limitedArray instance. Try interacting with it from the console first.
  • Make the following properties appear on all instances:
  • An .insert() method
  • A .retrieve() method
  • A .remove() method
  • What is the time complexity of the above functions?

• Using your understanding of hash tables, refactor your set implementation from above to run in constant time

• On Objects and Hash Tables: An astute hacker might find themself wondering "Is it not so that a JavaScript object is a hash table?" or even further, "Why would I ever need to create a hash table in JavaScript?" While it is true that objects and hash tables are functionally similar, knowing how a hash table works is hugely important as they are an incredibly useful and fundamental data structure. To have detailed knowledge of how a hash table is constructed will give you valuable insight on your path to code mastery. Additionally, other languages might not provide the convenience of JavaScript's object class, meaning you may someday have to put your hash table construction abilities to good use.

참고로 JavaScript object는 hash table 설명과 비슷한 효과를 가지고 있지만 hash table로 이루어지지 않았습니다. Chrome에 사용하는 JavaScript V8 엔진의 경우, hash table보다 훨씬 빠른 성능을 가지고 있습니다.

---

8. Binary Search Tree

Binary Tree는 children이 없거나 최대 2까지 있을 수 있습니다. Tree는 재귀형 자료구조라는 사실에 children이 최대 2이라는 제약이 있는 것을 생각할 수 있습니다. Binary Search Tree에서 children이 2일 때 하나의 child는 언제나 node보다 작고, 다른 하나는 node보다 큽니다. Children을 왼쪽 오른쪽으로 나눈다고 가정 했을 때, 어떤 것이 크고 작을지는 상관없지만 일정한 규칙으로 진행되어야 합니다.

Binary Search Tree는 영어사전 등에 사용됩니다.

• Implement a binarySearchTree class with the following properties:
  • A .left property, a binary search tree (BST) where all values are lower than than it the current value.
  • A .right property, a BST where all values are higher than than it the current value.
  • A .insert() method, which accepts a value and places in the tree in the correct position.
  • A .contains() method, which accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
  • A .depthFirstLog() method, which accepts a callback and executes it on every value contained in the tree.
  • What is the time complexity of the above functions?
  • Use case: Given a list of a million numbers, write a function that takes a new number and returns the closest number in the list using your BST. Profile this against the same operation using an array.