힙 트리 우선순위 큐를 위해 만들어진 자료구조 최소 값이나 최대 값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 한 자료구조 우선순위 큐 : 우선순위 개념을 큐에 도입한 자료구조. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다. 반 정렬 상태 완전 이진 트리의 일종 중복 값을 허용 종류 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 힙 구현의 표준은 배열이다. 부모와 자식 인덱스는 항상 정해져 있다. 왼쪽 자식 index = (부모 index) * 2 오른쪽 자식 index = (부모 index) * 2 + 1 부모 index = (자식 inde..
트리 노드들이 나뭇가지처럼 연결된 비선형 계층적 자료구조 그래프의 한 종류이다. 하나의 루트 노드와 0개 이상의 하위 트리 비선형 자료구조 : 데이터를 순차적으로 저장하지 않음 재귀적 자료구조 : 트리 내에 또 다른 트리가 있다. loop가 없는 연결 무방향 그래프 모든 자식 노드는 하나의 부모 노드만 갖는다. 노드가 n개인 트리는 항상 n-1개의 간선을 가진다. 관련 용어 노드(Node) : 그래프의 정점 루트 노드 : 트리의 기준이 되는 노드. 나무의 뿌리를 생각하면 된다. 루트 노드에서 가지가 뻗어나가는 이미지. 부모 노드 : 자신과 인접한 노드들 중 루트 노드로 향하는 노드 자식 노드 : 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드 단말 노드 : 자식 노드가 존재하지 않는 노드..
그래프 노드와 그 노드를 연결하는 간선을 모아 놓은 자료구조 즉, 연결된 객체 간의 관계를 표현하는 자료구조 관련 용어 정점(vertex) : 위치라는 개념. node라고도 부름 간선(edge) : 위치 간의 관계. 즉, 노드를 연결하는 선. link, branch라고도 부름 인접 정점 : 간선에 의해 직접 연결된 정점 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(내차수) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(외차수) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 : 경로를 구성하는 데 사용된 간선의 수 단순 경로 : 반복되는 정점이 없는 경로 (한붓그리기) 사이클 : 단순 경로의 시작과 종료 정점이 동일한 경우 그래프 구현 방법 1. 인접 행렬(2차원..
스택(Stack) LIFO(Last In First Out) 구조로, 가장 나중에 들어온 게 먼저 나간다. 맨 위만 바라보는 구조 ex) 뒤로가기(ctrl+Z) 사용 스택 구현체 없음 Array.prototype 사용 arr.push() // 삽입 arr.pop() // 삭제 // peek()은 없음! 배열의 마지막 인덱스로 접근 큐(Queue) FIFO(First In First Out) 구조로, 가장 먼저 들어온 게 먼저 나간다. 맨 아래에서만 꺼낼 수 있음 ex) 인터넷 쇼핑 배송, 마트 진열 사용 큐 구현체 없음 Array.prototype 사용 arr.push() // 삽입 arr.shift() // 삭제 // peek()은 없음! 배열의 0 인덱스로 접근
연결리스트 순서가 있는 데이터들을 저장할 때 그 다음(이전) 순서의 데이터가 있는 주소를 현재 데이터에 포함시키는 방식으로 자료를 저장하는 구조 노드 연결 리스트에서 노드는 데이터와 포인터를 가지는 객체를 의미 포인터 : 다음 노드의 주소 각 포인터 변수의 주소도 따로 존재한다. 장점 필요할 때마다 데이터를 생성하여 연결하면 되기 때문에 메모리 효율 좋음 삭제 및 추가 시 데이터 재구성 용이 단점 탐색 시 느림 (처음 또는 마지막 노드 탐색은 빠름) 구현이 까다롭다 데이터를 저장할 공간 뿐만 아니라 다음 노드의 주소를 저장하는 공간이 추가적으로 필요 사용 자바스크립트에서는 포인터가 없다. 때문에 객체를 참조하는 방식으로 구현 (오히려 더 간단하다) 연결리스트 구현 function Node(val) { t..
Hash Table Hash 고유한 데이터를 다루는 기법 또는 고유한 값 key-value 구조이다. hash table에서 hash는 해시 함수를 통해 만들어진 고유한 값이다. Hash Function 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 함수 내부적인 패턴에 의해 고유한 값(hash)이 생성되어 반환된다. Input : key // output : Hash 이렇게 나온 해시가 저장위치가 된다. Hash Table 해시 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 주소 또는 색인 삼아 데이터를 key와 함께 저장하는 자료구조 자바스크립트에서 Object, (Map, Set) 시간복잡도 : O(1) 아래 구조로 되어있다. 구성 key : 고유한 값. Input key..
