알고리즘/자료구조 (13) 썸네일형 리스트형 해시 테이블(Hash Table) Goal연관 배열과 해시 테이블에 대한 이해해시 테이블 관련 용어에 대한 이해해시 함수를 구현해본다.해시 충돌 처리 기법에 대해 몇 가지 설명할 수 있다.해시 테이블(hash table)이란?연관 배열(associative array)의 일종으로, 키(key)를 값(value)에 매핑할 수 있는 자료구조이다. *연관 배열 vs 해시 테이블더보기연관 배열(associative array) : (키, 값) 쌍으로 구성된 추상 자료형으로 연관 배열에서 키는 유일한 값을 갖는다.맵(map), 사전(dictionary)으로 불리기도 한다.참고) https://en.wikipedia.org/wiki/Associative_array 구현 형태 해시 테이블 관련 용어해시 테이블연관 배열(associative array.. AVL Tree Goal 자가 균형 트리에 대한 이해 AVL 트리에 대한 이해 AVL 트리를 직접 구현해본다. AVL Tree란? 자가 균형 이진탐색 트리(self-balancing binary search tree) 일종으로, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. AVL 트리는, 트리가 비균형 상태가 되면 스스로 노드들을 재배치(self-balancing)하여 균형 상태로 만든다. 따라서, 항상 균형 트리를 보장하기 때문에 O(logn)의 탐색 시간을 보장한다. *이진 탐색 트리에서 균형을 유지하는 것이 중요한 이유 더보기 이진 탐색 트리 연산(삽입, 삭제, 탐색)의 시간 복잡도는 탐색 시간에 지배된다. 그렇기 때문에 이진 탐색 트리에서 균형을 유지하는 것은 굉장히 .. 힙(heap) Goal 힙(heap)에 대한 이해 힙의 특징을 이해하고, 어떤 상황에서 쓰면 좋은지 설명할 수 있다. 힙을 표현할 수 있다 힙을 사용해서 우선 순위 큐를 구현하고 정렬할 수 있다. 힙(heap)이란? 완전이진트리(complete binary tree)를 기본으로 한 자료구조로서 다음과 같은 힙 속성(heap property)을 만족한다. 힙 속성(heap property) heap order property : 부모 자식 노드간에 대소 비교가 가능하다 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다(최대 힙, Max heap) 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다(최소 힙, Min heap). heap shape property : 완전이진트리 모양이다. (완전이진트리 .. 가중치 그래프(Weighted Graph), 최소 신장 트리(MST) Goal 가중치 그래프에 대한 이해 가중치 그래프를 표현(또는 구현)할 수 있다 최소 신장 트리에 대한 이해 최소 비용 신장 트리를 구할 수 있다 사전 관련 지식 : 그래프 가중치 그래프(Weighted Graph) 그래프의 간선에 가중치가 있는 그래프 가중치 그래프는 다음과 같이 표현된다. G = (V,E, w) V(G) : 그래프 G의 정점 집합 E(G) : 그래프 G의 간선 집합 w(e) : 간선 e의 가중치 (간선의 가중치(weight) 또는 비용(cost) 모두 같은 의미이다.) 가중치 그래치 그래프의 응용 분야는 매우 다양한데, 그 중에서 네트워크를 표현하는데 많이 사용되기 때문에 가중치 그래프를 네트워크라고도 한다. 가중치 그래프는 최소 환승, 최단 경로, 최소 비용 등과 같은 것들을 계산할.. 트리(Tree) Goal 트리 기본 용어에 대한 이해 트리와 이진 트리의 정의를 말할 수 있다 트리와 이진트리의 성질에 따른 특징을 설명할 수 있다 이진 탐색 트리에 대한 이해(정의, 연산, 성능, 활용 예시) 힙에 대한 이해(정의, 연산, 성능, 활용 예시) 트리의 기본 용어 트리는 그래프의 특수한 형태로 그래프 모양이 나무를 뒤집어 놓은 것 같다고 해서 이름 붙여졌다. (트리 용어 이전에 그래프에 대한 이해와 관련 용어를 찾아보면 좋다) 그래프 루트 노드(Root Node) : 트리에서 부모가 없는 최상위 노드. 트리의 시작점 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(Siblings Node) :.. 그래프(Graph) Goal 그래프가 무엇인지 설명할 수 있다 그래프 기본 용어에 대한 이해 특징에 따라 그래프를 구분지어 말할 수 있다 인접행렬, 인접 리스트에 대한 이해 (그래프 표현 방법에 대한 이해) 그래프 탐색에 대한 기본 이해 (DFS, BFS) 그래프(Graph) 정점(vertex/node)과 간선(edge/link)으로 구성된 자료구조 그래프(G) = 정점 집합(V) + 간선 집합(E) 수학적으로 그래프를 G = (V,E)와 같이 표현 정점(vertex / node) : 여러 가지 특성을 가질 수 있는 객체 간선(edge / link) : 정점들간의 관계 ex) 그래프 G1, G2가 있을 때 각각의 그래프의 정점과 간선은 다음과 같이 표시할 수 있다. - V(G1), E(G1) - V(G2), E(G2) 설명.. 덱(Deque) Goal 덱을 구현 할 수 있다 덱의 구조를 그리고 설명할 수 있다 덱(Deque) 데이터의 입/출력이 양 끝단에서만 이루어지는 형태의 자료구조 특징 원소의 추가 O(1) 원소의 삭제 O(1) 원소의 확인 O(1) - 제일 앞, 뒤쪽만 확인 가능 삽입 삭제가 양 끝단에서만 이루어지는 제한적 선형 자료구조이다 덱(Deque)은 앞, 뒤 양쪽에서 데이터의 삽입 삭제가 가능하다는 점에서 스택이나 큐보다 덜 제한적이다. 이런 특징 때문에 Deque을 Stack또는 Queue형태로 사용이 가능하다. (입출력 부분의 함수를 제한을 걸면된다) 덱(Deque)의 구현 BOJ 덱 구현 문제 : https://www.acmicpc.net/problem/10866 - 배열 덱 - https://github.com/jihyu.. 큐(Queue) Goal 큐를 구현할 수 있다. (배열, 링크드 리스트로 구현) 큐 구조를 그리고 설명할 수 있다 큐가 사용되는 예시를 들고, 어떨 때 사용되는지 설명할 수 있다 큐(Queue) 데이터의 입력은 가장 뒤쪽(back, rear)에서, 출력은 가장 앞쪽(front)에서 이루어지는 형태의 제한적 선형자료구조 먼저 입력된 순서대로 출력되는 선입선출(FIFO) 형태의 자료구조 특징 원소의 추가 O(1) 원소의 삭제 O(1) 제일 앞쪽(front), 제일 뒤쪽(back) 원소 확인 O(1) => 원칙적으로 중간에 있는 데이터 확인 및 변경 불가능 원형 큐(Circular Queue) 큐를 논리적으로 원형 형태로 설계한 자료구조 원형큐는 큐를 배열로 구현했을 때 발생하는 문제점을 보완하기 위해 고안된 자료구조이다. .. 이전 1 2 다음
