처음부터 차근차근

Graph 관련 문제를 해결하기 위해 모델링할 경우에는, 두 가지 방법이 존재합니다. 인접 행렬 인접 리스트 인접 행렬 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다. 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다. 간단히 요약하자면 다음과 같다. adj[i][j] = 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0 다음 그래프를 한번 살펴보자 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다. 0 - 1 이 연결되어있기 때문에..

Graph란?? 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. -wikipedia 그래프는 트리와 비슷하게 정점과 간선으로 구성되어 있다. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 그래프는 노다 간에 여러 개의 간선이 존재할 수 있다. 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프( = 양방향 그래프)로 나눌 수 있다. Vertex & Edge Vertex(정점) 노드라고 불리며, 그래프를 형성하는 기본 단위이다. 정점은 분할할 수 없는 객체이자 "점"으로 표현되는 위치, 사람, 물건 등이 될 수 있다. Edge(간선) ..

Heap Heap tree or Heap이라고 불린다. 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진트리를 말한다. 우선순위 Queue를 위하여 만들어진 자료구조이다. 힙은 일종의 반 정렬 상태(느슨한 정렬 상태)를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다) 힙은 계산 편의를 위해 인덱스를 1부터 사용한다 (parent: x, left: 2x, right: 2x+1) 힙의 데이터 삽입 여기서 규칙이란 최소힙, 최대힙의 규칙을 의미한다. 리프 노드에 삽입할 노..

자료구조의 HashTable을 한번 구현해봤다. Python에는 딕셔너리 자료구조가 Hash로 되어있기 때문에 직접 구현할 필요는 없지만, Javascript는 Hash 자료구조가 없기 때문에 직접 구현해줘야 한다. (비슷한 구조로 object가 있지만, 탐색 시 O(N)이 걸린다는 단점이 존재) HashTable 구현 class MyHashTable { // 길이를 명시하는 이유는 나중에 특정 상황에서 길이를 늘리고자 함 // 해시 충돌에 대응하기 위함 table = new Array(71); numItems = 0; // load factor 설정을 위해 아이템의 개수를 측정할 수 있는 변수 생성 resize() { // 새로운 배열 생성 const newTable = new Array(this.ta..

Hash란? 해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. - wikipidia 해시 테이블 토는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다. - 팀스파르타 알고리즘 강의 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. Hash의 용도 중 하나는 Hash table이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트..

Queue 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. - wikipidia 먼저 들어간 것이 먼저 나가는 "선입선출"로, FIFO 구조를 가지고 있다. 삭제 연산이 수행되는 곳을 Front, 삽입 연산이 이루어지는 곳을 Rear로 FIFO 구조를 위해서 스텍과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다. 큐는 Rear에서 이루어지는 삽입 연산을 Enqueue라고 부르며, Front에서 이루어지는 삭제 ..

이번에는 이중 연결 리스트를 구현했다. Doublylinkedlist 구현 // 이중 연결 리스트 Class Node class Node { constructor(data) { this.data = data; this.next = null; // 이중 연결 리스트이기 때문에 이전 값도 추가되어야 한다. this.prev = null; } } class DoublyLinkedList { constructor() { // 처음 만들었을 경우, head는 null을 넣어야 한다. this.head = null; // 마지막도 null을 해준다. this.tail = null; // 연결 리스트의 크기를 보기 위해 삽입 this.length = 0; } pushFirst(data) { let newNode = ..

Linkedlist란? 연결 리스트(Linkedlist)는 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 데이터를 담고있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당하게 된다 - wikipidea 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다. 삽입과 삭제 : O(1) (삭제의 경우 특정 노드를 아는 경우에는 1이지만, 모르는 경우에는 n만큼의 시간이 소요된다.) 탐색 : O(n) 연결 리스트의 가장 첫 번째 지점을 Head라고 부른다. 마지막 노드는 Null을 가리킨다. 장단점 장점 연결 리스트는 데이터 구조의 큰 틀을 바꾸지 않고 노드를 추가하거나 삭제하기 쉽다. 연결 리스트는 배..