728x90 탐색알고리즘4 강한 결합 요소(Strongly Connected Component) ※다음 포스팅은 나동빈님 블로그를 보고 포스팅한 것입니다. https://blog.naver.com/ndb796/221236952158 26. 강한 결합 요소(Strongly Connected Component) 강한 결합 요소란 그래프 안에서 '강하게 결합된 정점 집합'을 의미합니다. 서로 긴밀하게 연결되어 있다고... blog.naver.com 강한 결합 요소란 그래프 안에서 '강하게 결합된 노드의 정점 집합' 라는 의미 입니다. 서로 강하게 연결되어 있다고 하여 강한 결합 요소입니다. 이는 SCC 알고리즘이라고 불리는 데요. SCC 는 '같은 SCC 에서 선택한 두 정점은 서로에게 도달이 가능하다' 는 특징이 있습니다. 다음 그래프에서 SCC 를 구하면 다음과 같습니다. 집합에 속하는 정점끼리 서로.. 2020. 6. 13. 플로이드와샬 알고리즘(FloydWarShall) 안녕하세요. 옆집컴공생입니다. 오늘은 플로이드와샬 알고리즘(Floydwarshall) 에 대해 알아볼게요. 저번에 포스팅했던 다익스트라 알고리즘과 비슷한 부분이 굉장히 많은 알고리즘입니다. 혹시 다익스트라가 뭔지 모르시는 분은 아래 포스팅을 확인해주세요. https://com24everyday.tistory.com/137 다익스트라 알고리즘(Dijkstra Algorithm) 안녕하세요. 옆집 컴공생입니다. 오늘은 다익스트라 알고리즘을 배워볼거예요. 다익스트라(Dijkstra Algorith)은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘입니다. com24everyday.tistory.com 다익스트라 알고리즘은 '한 정점에서부터 다른 모든 노드를 최소 비용으로.. 2020. 6. 11. 깊이 우선 탐색(DFS) ※이 글은 나동빈님의 유튜브를 보고 복습용으로 포스팅됩니다※ https://blog.naver.com/ndb796/221230945092 16. 깊이 우선 탐색(DFS) 깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 ... blog.naver.com 깊이 우선 탐색(Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘입니다. 가까운게 우선이었던 너비 우선 탐색과는 다른 느낌이죠. 이 깊이라는 게 좀 애매하다고 느끼실 분도 계실 거 같습니다. 그냥 가장 아래까지 내려갔다 돌아오는 알고리즘이라고 생각하시면 될거 같아요. BFS와 동일하게 DFS는 맹목적으로 각 노드를 탐색할 때 주로 이용.. 2020. 6. 3. 너비 우선 탐색(BFS) ※이 포스팅은 나동빈님 강의를 듣고 정리한 것 입니다.※ https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16 너비 우선 탐색 (Breath-First-Search, BFS)입니다. 너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘입니다. 특히나 '맹목적인 탐색' 을 하고자 할때 사용하는 탐색 기법이고 미로찾기와 같은 곳에서 많이 활용이 됩니다. 이는 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용됩니다. 큐를 이용합니다. 'BFS는 가까운 거를 먼저 탐색한다'라는 개념입니다. 큐와 그래프가 준비가 되었습니다. BFS는 맨 처음에 시작.. 2020. 6. 3. 이전 1 다음 728x90
