Data Analysis & Merketing

BFS와 DFS는 그래프를 탐색하는 방법입니다. 그래프란 정점(Node)와 그 정점을 연결하는 간선(Edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. 1. DFS(Depth_First_Search) : 깊이 우선 탐색 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 조금 더 간단함 3. 검색 속도는 너비 우선 탐색(BFS)에 비해 느림 2. BFS(Breadth_First_Search) : 너비 우선 탐색 임의의 노드에서 시작해서 인접한..

1. 백트래킹이란? 백트레킹(BackTracking) 알고리즘 퇴각검색이라고도 불리며 이는 한정조건을 가진 문제를 풀려는 전략이다. 어떤 문제를 푸는데 있어서 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다. 하지만 백트래킹에서는 한정조건에서의 모든 경우의 수를 시도하는 것이기 때문에 상당한 경우의 수들이 배제되어 단순 다중 for문 보다 빠르게 해결되는 경우가 많다. 2. 구현 방법 BFS나 DFS와 함께 구현한다. 모든 경우의 수에서 한정조건을 만족하는 경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS와 DFS 모두 구현 가능하다. 하지만 백트래킹의 특성에서 한정조건에 부합하지 않다면(Node가 유망하지 않다면) 이전 수행(이전 Node)으로 돌아와야 하기 때문에 BFS보다는 DFS의 구현이 더..

힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 최소힙과 최대힙이 있으며 최소힙은 부모노드가 자식노드보다 작은 경우이고 최대힙은 부모노드가 자식노드보다 큰 경우이다. 대소관계는 부모와 자식 간에만 성립되고 형제노드 사이에는 대소관계가 성립되지 않는다. 모든 부모노드는 자식노드보다 값이 작거나 큰 이진트리(binary tree)구조이다. 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2)보다 작거나 같은 최소힙의 형태로 정렬된다. 파이썬 heapq은 heapq(priority queue) 알고리즘을 제공한다. 기본적으로 최소힙의 형태로 정렬되며 import heapq 하여 사용할 수 있다. [heapq의 함수들] - heapq...