자료구조6 (191120) - 자료구조 Hash Table Hash Table 해시테이블은 내부적으로 배열을 사용하여 데이터를 저장을 하기 때문에 특정한 값을 탐색하거나 추출할 때, 데이터의 삭제나 추가시에 시간복잡도가 평균적으로 O(1)이 나온다. 이는 해시 테이블이 데이터 고유의 index를 사용하여 바로 접근하기 때문이다. (평균적으로 O(1) 이고 O(N)이 나올 수도 있는데 조금 있다가 설명) 구성 해시 테이블은 기본적으로 키(key), 해시 함수(hash function), 해시(hash), 값(value), 저장소(bucket) 으로 이루어져 있다. 키(key) : 해시 함수의 input이다. 다양한 길이의 값일 수 있다. 해시 함수(hash function) : 키를 해시로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 input으로 받아.. 2019. 11. 20. (191118) 자료구조 - 이진 탐색 트리 이진 탐색 트리 (Binary Search Tree) 특징 - 기본적으로 이진 트리이므로 각 노드는 최대 2개의 자식만을 갖는다 (0~2개) - 모든 노드의 값은 유일하다 (중복된 값이 없다) - 좌측 하위트리의 값은 상위 노드(부모노드)의 값보다 작은 값이어야 한다. - 우측 하위트리의 값은 상위 노드(부모노드)의 값보다 큰 값이어야 한다. - 그리고 하위 트리의 하위 트리들도 같은 특징을 갖는다. 이진 탐색 트리의 탐색 방법 1. 찾고자하는 값을 루트 노드의 값과 비교 한다. 1-1. 비교해서 같으면 루트 노드를 리턴하고 탐색을 마친다. 2. 찾고자하는 값이 루트 노드의 값보다 크다면 루트노드 기준으로 오른쪽의 하위 노드를 기준으로 하여 다시 탐색한다. (1번 과정에서 루트 노드 대신 루트노드의 오른.. 2019. 11. 18. (191117) 자료구조 - Tree Tree 자료구조 tree는 graph 자료구조의 한 종류이다 -> 사이클이 없는 연결 그래프 + 유향 - 사이클이 없다 : 한 시작 정점과 종료 정점이 같지 않음 (즉, 끝에서 시작으로 못가) - 연결 그래프 : 모든 정점쌍에 항상 경로가 존재 (끊어진게 없다는 소리?) - 유향 그래프 : 루트 노드부터 자식노드로 ~ Base - 그래프의 한 종류이기 때문에 마찬가지로 정점과 간선으로 구성 - 루트 노드가 있고 루트 노드는 0개 이상의 자식을 갖음(자식 노드도 마찬가지) - 각 노드는 어떤 자료형으로도 표현 가능 - 계층 자료를 나타낼 때 사용 (디렉터리, 조직도 등!!) 용어 - 루트 노드(root node) : 부모가 없는 노드, 즉 트리는 하나의 루트 노드만 갖는다. - 단말 노드 (leaf no.. 2019. 11. 17. (191117) 자료구조 - Graph Graph 자료구조 연결되어 있는 데이터들의 관계를 표현할 수 있는 자료구조 정점(vertex)과 간선(edge)의 집합, root 노드 개념이 없음, 부모-자식 노드 개념이 없음 Graph 용어 정점(vertex) : 위치 (node 라고도 부름) 간선(edge) : 노드를 연결하는 선을 말함 무향 그래프 와 유향 그래프 - 정점과 간선의 연결 관계에 있어서 방향이 없는 것 / 있는 것 정점의 차수(degree) : 각 정점에 연결된 간선의 갯수 (무향 기준) - Indegree : 유향에서 정점에 들어오는 간선의 갯수 - Outdegree : 유향에서 정점에서 나가는 간선의 갯수 가중치 그래프 - 간선에 가중치 정보를 두어서 구성한 그래프 (네트워크) 연결 그래프 와 비연결 그래프 - 무향 그래프에 .. 2019. 11. 17. (191117) 자료구조 - Linked list 정리하면서 느낀점 핵심은 배열은 탐색은 O(1),탐색은 O(n)!!, 특정 index값 추출이 O(1), 데이터의 삭제 및 추가는 O(n) 연결리스트는 탐색은 O(n), 데이터의 삭제 및 추가는 O(1) 인듯.... (블로깅 하는데 너무 몰입하지말자...시간 너무 많이 씀....) 연결 리스트 (Linked list) 연결리스트에 대해 알아보기전에 배열과 연결리스트를 비교해보자. 배열 (array) - 데이터가 연속적으로 저장되어 있음 장점 1. 특정 데이터(엘리먼트)에 접근할 때 인덱스를 사용하여 매우 빠르고 간단하게 접근할 수 있다. 단점 1. (컴파일언어?에서) 배열을 사용하기 위해서는 배열의 크기를 미리 선언해야하고 크기의 수정이 불가능하기 때문에 메모리 관점에서 비효율적이다. 2. 중간에 데이터.. 2019. 11. 17. (191114) 자료구조 - Stack, Queue 오늘 배운 것 - 자료구조란 무엇인가 - 자료구조 중 stack 과 queue는 무엇인가 아래에 정리!! - 스택과 큐에 대한 기본 개념에 대해서 알 수 있었다. Stack 자료구조 stack 자료구조는 후입선출(LIFO, Last In First Out)의 구조로 위 모습에서 알 수 있듯이 쉽게 상자를 생각하면 된다. 빈 상자에 물건을 쌓는 경우 상자에 가장 먼저 들어온 물건이 제일 밑에 쌓이고 제일 마지막에 들어온 물건이 맨 위에 쌓이기 때문에 만약 물건을 뺀다고 하면 제일 마지막에 들어온 물건부터 상자에서 빠지게되고 제일 먼저 들어온 물건은 그 다음에 들어온 물건들이 모두 빠져야 뺄 수 있다. (stack의 대표적인 예 : 브라우저의 뒤로가기) Property / Method stack 자료구조는 .. 2019. 11. 14. 이전 1 다음
