DailyStudyNote

DFS(Depth First Search, 깊이 우선 탐색) BFS(Breadth First Search, 너비 우선 탐색) DFS(Depth First Search, 깊이 우선 탐색) 란 루트 노드 혹은 다른 임의의 노드에서 다음 분기(Branch)로 넘어가 기전에 해당 분기를 완벽하게 탐색하는 방법이며 스택(Stack) 혹은 재귀함수(Recursion)로 구현된다. 코드(Python) """ 1 / | \ 2 5 9 | /\ | 3 6 8 10 / | 4 7 """ graph = { 1: [2,5,9], 2: [3], 3: [4], 4: [], 5: [6,8], 6: [7], 7: [], 8: [], 9: [10], 10: [] } def recursive_dfs(v, visited = []): vi..

최소 공통 조상(Lowest Common Ancestor, LCA) 최소 공통 조상(Lowest Common Ancestor, LCA) 란? 최소 공통 조상(LCA) 란 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘 이다. 즉 두 정점이 만나는 최초 부모 정점을 찾는 것을 의미한다. 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘 모든 노드에 대한 깊이(Depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이(Depth)가 동일 하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 최소 공통 조상을 찾을 두 노드를 확인한다. LCA 알고리즘 풀이 이해 1. 각 노드의 "D..

계수 정렬(Counting Sort) 계수 정렬(Counting Sort) 계수 정렬(Counting Sort)란 숫자들간 비교를 하지 않고 정렬하는 알고리즘이다. 각 숫자가 몇개 있는지 개수를 세어 저장한 후에 정렬하는 방식이다. 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있는데 조건은 다음과 같다. ▶ 데이터의 크기 범위가 제한된 경우 → 0~100 까지의 점수를 정렬하는 경우가 이 조건에 해당하는 예가 될 수 있다. ▶ 데이터가 양의 정수인 경우 → 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못한다. ▶ 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우 → 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아진다...

힙(Heaps) 힙(Heap)이란? 이진 트리의 한 종류 (이진 힙-binary heap)이다. 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙(max heap) 최소 힙(min heap) 2. 완전 이진 트리 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조 로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다. 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 최대 힙(max heap)의 추상적 자료 구조 재귀적으로도 정의된다. 즉, 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙 이다. 연산의 정의 __init__(): 빈..

이진 탐색 트리(BST, Binary Search Tree) 이진 탐색 트리 정의 이진탐색 트리란 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모든 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리이며, 각 노드는 중복된 키를 허용하지 않는다. 연산의 정의 ▶ insert(key, data) : 트리에 주어진 데이터 원소를 추가한다. ▶ remove(key) : 특정 원소를 트리로 부터 삭제한다. ▶ lookup(key) : 특정 원소를 검색한다. ▶ inorder(): 키의 순서대로 데이터 원소를 나열한다. ▶ min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색..

'어서와! 자료구조와 알고리즘은 처음이지?' 이진트리의 넓이 우선 순회(BFS; Breadth First Traversal) 원칙 ✔ 수준(level)이 낮은 노드를 우선으로 방문 ✔ 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문 ✔ 왼쪽 자식 노드를 오른 쪽 자식 노드보다 먼저 방문 ✔ 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록(방문한 노드의 자식 노드 기록) ✔ 큐(Queue) 이용 → 순회 결과: A - B - C - D - E - F - G - H - J 알고리즘 설계 1. traversal 빈 리스트 초기화 2. 빈 트리가 아니면(root != None) root node를 큐에 추가(enqueue) 3. q 가 비어있지 않는 동안, 3.1 node ← q..

'어서와! 자료구조와 알고리즘은 처음이지?' 이진 트리(Binary Tree) 연산의 정의 1. size() - 현재 트리에 포함되어 있는 노드의 수를 구한다. 2. depth() - 현재 트리의 깊이 (또는 높이, height)를 구한다. 3. 순회(traversal) 이진 트리의 구현 - 노드(Node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None 이진 트리의 구현 - 트리(Tree) class BinaryTree: # r 은 node def __init__(self, r): self.root = r 이진 트리의 구현 - size() 재귀적인 방법으로 쉽게 구할 수 있다. class N..

'어서와! 자료구조와 알고리즘은 처음이지?' 트리(Tree) 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조 ✔ 부모의 부모(의 부모의...) - 조상(ancestor) ✔ 자식의 자식(의 자식의...) - 후손(descendant) 트리의 높이(Height) 트리의 높이(height) = 최대수준(level) + 1 트리의 높이는 깊이(depth)라고도 한다. 부분트리(서브트리, SubTree) 노드의 차수(Degree) = 자식(서브트리)의 수 degree 가 0인 노드는 leaf 노드이다. 이진트리(Binary Tree) 모든 노드의 차수가 2 이하인 트리 이진트리는 재귀적으로 정의할 수 있다. ✔ 빈 트리(Empty Tree)이거나 ✔ 루트노드 + 왼쪽 서브트리..