Computer Science/자료구조11 [자료구조] 그래프(Graph) 그래프란?그래프는 vertex와 edge로 구성된 대표적인 비선형 자료구조이다.vertex는 트리에서 노드와 비슷한 개념이고, edge는 vertex간의 연결관계를 나타내는 선이다.두 vertex가 edge로 연결되어있을때, 두 vertex는 "인접해있다" 고 한다. 트리도 그래프의 일종이지만, 그래프는 트리보다 훨씬 더 넓은 범위를 포함한다. 그래프의 종류- 방향 그래프 (directed graph) 화살표를 이용해서 방향을 표시할 수 있는 그래프를 방향그래프라고 한다.방향 그래프는 무조건 방향의 순서대로만 노드를 이동시킬 수 있다. 방향이 없는 그래프는 무방향 그래프(undirected graph)라고 한다. - 가중치 그래프 (weighted graph)가중치 그래프는 아래그림처럼 ed.. 2024. 8. 3. [자료구조] 이진탐색트리(BST - Binary Search Tree) 일단 트리구조는 그 자체만으로는 데이터값에 대한 어떠한 제약도 없기때문에,어떤 특정한 값을 찾기위해서는 트리의 모든 데이터를 탐색해야하는 상황이 발생한다.그러면 데이터 N개만큼의 탐색을 진행해야하기 때문에 시간복잡도면에 있어서 좋지 않다.이런 문제를 해결하기위해 이진탐색트리가 나오게되었는데, 이진탐색트리는 데이터의 특성에 제약을 줌으로써 탐색속도를 O(logN)으로 줄여주는 특징이 있다. 이진트리와 이진탐색트리 비교이진탐색트리는 기본적으로 왼쪽 자식노드와 오른쪽 자식노드를 가질 수 있다는 점에서 이진트리와 같은 구조라고 볼 수 있다.그러나 일반적인 이진트리와의 차이점은 데이터값에 제약이 생긴다는것이다.이진탐색트리에서는 루트노드를 기준으로 왼쪽서브트리는 루트노드보다 작은값들로만 이루어져있어야하고,오른쪽.. 2024. 7. 26. [자료구조] 이진힙[힙](heap) 힙(Heap)힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기반으로 한 자료구조다. 따라서 완전 이진트리의 속성을 가지고 있다.완전 이진트리의 특징1. 마지막 레벨을 제외하고 모든 노드가 채워져있어야한다.2. 노드는 왼쪽에서 오른쪽 방향으로 채워져야한다. 힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 구분할 수 있다. 최대힙은 부모노드가 항상 자식노드보다 큰값을 가지고 있기 때문에, 루트노드는 항상 트리의 최대값이게 된다! 이와 반대로 최소힙은 부모노드의 값은 항상 자식노드보다 작기 때문에, 루트노드는 항상 트리의 최소값이게 된다!이런 최대힙과 최소힙의 특성.. 2024. 7. 26. [트리순회] 후위탐색(postorder) 저번까지 트리탐색방법 중 하나인 전위탐색과 중위탐색을 살펴봤었다https://coding-juuwon2.tistory.com/441 [트리순회] 전위탐색트리순회(트리탐색)이란?트리순회란 트리구조에서 각 노드를 한번씩 방문하는 과정을 말한다.트리순회에는 3가지 방법이 있다1) 전위탐색 (preorder)2) 중위탐색 (inorder)3) 후위탐색 (postorder)이는 노coding-juuwon2.tistory.comhttps://coding-juuwon2.tistory.com/442 [트리순회] 중위탐색(inorder)저번에는 트리탐색방법 중 하나인 전위탐색을 살펴봤었는데https://coding-juuwon2.tistory.com/441 [트리순회] 전위탐색트리순회(트리탐색)이란?트리순회란 트리구조에.. 2024. 7. 26. [트리순회] 중위탐색(inorder) 저번에는 트리탐색방법 중 하나인 전위탐색을 살펴봤었는데https://coding-juuwon2.tistory.com/441 [트리순회] 전위탐색트리순회(트리탐색)이란?트리순회란 트리구조에서 각 노드를 한번씩 방문하는 과정을 말한다.트리순회에는 3가지 방법이 있다1) 전위탐색 (preorder)2) 중위탐색 (inorder)3) 후위탐색 (postorder)이는 노coding-juuwon2.tistory.com 이번에는 중위탐색을 살펴볼것이다!!중위탐색(inorder) 순서1. 왼쪽 서브트리를 inorder2. 루트 노드 방문 3. 오른쪽 서브트리를 inorder 위의 트리를 중위탐색을 이용해서 탐색해볼건데 탐색방식과 상관없이 시작은 항상 루트노드부터 시작하게된다.루트노드인 A노드부터 시작을 하더라.. 2024. 7. 26. [트리순회] 전위탐색(preorder) 트리순회(트리탐색)이란?트리순회란 트리를 탐색하는 방법인데, 트리구조에서 각 노드를 한번씩 방문하는 과정을 말한다.트리순회에는 3가지 방법이 있다1) 전위탐색 (preorder)2) 중위탐색 (inorder)3) 후위탐색 (postorder)이는 노드방문을 언제하는지를 기준으로 구분할 수 있다. 이번에는 전위탐색을 먼저 살펴볼것이다!!전위탐색(preorder) 순서1. 루트 노드 방문 2. 왼쪽 서브트리를 preorder3. 오른쪽 서브트리를 preorder 전위탐색(preorder)은 루트노드 방문이 제일먼저 이뤄지고그 다음 왼쪽 서브트리를 preorder하고, 그 후에 오른쪽 서브트리를 preorder하는 방식으로 이뤄진다.서브트리를 preorder한다는것은 재귀호출로 탐색이 이뤄지는 것을 의미한.. 2024. 7. 26. 이전 1 2 다음
