익명의 개발노트

1. 해시테이블이란? 1) 효율적인 탐색을 위한 자료구조로서 키-값으로 저장을 한다. 2) 키를 해싱하여 해시테이블의 인덱스를 구한 후에 저장을 함. ※ 해시테이블은 개발자의 기본이라고 불리울 만큼 중요하며, 자유자재로 다룰 줄 알아야 한다. 3) 핵심은 해시함수를 거친 후 해시테이블에 저장되는 방식이다. 2. 충돌시 회피방법 3가지. 1) Chaining : 저장을 Linked List 방식으로 저장하는 방법이다. 2) Linear probing : 비어있는 인덱스에 저장하는 방식이며, if 5번 인덱스랑 겹치는데 6번 인덱스가 비어있으면 6번 인덱스에 저장, 6번도 이미 차있으면 7번에 저장하는 방식. 3) Table resize : 테이블을 기존의 2배로 늘리고 조정하는 방식. 1. 간단한 해시테이..

doubly linked list는 양방향 링크드 리스트라고 불리운다. 양방향이기 때문에 단방향 리스트하고 비교시 이전값을 가리키는 포인터가 들어있다. 1. Linked List와 차이점 1) 시작과 끝 부분이 거꾸로도 가능하다는 의미이다. 2) 원하는 element의 이전값이나 다음값으로도 갈 수 가 있다. 3) 단방향에서는 원하는 element를 놓쳤을 경우 처음부터 돌아가서 탐색해야하는데, 양방향은 그럴 필요없다. 2.functional instantiation function DoublyLinkedList(){ let Node = function(item){ this.element = item; this.next = null; this.prev = null; //추가됨. }; let length ..

1. Graph란? 1) 모든 노드를 각각 노드와 연결하는 선(E, edge)을 하나로 모아 놓은 자료 구조 2. 종류 1) 방향 그래프(directed) 2) 무방향 그래프(undirected) 3) 가중치 그래프(weighted or Network) 3. 특징 1) 그래프에는 방향이 있을 수도, 없을 수도 있다. 2) 그래프에는 사이클이 존재 할수도, 존재 하지 않을 수도 있다. 3) 그래프는 네트워크 모델이다. 4) 2개 이상의 경로가 가능하다. 5) Root Node의 개념이 없다. 6) 부모-자식 개념이 없다. 7) self loop 뿐만 아니라 loop or circuit 모두 가능하다. 8) 순회는 DFS 또는 BFS로 이루어진다. 9) 그래프는 순환(Cyclic) 혹은 비순환(Acyclic..

Binary -heap 구조는 트리구조에서 최대값과 최소값을 빠르게 찾기 위한 완전 이진트리(complete binary tree) 기본으로 한 자료구조임. 1. 종류 1) Min Heap : Root Node에 가장 작은 값이 오도록 하는 것. 부모노드는 자식노드보다 작은 값을 가지는 트리구조. 2) Max Heap : Root Node에 가장 큰 값이 오도록 하는 것. 모든 부모노드는 자기 자식노드보다 큰 값을 가지는 트리구조. ※ 근본적으로 두개는 갖고 숫자만 반대로 하면 된다. 아래 설명은 최소힙만 보도록 하겠다. 2. 특징 1) 삽입(insert) (1) 완전 이진트리의 구성을 잃지 않도록 마지막 Child Node의 왼쪽부터 채워나감. ※ 왼쪽 채워져있으면 오른쪽에 채우면 됨 (2) 삽입된 원..

트리구조로 데이터에 접근하는 방법(Tree traversals)으로 3가지 방법이 있다. 1. In-order traversal 2. Pre-order traversal 3. Post-order traversal 1. In-order traversal 1) Root Node를 시작으로 왼쪽노드, 호출한 노드, 오른쪽 노드순서로 탐색을 한다. 2) Left Node →Root Node →Right Node 순으로 출력한다. 3) 위그림으로 출력해보면 출력순서는 : 4 → 2 → 5 → 1 → 3 2. Pre-order traversal 1) Root Node를 pre(=before) 에 출력, 자기 자신이 먼저 출력한다. 2) Root Node → Left Node → Right Node 순으로 출력한다...

