자료구조6 Tree 트리 구조란 그래프의 일종이다. 트리는 노드로 구성된 계층적 자료구조인데 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 구현할 수 있다. A, B, C, D 등 트리를 구성하는 요소를 node라고 하며 이 노드를 잇는 선을 edge라고 한다. A와 같이 최상위 노드를 root라 하며 루트를 기준으로 하위 노드와의 거리를 depth라고 한다. 같은 부모를 가지며 같은 depth에 존재하는 F, G는 sibling관계에 있다고 한다. E는 J의 parent이고 J는 E의 child이다. H, I와 같이 자식이 없는 노드를 leaf라고 한다. 2021. 1. 25. Graph 그래프는 정점(vertex 또는 node라고 불림)과 정점과 정점 사이를 잇는 간선(edge)으로 구성된 자료구조를 말한다.그래프는 무방향, 방향일 수 있다. 이는 간선에 의해 연결된 2개의 정점이 대칭, 비대칭일 수 있음을 의미한다. 그래프의 구현 방식에는 두 가지 방법이 있다. 1. 인접 행렬 방식(Adjacency)2차원 배열을 이용하여 n개의 정점 사이의 간선을 표현하는 방식이다.위의 무방향그래프(왼쪽)로 예를 들어 보면 이와 같이 표현할 수 있다.(무방향 그래프이기 때문에 대칭적으로 구현된다.)이제 이배 열을 순환하면서 정점과 정점 사이의 관계를 알아낼 수 있다. 2. 인접 리스트 방식(Adjacency list)리스트를 이용하여 구현한 방식으로 배열, 연결 리스트 등으로 구현 가능하다.위의 방.. 2021. 1. 25. Hash Table hash table은 키, 값으로 구성된 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 해시 함수를 통해 특정 숫자 값의 인덱스로 변환하여 사용한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다. 이처럼 key값을 해시 함수로 특정 숫자 값으로 변환시켜 저장하는 구조이다. key값을 해시 값으로 변환하는 과정을 해싱(hashing)이라 한다. hash table은 storage 배열 안에 hash값을 index로 하는 bucket의 형태로 되어 있다. 이때 bucket안에 원래의 데이터 key, value가 tuple에 들어가 있는 것을 볼 수 있다. 값의 변경을 막기 위해 tuple을 사용하여 bucke.. 2021. 1. 23. Linked List linked list는 노드로 구성이 되어 있으며 각 노드가 데이터와 포인터를 가지고 한 줄로 연결된 방식의 자료구조이다. 여기서 포인터는 각 노드를 연결하는 역할을 한다. linked list는 단일 연결 리스트와 이중 연결 리스트 등이 있다. linked list에는 head와 tail이 있는데 head에서 시작하여 포인터를 따라가면 tail에 도착하는 구조이다. 이중 연결 리스트는 위의 예시에서 봤을 때 포인터를 단방향에서 양방향으로 이어주면 된다. (이중 연결 리스트에서는 tail에서 시작하여 포인터를 따라갈 수 있다.) 시간 복잡도 linked list는 배열과 다르게 index가 없다. 그래서 값을 가져오기 위해서는 포인터를 따라 일일이 다 검색을 해줘야 하기에 시간 복잡도는 O(n)이 된다... 2021. 1. 22. Queue queue는 먼저 집어넣은 데이터가 먼저 나오는 First In First Out 구조로 되어있다. 나중에 집어넣은 데이터가 먼저 나오는 stack과 반대되는 개념이다. queue는 놀이공원에서 서는 줄과 같이 작동한다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다. queue의 메서드에는 enqueue, dequeue, size 가있다. enqueue는 queue에 맨 뒤에 요소를 추가해주고 dequeue은 queue의 맨 앞의 요소를 꺼내고 이를 반환해준다.(return값이 있다.) size는 queue의 데이터 개수를 반환해준다. let queue = new Queue(); queue.enqueue(1); queue.enqueue(2); queue.dequeue(); .. 2021. 1. 21. Stack stack은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(Last In First Out)로 되어 있다. stack은 쌓여있는 접시 더미와 같이 작동하는데 새로운 접시가 쌓일 때 맨 위에서 쌓이고, 접시를 가져갈 때는 맨 위에서 가지고 간다. stack의 메서드에는 push,pop,size 가 있다. push는 stack에 맨뒤에 요소를 추가해주고 pop은 stack의 맨뒤의 요소를 꺼내고 이를 반환해준다.(return값이 있다.) size는 stack의 데이터 개수를 반환해준다. let stack = new Stack(); stack.push(1); stack.push(2); stack.pop(); // 2 stack.size(); // 1 시간 복잡도 stack에서 추가하기와 삭제하기의 경우의.. 2021. 1. 21. 이전 1 다음
