Hash Table 해시 테이블을 사용하는 이유? 적은 자원으로 많은 데이터의 효율적인 관리 언제나 동일한 해시 값을 리턴하므로 찾고자하는 값의 index를 알면 빠른 검색이 가능 Hash Function 단방향의 해시 함수를 구현하여 해시 값을 리턴한다. 데이터가 많아지면 다른 데이터가 동일한 해시 값으로 충돌나는 현상이 ‘Collision’ 이다. 좋은 해시 함수란, 데이터는 고르게 분포하고 충돌을 최소화할 수 있는 함수이다. Resolve Collision Open Addressing Linear Probing index에 대한 충돌이 발생했을 때, index 뒤에 있는 버킷 중에 빈 버킷을 찾아 데이터를 넣는 방식 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭..
Graph (그래프) 현실세계 사물, 개념 간 연결 관계를 수학적 모델로 단순화하여 표현한 것 V : 정점 (Vertex / Node) / E : 간선 (Edge / Link / Arc) 표현 : 그래프 G = (V, E) 그래프 용어 정점, 노드 (Vertex, Node) 간선 (Edge) 무향 간선 (Undirected Edge) : 방향이 존재하지 않는 간선으로 양방향이다. 유향 간선 (Directed Edge) : 방향이 존재하는 간선이다. 인접 (Adjacent) : (정점의 관점에서) 두 정점 사이에 간선이 존재하면 A, B는 인접한다. 부속 (Incident) : (간선의 관점에서) 두 정점 사이에 간선 e가 존재하면 간선 e는 두 정점에 부속한다. 차수 (Degree) : 한 정점에 연결된..
Tree (트리) 자료들 사이의 계층적 관계를 나타내는데 사용하는 비선형 자료구조 (부모-자식 관계로 표현) 트리가 만족하는 조건 루트 노드(root node)가 존재 → 트리는 반드시 1개 이상의 노드를 가짐 트리의 부분 트리(sub tree)도 트리 구조를 따름 Tree 용어 루트 노드 (Root) : 트리의 최상위 노드로 unique 부모 노드 (Parent) : 부모-자식에서 상위 계층 노드 자식 노드 (Child) : 부모-자식에서 하위 계층 노드 형제 노드 : 부모가 동일한 노드 조상 노드 : 해당 노드의 부모 노드부터 루트 노드까지 가는 경로에 존재하는 모든 노드들 후손 노드 : 해당 노드를 루트로 하는 부분 트리에 있는 모든 노드들 내부 노드 (internal/nonterminal) : 자..
Stack (스택) 선형 자료구조로 삽입, 삭제 연산이 한 방향에서 수행 LIFO(Last In First Out) : 나중에 들어간 원소가 먼저 나오는 구조 Stack 용어와 주요 연산 용어 Top : 스택에 데이터가 삽입될 위치 연산 push : 스택의 top에 원소 삽입 pop : 스택의 top에 있는 원소 삭제 및 반환 peek : 스택의 top에 있는 원소 반환 Stack 시간 복잡도 데이터 삽입/삭제 : O(1) top 데이터 조회 : O(1) 특정 데이터 조회 : O(n) Stack 활용 시스템 스택(System Stack)과 실행시간 스택(Runtime stack) 프로그램의 함수 호출과 복귀에 따른 실행 순서 관리 웹 브라우저 방문 기록 관리 (뒤로가기) 실행 취소 (undo) 수식의 후..
Array index로 element에 접근이 가능한 자료구조 일반적으로 논리적 저장 장소와 물리적 저장 장소가 같다. 찾고자하는 원소의 index를 알고 있으면 O(1)을 갖는다. 배열의 삭제 작업이 발생하면, 원소 접근 O(1)을 수행하고 빈 공간을 만든 다음 삭제한 원소보다 인덱스가 큰 원소들이 이동하는 비용이 발생하게 되어 O(n)을 수행하게 된다. ( worst case도 O(n) 수행 ) 배열의 추가 작업도 모든 원소들의 인덱스를 이동하는 비용이 발생하여 O(n)을 수행한다. 일반적인 의미의 배열은 메모리 영역을 연속적으로 사용한다. 이러한 배열은 밀집 배열(dense array)이라고 한다. 하지만, 자바스크립트의 배열은 배열 요소를 위한 각각의 메모리 공간이 동일한 크기를 갖지 않아도 되며..
더보기 참고: https://www.geeksforgeeks.org/doubly-linked-list/ 참고: https://yjg-lab.tistory.com/122 ✔️ 이중 연결 리스트란? [자료구조] 연결 리스트: https://slumpdev.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8 이중 연결 리스트를 알려면 우선, 연결 리스트에 대하여 공부를 해야하는데 앞선 글을 참고하자. 이중 연결 리스트, Double Linked List는 자료구조에서 나오는 하나의 개념이다. 간단하게 줄여서 DLL이라고 부르는데, 이중 연결 리스트는 하나의, 단일의 연결 리스트에 ..
