힙 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 즉, 힙을 이해하기 위해서는 트리에 대한 사전 지식이 필요하다. 힙은 왜 사용할까? 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림, 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림, 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 힙 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap)로 분류할 수 있다. 즉, 힙은 ..

트리 트리는 트리 모양으로 만든 자료구조이다. 즉, 모양은 트리구조지만, 내부적으로는 리스트이다. 자세히 다루자면 아래와 같다. 트리는 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다. 그렇다면 트리는 어디서 많이 사용되는가? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 용어 트리를 공부하다보면 용어가 많이 나와 이를 정리해 보았다. Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node..

자료구조 공부 목표 자료구조 개념 및 설명 stack, queue, tree, graph 개념 이해 기본 개념과 구조를 파악 및 목적을 이해 상황에 맞는 자료구조를 떠올릴 수 있다. tree 및 graph 탐색 기법 이해 BST 이해 BFS, DFS 개념 이해 자료구조란? 쉽게 말해 데이터들의 구조이다. 수많은 데이터들을 어떻게 저장하고, 어떻게 위치를 새우냐에 따라 사용하는 방법이 다를 것이다. 데이터 : 문자, 숫자, 그림, 영상 등 다양한 정보의 집합 자료구조 종류 자료구조 단순구조 정수 / 실수 문자 / 문자열 2진수 선형구조 (선 모양으로 생긴 자료 구조) 리스트(배열) 연결 리스트 단순 / 이중 / 원형 덱 / 스텍 / 큐 비선형구조 트리 일반 트리 / 이진 트리 그래프 방향 그래프 / 무방향..

비선형구조 1. 트리 (Tree) 사이클(순환)이 없는 연결된 그래프입니다. 트리를 구성하는 노드 간에는 단순 경로가 존재하는 특징이 있습니다. 여기서 단순 경로란 지나왔던 접점을 다시 지나지 않는 경로 입니다. 우리가 주로 쓰는 간단한 예시로는 폴더 구조가 있습니다. 트리는 일반트리와 이진트리가 있습니다. 차이로는 이진트리는 2개 이상의 노드가 존재하지 않는 구조라 생각하면 쉽습니다. ( 이진트리 - 각 노드가 최대 두개의 자식을 갖는 트리 ) 트리의 큰 특징으로는 1. 방향성 있음. 2. 각 노드는 어떤 자료형으로도 표현이 가능 3. 사이클이 존재 할 수 없다.(하나의 연결 그래프) 4. 트리는 이진 트리, 이진 탐색 트리, 균형트리 등이 있습니다. 2. 그래프 (Graph) 그래프란? 노드와 노드를..