기술개발/Algorithm 2021. 2. 8. 16:52

BFS, DFS란? BFS: 자료의 검색, 트리나 그래프를 탐색하는 방법으로써 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS: 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더이상 방문하지 않은 정점이 없을때가지 방문하지 않은 모든 정점들에 대해서도 적용 이 두개가 필요한 이유: 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 탐색이 있는 반면 전부 탐색 해야하는 경우가 있다. 위 두 방법은 이때 모든 경우의 수를 탐색할 때 필요한 알고리즘이다. 💡 DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구합니다. 따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않습니다. B..

기술개발/Algorithm 2021. 2. 5. 17:58

그래프 DFS, BFS에 대해 활용하기 전에 배우는 사전 개념 그래프란? 연결되어 있는 정점과 정점간의 관계를 표시한 자료 구조 💡 비선형 구조는 표현에 초점이 맞춰져 있다고 말씀 드렸는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다. # 출처: 스파르타코딩클럽 예를 들면 SNS의 관계 같은 경우가 그래프 구조일 것 💡 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) # 출처: 스파르타코딩클럽 그래프는 원..

기술개발/Algorithm 2021. 2. 2. 23:05

4주차에 배우는 것 트리, 힙의 개념과 활용법 그래프, BFS, DFS Dynamic Programming의 개념과 필요성 트리 & 힙 트리를 이용하면 계층 구조의 데이터를 쉽게 표현 가능 힙을 이용하면 최댓값, 최솟값을 쉽게 뽑을 수 있음 BFS & DFS BFS(Breadth First Search): 너비 우선 탐색, 모든 것들을 하나씩 방문해야지만 다음 것을 봄 DFS(Depth First Search): 깊이 우선 탐색, 깊이로 내려가며 방문 각 탐색의 장단점 알기 Dynamic Programming 동적 계획법 부분 문제의 해를 통해 전체 문제를 해결하는 방법 DP라고도 하며 알고리즘 문제를 해결하는데 매우 많이 사용되는 편