힙 트리 우선순위 큐를 위해 만들어진 자료구조 최소 값이나 최대 값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 한 자료구조 우선순위 큐 : 우선순위 개념을 큐에 도입한 자료구조. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다. 반 정렬 상태 완전 이진 트리의 일종 중복 값을 허용 종류 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 힙 구현의 표준은 배열이다. 부모와 자식 인덱스는 항상 정해져 있다. 왼쪽 자식 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..
자료구조 데이터를 저장하는 방식. 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 반드시 필요하다. [선형 자료구조] 한 종류의 데이터가 선처럼 길게 나열된 자료구조 ▶ 탐색법 : 순차 탐색, 이진 탐색이 있음 Ⅰ. 랜덤 접근 가능 모든 자료에 O(1)의 시간 복잡도로 접근할 수 있는 자료구조 배열, 해시가 포함된다. 1. 배열(Array) 🔗 ▶ 정의 배열 : 같은 타입의 변수들로 이루어진 유한 집합 배열 요소(element) : 배열을 구성하는 각각의 값 인덱스(index) : 배열의 위치를 가리키는 숫자. 0에서 시작한다. ▶ 종류 1차원 배열, 2차원 배열 등 ▶ 특징 배열이 차지하는 메모리의 크기 = 배열의 길이 * sizeof(타입); 2. 해시(Hash) 🔗 ▶ ..
문자열(String)? 말그대로 문자열. 둘 이상의 결합된 문자를 뜻다. 문자열은 단순구조이다. 단순구조 : 정수, 실수, 문자, 문자열 등 자료의 형태 문자열의 구현 보통 배열로 표현할 수 있지만, 자바에서는 아예 기본형으로 제공된다. C에서는 문자열의 끝이 특정문자(NULL, ASCII 0번 문자)로 정해져 있다. 참고 https://gusdnd852.tistory.com/166 https://librewiki.net/wiki/%EC%8B%9C%EB%A6%AC%EC%A6%88:%EC%88%98%ED%95%99%EC%9D%B8%EB%93%AF_%EA%B3%BC%ED%95%99%EC%95%84%EB%8B%8C_%EA%B3%B5%ED%95%99%EA%B0%99%EC%9D%80_%EC%BB%B4%ED%93%..
✅ 비선형 자료구조 : i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조 힙(Heap)? 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조. 일종의 반정렬 상태를 유지한다. 힙 트리 중복 값을 허용한다. 우선순위 큐 : 우선순위의 개념을 큐에 도입. 데이터들이 우선순위를 가지고 있어서 우선순위가 높은 데이터가 먼저 나간다. 반 정렬 상태 : 어려 값 중에서 최댓값과 최솟값을 빠르게 찾도록 만들어진 자료구조이다. 힙의 종류 최대 힙(Max Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 최소 힙(Min Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 힙의 구현 힙을 다루는 표준 자료구조는 배열이다. 높이 순서대로 조회하면..
