본문 바로가기

Base/자료구조5

Data Structure(5) Tree(트리), Binary Search Tree(이진검색트리) Tree (트리) 트리는 노드(node)들을 선(edge)으로 연결한 계층형 자료구조이다. 제일 위에 root(뿌리) 노드 하나가 있고, 그 아래 나머지 자식 노드들이 선으로 연결되고 또 연결되는 구조이다. 나무를 거꾸로 한 모양같다고 해서 트리라는 이름이 붙여졌다고 한다. 관련 용어 루트노드(root node) : 최상위 노드 리프노드(leaf node) : 자식이 없는 노드 부모 노드(parent node) : 노드에 연결된 한단계 상위 레벨 노드 자식노드(child node) : 서브트리의 루트노드들 ex. A의 자식 : B, C 형제노드(sibling) : 같은 부모 + 같은 depth에 있는 노드들 노드의 차수 : 한 노드의 서브트리의 수 트리의 차수 : 트리노드 차수들 중 최대 차수 트리의 높.. 2021. 1. 22.
Data Structure(4) Graph(그래프) Graph (그래프) Graph(그래프)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. 지하철 노선도처럼 서로 연결된 데이터들이 어떤 관계인 지 표시할 때 주로 사용한다. let subway = { '교대': ['동대문운동장','사당','충무로'], '동대문운동장': ['교대','을지로3가','충무로'], '사당': ['교대','서울역', '신도림'], '서울역': ['사당','시청','신도림','충무로'], ...} Graph 종류 그래프는 방향성을 가졌는지 여부에 따라 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)로 구분할 수 있다. 1. 방향 그래프(Directed Graph) 방향 그래프는 말 그대로 방향을 나타내는 화살표가 있는 그래.. 2021. 1. 22.
Data Structure(3) Hash Table(해시 테이블) Hash Table (해시 테이블) 해시 테이블은 { 키(key) : 값(value) } 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키(key)를 '해시 함수'(Hash function)라는 함수를 통해 특정 숫자값의 인덱스(index)로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다. 해시테이블 : 키(key) → 해시 함수(Hash function) → 인덱스(index)로 변환해 저장하는 자료구조! 관련 용어 키(key) : 원래의 데이터 값(해시 함수 입력 전) 값(value) : 최종 저장되는 값 해싱(hashing) : key → index로 바꾸는 과정 해시함수(hash function.. 2021. 1. 21.
Data Structure(2) Linked List (연결 리스트) Linked List (연결 리스트) 우선 List(리스트)는 데이터에 순서를 매겨둔 자료구조이다. 데이터들이 순서대로 쭉 늘어진 모양을 하고있다. 아직까지 이 데이터들은 차례대로 줄을 서고 있을 뿐 서로에 대해 모르는 상태이다. Linked List(연결 리스트)는 데이터들이 연락처를 주고받아 자기 뒤에있는 사람에게 연락을 할 수 있게 된 상태이다. 대신 누군가를 건너뛰거나 뒤를 돌아서 앞 사람에게 연락을 할 수는 없다. 오직 자기 뒷사람에게만 연락할 수 있다! 조금만 더 자세히 살펴보자. 연결 리스트에 일렬로 연결된 데이터들을 각각 노드(node)라고 한다. 그리고 이 노드들은 각각 1) 데이터(data)와 2) 다음 노드 정보(next)를 갖는다. ✔️ 노드(node) = 데이터(data) + 다음.. 2021. 1. 21.
Data Structure(1) Stack (스택), Queue (큐) 스택(Stack), 그리고 큐(Queue)는 모두 '자료구조'의 한 종류이다. 처리해야할 데이터가 많아졌을 때, 어떤 순서로 저장하고 처리해야할 지를 정해둔 방식이라고 할 수 있다. 간단히 말하면 스택은 가장 마지막에 쌓인 데이터를 먼저 처리하고, 큐는 가장 먼저 쌓인 데이터를 먼저 처리한다는 점에서 차이가 있다. 이렇게 데이터들을 임시 저장하는 가장 기본적인 자료구조인 스택(Stack), 큐(Queue)에 대해 좀 더 알아보자! 스택(Stack) 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO — Last In First Out)으로 되어 있다. 스택(Stack)은 번역.. 2021. 1. 19.
반응형

티스토리툴바