Web Development/CS Basic5 [자료구조] 깊이 우선 탐색(DFS, Depth First Search) 이해 및 Python 구현 - CS면접 대비 그래프 G의 한 정점 v 가 주어졌을 때, v에 연결된 모든 정점들을 방문하는 방법으로 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있다. 이 글에서는 깊이우선탐색(DFS)에 대해 정리해보고자 한다. 깊이 우선 탐색(DFS, Depth First Search) [1] Graph의 정의 먼저, 깊이 우선 탐색은 그래프 자료구조를 탐색하기 위한 방법이자 그래프 자료구조의 대표적인 연산이다. 따라서 그래프 자료구조의 정의부터 살펴보자. 다소 딱딱하게 느껴지겠지만, 전공서적에 있는 정의를 그대로 가져와 써보면 아래와 같다. 그래프 G는 두개의 집합 V와 E로 구성되며 다음과 같이 정의할 수 있다. V(G) : 공집합이 아닌 정점(Vertice)의 유한 집합. E(G) : 정점 쌍들의 집합으로, 이러한 쌍을 간.. 2021. 12. 23. [자료구조] AVL Tree(AVL 트리) - CS면접 대비 이번 글에서는 AVL 트리에 관한 내용을 정리해보고자 한다. 이전 글에서 언급했던 것처럼 BST는 공백인 상태에서 이미 정렬된 수를 연속으로 삽입하는 경우 편향(skewed) 문제가 발생한다. 따라서 최악의 경우 자료 탐색에 소요되는 시간이 리스트를 순차 탐색하는 것과 같아진다. 균형 탐색 트리의 일종인 AVL 트리는 이러한 BST의 편향 문제를 해결하기 위해 고안되었으며, 동적 검색을 O(log N) 시간 내에 할 수 있고, 새로운 키를 O(log N) 시간 내에 삽입하거나 삭제할 수 있다. AVL 트리(AVL Tree) [1] AVL 트리의 정의 어떤 이진트리 노드 T의 balance factor(균형인수)를 $BF(t) = h_L - h_R$ 라 할 때, 모든 노드 T에 대해 $BF(t)$= -1,.. 2021. 12. 7. [자료구조] BST(Binary Search Tree) 이진 탐색 트리 - CS면접 대비 이번 글에서는 탐색, 삽입, 삭제 연산에서 탁월한 성능을 보이는 BST(Binary Search Tree)에 관한 내용을 정리해보고자 한다. 1부터 100까지의 수 중 임의의 수 하나를 맞히는 게임을 한다고 가정해보자. 직관적으로 생각했을 때 가운데 값인 50을 가장 먼저 말하고 맞히려는 수가 그보다 큰 경우 75를 작은 경우 25를 외치는 식으로 답을 찾는 게 가장 효율적인 방법일 것이다. 이진 탐색 트리는 이와 유사한 방식으로 자료 탐색이 가능한 이진 트리 자료구조라고 할 수 있다. 이진 탐색 트리(BST, Binary Search Tree) [1] 이진 탐색 트리(BST)의 정의 이진 탐색 트리(BST)는 이진 트리로서 공백일 수 있으며, 만약 공백이 아니라면 다음 성질을 만족한다. 모든 원소는 키.. 2021. 12. 2. [자료구조] Binary Heap(히프)와 Priority Queue(우선순위 큐) - CS면접 대비 이번 글에서는 우선순위 큐(Priority Queue) 구현을 위해 사용되는 이진 히프(Binary Heap)에 관한 내용을 정리해보고자 한다. 일반적인 배열로 우선순위 큐를 구현하는 경우 삽입에 O(N) 정렬에 O(log N) 시간이 소요되는 반면, 히프로 구현하는 경우 enqueue와 dequeue 연산을 O(log N) 시간에 가능하게 해준다. 이진 히프(Binary Heap) [1] 최대/최소 히프의 정의 최대 히프(max heap)는 최대 트리(max tree)*이면서 완전 이진 트리(complete binary tree)이다. 최소 히프(min heap)는 최소 트리(min tree)*이면서 완전 이진 트리(complete binary tree)이다. * 최대(최소) 트리 : 각 노드의 키 값.. 2021. 11. 30. [자료구조] Binary Tree(이진 트리) - CS면접 대비 이번 글에서는 컴퓨터 프로그래밍에서 자주 사용되는 자료구조 중 하나인 이진 트리에 관한 내용을 정리해보고자 한다. 1. 이진 트리의 정의 및 성질 먼저, 이진 트리(binary tree)는 공백이거나 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리라고 하는 2개의 분리된 이진 트리로 구성된 노드의 유한 집합이다. 이진 트리와 일반적인 트리의 주요한 차이점은 다음과 같다. 일반 트리의 경우 0개의 노드를 가질 수 없으나, 공백 이진 트리는 존재함 일반 트리는 자식의 순서를 구분하지 않으나, 이진 트리는 왼쪽 자식과 오른쪽 자식을 구별함 또한, 이진 트리는 노드의 수와 관련하여 다음과 같은 성질을 갖는다. 레벨 i 에서의 최대 노드 수는 2^(i -1) → 예) 레벨 3에서 최대 노드의 수는 4개 깊이.. 2021. 11. 16. 이전 1 다음 반응형
