본문 바로가기

전체 글186

[자료구조] 이진힙[힙](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.
[자료구조] 이진트리 (Binary Tree) 이진트리(Binary Tree)란?이진트리(Binary Tree)란 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질때 이진트리라고 한다.최대 2개의 자식노드를 가질때이기 때문에 자식이 없을수도 있고, 한개만 있을수도 있다  이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현한다.그래서 같은 루트에 같은 자식노드 하나를 가지고있어도, 자식노드의 위치가 왼쪽과 오른쪽이 다르다면 이 두 트리는 서로 다른 트리가된다.아래 그림은 A라는 같은 루트노드를 가지고있지만, 자식노드의 위치가 왼쪽,오른쪽 다르기때문에 두개의 트리는 별개의 트리(서로 다른 트리)가 된다.       이진트리(Binary Tree)의 종류1. 정 이진트리(Full Binary Tree / Strict Binary Tree) 이.. 2024. 7. 26.
[자료구조] 트리(Tree)란? 배열, 리스트, 스택과 큐, 해시테이블과 같은 자료구조는 데이터의 이전 데이터나 다음 데이터의 순서가 존재하는 선형 자료구조에 해당한다.이러한 구조는 특정 데이터를 검색할때 순서대로 데이터를 찾아야하는 문제점과,데이터를 저장하기위해 일정한 공간을 미리 할당해야하는 등의 제한적인 구조를 가지고있어 복잡한 문제를 해결하는데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 계층적 문제란 계층적 속성을 갖는 자료는 선형구조로 표현하기가 어렵다는 것을 뜻한다순환 종속성 문제란 두개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 뜻하는데, 이또한 선형구조로 표현하기에는 어려움이 있다. 따라서 이러한 단점들을 개선하기위해 비선형 자료구조가 나오게되었다비선형 자료구조는 크게 트리와 .. 2024. 7. 26.

티스토리툴바