CS/자료구조9 [자료구조] 해시 (Hash) Hash : 임의 값을 고정길이로 변환하는 행위 🏷️ 해시 함수(hash function) 란? 키 값을 데이터 주소로 변환하는 함수 데이터를 효율적으로 관리하기 위해 키 값(Key)을 해시 값(hash value)으로 매핑(hashing)하는 함수이다. 키 값을 비교하여 찾는 검색이 아니라, 산술적인 연산을 이용하여 해시 값으로 계산하여 데이터 주소로 찾아가는 계산 검색이다. 🏷️ 해시 테이블(Hash Table) 이란? 해시 함수를 사용하여 Key를 해시 값으로 매핑하고, 매핑된 값을 색인(index) 혹은 주소로 삼아 데이터 값과 함께 형식으로 저장하는 자료구조 접근 구조 Bucket : 해시 테이블 내의 저장 공간 Slot : 버킷 내부의 개별적인 저장 공간 특징 검색 .. 2023. 7. 29. [자료구조] 신장 트리 (Spanning Tree) 🏷️ 신장 트리(Spanning Tree) 란? 무방향 그래프에서 모든 노드를 포함하는 부분 그래프이며, 사이클이 없는 단순 연결 그래프(Tree)이다. 특징 연결 그래프 G는 둘 이상의 신장 트리를 가질 수 있다. 그래프 G에서 최소한으로 연결된 그래프가 신장 트리이다. 그래프 G의 모든 신장트리는 동일한 수의 정점 N과 N-1개의 간선을 가진다. N개의 모든 정점과 N-1개의 간선으로 이루어져 있다. 사이클이 존재하지 않는다. 연결 그래프 탐색을 통해 신장트리를 생성 할 수 있다. DFS를 통해 생성된 신장 트리 : 깊이 우선 신장 트리(Depth First Spanning Tree) BFS를 통해 생성된 신장 트리 : 너비 우선 신장 트리(Bredth First Spanning Tree) 응용 분야.. 2023. 7. 29. [자료구조] 그래프 (Graph) 🏷️ 그래프(Graph) 란? 요소들 간의 관계를 표현하는 망구조를 구현한 자료구조 구조 그래프 G 는 연결할 객체를 나타내는 정점(vertex)의 집합 V와 연결하는 간선(edge)의 집합 E로 구성되며, G = ( V , E )으로 표현할 수 있다. Vertex(정점) : 그래프의 기본 요소 Edge (간선) : 정점과 정점을 연결하는 선 Degree (차수) : 정점이 가지는 간선의 수 정점을 향하면 진입차수(in-degree) 정점에서 나가면 진출차수(out-degree) 방향 그래프에서 정점의 차수 = 진입차수 + 진출차수 Path(경로) : 정점 a → b까지 간선을 따라 이동할때 만나는 정점을 순서대로 나열한 리스트 단순 경로 : 시작 정점과 끝 정점을 제외하고 정점을 중복으로 거치지 않는 .. 2023. 7. 29. [자료구조] 이진 힙 (Binary Heap) 🏷️ 힙(Heap)이란? 완전 이진트리 기반의 자료구조로, 최대 또는 최솟값을 빠르게 검색하기 위한 자료구조 특징 완전 이진 트리 : Heap은 완전 이진트리를 기반의 자료구조이다. 때문에, 배열을 사용하여 효울적으로 구현할 수 있다. 시간복잡도 : 삽입 삭제 연산의 시간복잡도는 O(log n)이다. 노드간의 관계 : Heap은 부모 > 자식 이거나, 부모 자식 노드 관계를 가지는 Heap Min Heap : 항상 부모 노드 < 자식 노드 관계를 가지는 Heap 우선순위 큐 : 힙은 우선순위 큐를 구현하기 위해 사용되는 자료구조 중에 가장 효율적인 자료구조이다. 기본연산 Java에서의 He.. 2023. 7. 29. [자료구조] 이진 검색 트리 (Binary Search Tree) 🏷️ 이진 검색 트리(Binary Search Tree)이란? 모든 노드가 최대 2개의 자식 노드를 가지면서, 왼쪽 자식 < 부모 < 오른쪽 자식 관계를 가지는 자료구조 특징 이진 검색트리는 중복값을 허용하지 않기 때문에, 동일한 값을 가진 노드가 2개 이상 존재하지 않는다. 왼쪽 < 노드 < 오른쪽 관계를 항상 준수한다. 모든 노드에서 왼쪽 서브트리의 모든 값은 해당 노드의 값보다 작고, 오른쪽 서브트리에 속한 노드들의 값은 해당 노드의 값보다 다. 모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리는 모두 이진 검색 트리이다. 🏷️ 이진 검색 트리(Binary Search Tree) 구현 연산 검색, 삽입, 삭제 연산 평균 시간 복잡도는 O(logN), 최악의 경우, O(n) 이다. 검색 검색은 항상 .. 2023. 7. 29. [자료구조] 트리 (Tree) 🏷️ 트리 (Tree) 란? 비선형 자료구조로 자료들 간의 계층 관계를 가지는 계층형 자료구조 구조 Node Root Node : 트리의 가장 상단에 위치한 노드 Parent Node (부모 노드) : 노드의 바로 위에 있는 노드를 부모노드라고 한다. Child Node (자식 노드) : 노드의 바로 아래에 있는 노드를 자식노드라고 한다. Sibling Node (형제 노드) : 같은 부모 노드를 가지고 있는 노드 Leaf Node (단말 노드) : 자식노드가 없고, 가장 끝에 위치한 노드 Key : 노드에 저장된 값을 의미한다. Edge (간선) : 노드를 연결하는 선 Degree (차수) : 노드가 가지는 서브트리 혹은 자식 노드의 개수 Level : 루트 노드부터 특정 노드까지의 경로에 존재하는 간.. 2023. 7. 29. [자료구조] 큐 (Queue) 🏷️ 큐(Queue) 란? 데이터를 순서대로 저장하고, 가장 먼저 저장된 데이터가 가장 먼저 삭제되는 자료구조이다. 특징 Rear, Front : Queue는 삽입 연산은 Rear에서, 삭제 연산은 Front에만 가능하다. 선입선출(FIFO) : 시간 순서에 따라 자료가 저장되고, 가장 처음에 저장된 데이터가 가장 먼저 제거된다. 기본 연산 EnQueue : 큐의 마지막 위치(Rear) 데이터를 삽입 DeQueue : 큐의 처음 위치(Front) 데이터 제거 Peek : 큐의 처음 데이터(Front) 반환 IsEmpty : 비어있는지를 True, False로 반환 Size : 저장된 데이터의 개수를 반환 🏷️ 큐(Queue) 구현 순차 자료구조 큐를 1 차월 배열을 통해 구현되는 방식은 데이터가 순차적으.. 2023. 7. 25. [자료구조] 스택(Stack) 🏷️ 스택(Stack)이란? 데이터를 쌓아 올리는 형태의 선형 자료구조 특징 TOP : Stack은 top으로 정한 한 곳에서만 데이터를 쌓을 수 있고, 삽입 삭제가 가능하다. 후입선출(LIFO) : 시간 순서에 따라 자료가 쌓이고, 가장 최근에 삽입된 데이터가 가장 먼저 제거된다. 기본 연산 Push : 스택의 최상단(Top)에 데이터를 삽입 Pop : 스택의 가장 최근 데이터 제거 Peek : 스택의 최상단(Top) 데이터 반환 IsEmpty : 비어있는지를 True, False로 반환 Size : 저장된 데이터의 개수를 반환 🏷️ 스택(Stack) 구현 순차 자료구조 스택이 1차원 배열을 통해 구현되는 방식은 데이터가 순차적으로 쌓이는 순서를 배열의 인덱스로 표현한다. 마지막 데이터의 인덱스를 to.. 2023. 7. 25. [자료구조] 배열(Array) & ArrayList & 연결 리스트(LinkedList) 🏷️배열 ( Array ) 배열은 동일한 데이터 타입의 원소들을 연속된 메모리 공간에 저장하는 선형 자료구조 장점 순서 : 배열은 메모리에 논리적인 순서대로 연속적으로 저장되기 때문에 순서가 유지된다. 인덱스 : 순서가 존재하기 때문에, 인덱스를 통한 접근이 가능하다. 시간복잡도는 O(1)이다. 메모리 : 배열은 요소들을 연속된 메모리 공간에 저장하기 때문에 메모리 관리가 용이하다. 단점 고정된 크기 : 선언할 때 크기를 정할 수 있고, 선언 후에는 변경이 불가능하다. 삽입/삭제 : 작업 시 다른 요소들을 모두 이동시켜야 하고, 최악의 경우 시간복잡도는 O(n)이다. 🏷️ ArrayList ArrayList는 크기가 가변적인 동적 배열을 구현한 자료구조 장점 동적 크기 : 삽입/삭제 작업 시에 자동으로 .. 2023. 7. 24. 이전 1 다음
