[알고리즘 자습]그래프(Graph) - 3. 위상 정렬, 파이썬(Python3)
앞선 게시물들에서, 0. 그래프 자료구조 1. BFS, 너비우선 탐색 2. DFS, 깊이우선 탐색 이 3가지에 대한 정의와 활용을 예제를 통해 알아보면서 정리했다. 이 정도 수준의 알고리즘을 알았다면, 우리는 그래프에 관해서는 어느정도 잘 이해하고 있다고 봐도 좋다. 그렇기 때문에, 그래프 알고리즘 중 하나인 위상 정렬에 대해 아주 쉽게 알아볼 수 있다. 알아서 나쁠거 하나도 없고, 위상 정렬을 이용해 문제를 풀면 BFS, DFS보다 쉽게 풀리는 문제도 있다. 따라서, 우리는 충분히 위상 정렬에 대해 알아볼 필요가 있다. 위상 정렬 위상 정렬에 대해 설명하기 전에, 단어를 먼저 이해하고 시작하는 것이 좋을 것 같다. 우리는 살면서 알게 모르게 위상이라는 단어를 많이 써왔다. 누구누구의 사회적 위상이 어떻..
[알고리즘 자습]그래프(Graph) - 2. DFS(깊이 우선 탐색)의 정의와 활용, 예제, 파이썬(Python3)
2020/03/04 - [공부/알고리즘] - [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) 코딩테스트를 준비하는 사람이든 아니든, 프로그래밍에 발을 들여본 적이 있는 사람들은 무조건 들어봤을 것이다. 너비 우선 탐색, BFS이다. 코딩테스트 단골 문제이기도 하고, 백준 및 프로그래머스에서도 굉장히.. sexy-developer.tistory.com 위의 링크를 걸어놓은 이전 게시물에서, 그래프 순회 알고리즘을 배워야 하는 이유, 그리고 최단 경로 등의 문제에 주로 쓰이는 BFS에 대해 알아보고, 예제를 풀어봄으로써 그 원리를 익..
[알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3)
코딩테스트를 준비하는 사람이든 아니든, 프로그래밍에 발을 들여본 적이 있는 사람들은 무조건 들어봤을 것이다. 너비 우선 탐색, BFS이다. 코딩테스트 단골 문제이기도 하고, 백준 및 프로그래머스에서도 굉장히 많은 문제가 준비되어 있다. 문제가 많다는 것인 즉슨 연습할 기회가 충분히 주어져 있다는 뜻이다. 근데 나는 옛날에 배웠던 BFS가 정확히 기억이 나지를 않아서, 쉬운 문제도 풀지 못했다. 그래서, 한번 정리를 하고자 한다. 혹시, 이 글을 읽는 사람이 BFS가 뭔지는 들어는 봤고, 너비우선 탐색이라 한 노드에 연결되어있는 다른 노드들을 방문한 다음에 이러쿵저러쿵... 이렇게까지 설명은 할 수 있지만, 당장 구현을 못하겠다라는 생각이 든다면 나와 같이 이글을 쭉 읽어보자. 그래프 순회 알고리즘 전 게..