트리구조는 위 그림과 같은 형태의 데이터 구조를 말한다. 1. 특징 1) 1개의 Root Node갖는다. 2) Root Node는 0개 이상의 Child Node를 갖는다. 3) Child Node 또한 0개 이상의 Child Node를 갖고 있고, 이는 반복적으로 정의된다. 4) 트리에는 Cycle이 존재할 수 없다. 5) 각 Node는 어떤 자료형으로도 표현 가능하며, 부모 Node로의 연결이 있을 수도 없을 수도 있다. 2. 종류 1) 이진트리(Binary tree), 이진검색트리(Binary search tree), 완전이진트리(Complete binary tree), 전 이진트리(Full binary tree), 포화이진트리(perfect binary tree) 로 구분된다. 2) 트리는 균형(..

큐는 흔히들 이야기하는 선착순, 카페 줄서기, 은행줄서기를 생각하면 이해하기 쉽다. 먼저 들어온 값이 먼저 나가는 것으로 , FIFO(First in First Out)으로 볼 수 있다. 큐는 프로세스 스케줄링, 네트워크 패킷처리, 프린트 대기열, 대부분의 입출력 등에서 사용된다. 큐에서 흔히 사용되는 ADT(Abstract Data Type)는 Enqueue(삽입), Dequeue(값 빼기), Size(크기확인), Empty(비었는지 확인), peek (맨 앞값 확인) 가 있다. Psuedo 코드 QueueArr[10] 생성 tail =0 생성(꼬리) head =0(맨앞) 생성 Enqueue(data) 함수 생성 tail이 큐배열의 길이보다 크면 "큐 오버플로우" 메시지 출력 그 반대면 배열에 data..

메모리 안의 데이터를 효율적으로 처리하기 위한 자료구조 FILO(First in Last Out), LIFO(Last in First Out) 의 의미. 구현방법은 두가지가 있다. 1. 정적인 1차원 배열 : 구현하기 쉬우며, 사이즈를 미리 알아야한다. 2. Dynamic Array : 리스트이며, 사이즈를 몰라도 되지만, 구현하는데 어렵다. 위 그림이 대표적인 스택의 모습이다. 또한 우리가 살아오면서 스택을 몸소 실천하면서 살아왔다. 맨 아래부터 차곡차곡 엎드리고 사람을 쌓으면, 위에있는 사람먼저 내려와야 안전하다. 더이상 설명은 안해도 이해할 것으로 믿는다. ADT(추상 데이터 타입)은 push, pop, peek, isEmpty가 있다. Pseudo 코드 stack arr[10] 생성 Top = 0..

Linked List는 노드값에 데이터와 헤더값을 기본으로 데이터를 찾아가는 방식임. 데이터(실제 데이터 공간), 헤더(주소 데이터공간)을 의미. 헤더에는 내 앞에 있는 노드의 주소를 저장한다. EX) 선생님이 철수에게 "이 화분 누가 깨뜨렸어?" 라고 묻자. 철수는 영희를 가리키며, "영희가 그랬어요." 영희는 "빡구가 그랬어요" 라며 손가락으로 가리킨다. 이때 손가락 부분이 헤더라고 보면 이해하기 쉽다. 장점으로는 삽입, 삭제가 많은 데이터 리스트에 사용한다. 특징은 데이터 중간에 삽입, 삭제 가능하며, 동적어레이로 크기 조절이 자유롭다. 따라서 메모리 공간을 절약할 수 있음. 하지만, 계속 단서를 찾아가기 때문에 접근 속도가 느리다. 새 Node[DATA, HEAD] 생성 LinkedList 만들기..

컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리 , 저장을 의미하며, 데이터 값의 모임. 데이터간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미함. 자료구조에는 여러종류가 있으며, 직접 구현해 보는 것이 가장 중요함. 각 자료구조의 본질과 컨셉을 이해하는 것이 중요하다. 자료구조의 기본적인 구성 1. insert : 데이터를 어떻게 저장할 것인가? 2. Search : 데이터를 어떻게 탐색할 것인가? 3. Delete : 데이터를 어떻게 삭제할 것인가? 일반적으로 자료구조는 단순구조, 파일구조, 선형, 비선형구조로 나뉘며, 선형구조(Linear)와 비선형구조(Non-Linear)를 말한다. 선형구조 : Stack, Que, Linked List, Arrays, Deque ..