개발 노트/자료구조 (11) 썸네일형 리스트형 [자료구조] 그래프(Graph) 그래프란?그래프는 vertex와 edge로 구성된 대표적인 비선형 자료구조이다.vertex는 트리에서 노드와 비슷한 개념이고, edge는 vertex간의 연결관계를 나타내는 선이다.두 vertex가 edge로 연결되어있을때, 두 vertex는 "인접해있다" 고 한다. 트리도 그래프의 일종이지만, 그래프는 트리보다 훨씬 더 넓은 범위를 포함한다. 그래프의 종류- 방향 그래프 (directed graph) 화살표를 이용해서 방향을 표시할 수 있는 그래프를 방향그래프라고 한다.방향 그래프는 무조건 방향의 순서대로만 노드를 이동시킬 수 있다. 방향이 없는 그래프는 무방향 그래프(undirected graph)라고 한다. - 가중치 그래프 (weighted graph)가중치 그래프는 아래그림처럼 ed.. [자료구조] 이진탐색트리(BST - Binary Search Tree) 일단 트리구조는 그 자체만으로는 데이터값에 대한 어떠한 제약도 없기때문에,어떤 특정한 값을 찾기위해서는 트리의 모든 데이터를 탐색해야하는 상황이 발생한다.그러면 데이터 N개만큼의 탐색을 진행해야하기 때문에 시간복잡도면에 있어서 좋지 않다.이런 문제를 해결하기위해 이진탐색트리가 나오게되었는데, 이진탐색트리는 데이터의 특성에 제약을 줌으로써 탐색속도를 O(logN)으로 줄여주는 특징이 있다. 이진트리와 이진탐색트리 비교이진탐색트리는 기본적으로 왼쪽 자식노드와 오른쪽 자식노드를 가질 수 있다는 점에서 이진트리와 같은 구조라고 볼 수 있다.그러나 일반적인 이진트리와의 차이점은 데이터값에 제약이 생긴다는것이다.이진탐색트리에서는 루트노드를 기준으로 왼쪽서브트리는 루트노드보다 작은값들로만 이루어져있어야하고,오른쪽.. [자료구조] 이진힙[힙](heap) 힙(Heap)힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기반으로 한 자료구조다. 따라서 완전 이진트리의 속성을 가지고 있다.완전 이진트리의 특징1. 마지막 레벨을 제외하고 모든 노드가 채워져있어야한다.2. 노드는 왼쪽에서 오른쪽 방향으로 채워져야한다. 힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 구분할 수 있다. 최대힙은 부모노드가 항상 자식노드보다 큰값을 가지고 있기 때문에, 루트노드는 항상 트리의 최대값이게 된다! 이와 반대로 최소힙은 부모노드의 값은 항상 자식노드보다 작기 때문에, 루트노드는 항상 트리의 최소값이게 된다!이런 최대힙과 최소힙의 특성.. [트리순회] 후위탐색(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 [트리순회] 전위탐색트리순회(트리탐색)이란?트리순회란 트리구조에.. [트리순회] 중위탐색(inorder) 저번에는 트리탐색방법 중 하나인 전위탐색을 살펴봤었는데https://coding-juuwon2.tistory.com/441 [트리순회] 전위탐색트리순회(트리탐색)이란?트리순회란 트리구조에서 각 노드를 한번씩 방문하는 과정을 말한다.트리순회에는 3가지 방법이 있다1) 전위탐색 (preorder)2) 중위탐색 (inorder)3) 후위탐색 (postorder)이는 노coding-juuwon2.tistory.com 이번에는 중위탐색을 살펴볼것이다!!중위탐색(inorder) 순서1. 왼쪽 서브트리를 inorder2. 루트 노드 방문 3. 오른쪽 서브트리를 inorder 위의 트리를 중위탐색을 이용해서 탐색해볼건데 탐색방식과 상관없이 시작은 항상 루트노드부터 시작하게된다.루트노드인 A노드부터 시작을 하더라.. [트리순회] 전위탐색(preorder) 트리순회(트리탐색)이란?트리순회란 트리를 탐색하는 방법인데, 트리구조에서 각 노드를 한번씩 방문하는 과정을 말한다.트리순회에는 3가지 방법이 있다1) 전위탐색 (preorder)2) 중위탐색 (inorder)3) 후위탐색 (postorder)이는 노드방문을 언제하는지를 기준으로 구분할 수 있다. 이번에는 전위탐색을 먼저 살펴볼것이다!!전위탐색(preorder) 순서1. 루트 노드 방문 2. 왼쪽 서브트리를 preorder3. 오른쪽 서브트리를 preorder 전위탐색(preorder)은 루트노드 방문이 제일먼저 이뤄지고그 다음 왼쪽 서브트리를 preorder하고, 그 후에 오른쪽 서브트리를 preorder하는 방식으로 이뤄진다.서브트리를 preorder한다는것은 재귀호출로 탐색이 이뤄지는 것을 의미한.. [자료구조] 이진트리 (Binary Tree) 이진트리(Binary Tree)란?이진트리(Binary Tree)란 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질때 이진트리라고 한다.최대 2개의 자식노드를 가질때이기 때문에 자식이 없을수도 있고, 한개만 있을수도 있다 이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현한다.그래서 같은 루트에 같은 자식노드 하나를 가지고있어도, 자식노드의 위치가 왼쪽과 오른쪽이 다르다면 이 두 트리는 서로 다른 트리가된다.아래 그림은 A라는 같은 루트노드를 가지고있지만, 자식노드의 위치가 왼쪽,오른쪽 다르기때문에 두개의 트리는 별개의 트리(서로 다른 트리)가 된다. 이진트리(Binary Tree)의 종류1. 정 이진트리(Full Binary Tree / Strict Binary Tree) 이.. [자료구조] 트리(Tree)란? 배열, 리스트, 스택과 큐, 해시테이블과 같은 자료구조는 데이터의 이전 데이터나 다음 데이터의 순서가 존재하는 선형 자료구조에 해당한다.이러한 구조는 특정 데이터를 검색할때 순서대로 데이터를 찾아야하는 문제점과,데이터를 저장하기위해 일정한 공간을 미리 할당해야하는 등의 제한적인 구조를 가지고있어 복잡한 문제를 해결하는데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 계층적 문제란 계층적 속성을 갖는 자료는 선형구조로 표현하기가 어렵다는 것을 뜻한다순환 종속성 문제란 두개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 뜻하는데, 이또한 선형구조로 표현하기에는 어려움이 있다. 따라서 이러한 단점들을 개선하기위해 비선형 자료구조가 나오게되었다비선형 자료구조는 크게 트리와 .. 정렬 알고리즘[Quick Sort] Quick sort 란? Quick sort는 최선,평균 시간복잡도가 O(n log n)이고, 최악의 경우에는 O(n^2)인것을 확인할 수 있다.그리고 메모리는 O(n log n)인것을 확인할 수 있다 Quick sort는 이름에서도 나타나듯이 평균적으로 매우 빠른 수행속도를 자랑하는 정렬방법이다. Quick sort도 Merge sort와 같이 분할정복법을 사용한다. 그러나 Merge sort와 달리 리스트를 균등하게 분할할 필요는 없다.Quick sort도 Merge sort와 같이 시간복잡도가 O(n log n)인데, Quick sort가 훨씬 짧은 시간이 걸린다는것을 알 수 있다. 왜그럴까??이는 "참조지역성의 원리"로 설명할 수 있다!Quick sort는 알고리즘 특성상 동일한 배열 내에서 자리.. 정렬 알고리즘[Merge Sort] 정렬알고리즘을 살펴보기전에 먼저 시간복잡도에 대해서 알아볼 필요가 있다시간복잡도에 대한 내용을 정리했었어서 링크만 첨부하도록 하겠다시간복잡도란?간단하게 한줄로 요약해보면시간복잡도란 "입력값과 연산수행시간의 상관관계를 나타내는 척도" 를 말한다즉, "문제를 해결하는데 걸리는 시간과 입력의 합수관계"이다. 시간복잡도는 최악을 기준으로 "빅오 표기법"으로 표시하여 성능을 예측하는데,시간복잡도가 빠른순으로 보면 아래와 같이 나타낼 수 있다O(1) O(log n) O(n) O(n log n) O(n^2)O(1)이 시간복잡도가 가장 좋고(가장 빠르고), O(n^2)이 가장 안좋은것(가장 느림)을 알 수 있다 Merge sort 란?이제 5개의 정렬알고리즘이 있는 표를 보면서 Merge Sort에 대해서 알아.. 이전 1 2 다음
