늘 겸손하게

1. 그리디 알고리즘 현 상황에서 최적의 선택지를 선택하는 알고리즘. 단, 현 상황에서 최적의 선택이 전체 상황에서는 최적의 선택이 아닐 수 있다. 2. 완전탐색 ( Exhaustive Search, Brute Force ) 가능한 모든 경우의 수를 일일히 탐색하는 방법. 무식하게 가능한 경우를 다 찾아보는 방식으로 Brute Force 알고리즘이라고도 불린다. 구현은 쉬우나 효율적인 알고리즘이라고 하기는 어렵다. 3. BFS Breadth-First Search의 약자로, 너비 우선 탐색이라 불린다. 그래프의 시작 노드에 인접한 노드부터 탐색하는 알고리즘으로 노드를 넓게 탐색한다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다. 4. DFS Depth-First..

우리가 흔히 아는 큐는 데이터가 rear에서 삽입되고 front에서 나가는(삭제) 선입선출(first-in first out) 구조의 자료구조입니다. 그렇다면 우선순위 큐(Priority Queue)는 무엇일까요? 우선순위 큐는 큐와 비슷하지만 다릅니다. 우선순위 큐의 모든 원소는 우선 순위가 있어 원소가 큐에서 제거되는 순서는 우선순위에 따라 결정됩니다. 보통 우선순위가 높은 원소가 가장 먼저 제거 대상이 됩니다. 그러므로 우선 순위 큐 내부의 모든 원소들은 오름차순, 혹은 내림차순으로 정렬된 채로 저장됩니다. 우선순위 큐를 구현하기 위해 다음과 같은 자료 구조를 이용할 수 있습니다. 배열 연결 리스트 (Linked List) 힙 ( Heap data structure ) 이진 탐색 트리 ( Binar..

자료구조 heap 은 완전 이진트리를 기반으로 하는 자료 구조입니다. 많은 값들 중에서 최소 혹은 최대 값을 빠르게 찾는것이 가능한 자료 구조입니다. 일반적으로 힙은 두 가지 타입이 존재합니다. 1. Max-Heap Max-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 커야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다. 2. Min-Heap Min-Heap의 루트 노드 값은 모든 자식 노드의 노드 값보다 작아야 합니다. 이러한 속성은 모든 하위 트리도 만족해야 합니다. 왜 힙을 쓰나요? 최대값 및 최솟값을 찾아내는 작업의 시간복잡도는 O(logN)으로 매우 빠릅니다. 새로운 원소를 저장하고 정렬하는데의 시간복잡도 또한 O(logN)으로 매우 빠릅니다. 그러므로 많은 데이터를 빠르게..

안녕하세요 besforyou 입니다 이번 글에서는 그래프의 DFS에 대해 소개하겠습니다. 출처 : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/ Depth First Search or DFS for a Graph - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geek..