728x90 그래프알고리즘4 위상정렬(Topology Sort) 위상 정렬(Topology Sort) 는 순서가 정해져있는 작업을 차례로 수행할 때 순서를 결정해주기 위해 사용되는 알고리즘입니다. 예시를 바로 볼까요. 다음과 같이 할 일 루틴이 있다고 합시다. 청소나 블로그 작성은 어느것을 먼저 수행하든지 상관이 없지만 점심은 강의를 복습하고 나서야 할 수 있습니다. 이처럼 한 단계를 수행하기 전에 해야하는, 즉 화살표의 개수(조건)를 '진입 차수' 라고 합니다. 이러한 조건들에 부합하는 일직선이 순서를 찾는것이 위상정렬입니다. 출근 -> 청소 -> 블로그 작성 -> 강의듣기 -> 강의 복습 -> 점심먹기 위와 같이 정렬을 수행할 수 있습니다. 그리고 다양한 답이 존재합니다. 그렇기 때문에 더욱 매력적인 알고리즘이라고 할 수 있습니다. 또 위상정렬을 DAG(Direc.. 2020. 6. 12. 플로이드와샬 알고리즘(FloydWarShall) 안녕하세요. 옆집컴공생입니다. 오늘은 플로이드와샬 알고리즘(Floydwarshall) 에 대해 알아볼게요. 저번에 포스팅했던 다익스트라 알고리즘과 비슷한 부분이 굉장히 많은 알고리즘입니다. 혹시 다익스트라가 뭔지 모르시는 분은 아래 포스팅을 확인해주세요. https://com24everyday.tistory.com/137 다익스트라 알고리즘(Dijkstra Algorithm) 안녕하세요. 옆집 컴공생입니다. 오늘은 다익스트라 알고리즘을 배워볼거예요. 다익스트라(Dijkstra Algorith)은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘입니다. com24everyday.tistory.com 다익스트라 알고리즘은 '한 정점에서부터 다른 모든 노드를 최소 비용으로.. 2020. 6. 11. 이진 트리 구현과 순회(Traversal) ※이 글은 나동빈님 강의를 보고 복습용으로 작성하는 글입니다. https://blog.naver.com/ndb796/221233560789 19. 이진 트리의 구현과 순회(Traversal) 방식 기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리(Binary Tree)입니다. 이진 트리는 트리 자... blog.naver.com 이진 트리(Binary Tree)는 굉장히 많이 사용되는 비선형 자료구조입니다. 비선형이란 선, 즉 일렬로 구현되지 않았다는 뜻입니다. 또 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도 증진을 위해 사용되는 구조입니다. 이전 Heap Sort 에서도 다뤄 본 적이 있었습니다. https://com24everyday.tistory.com/101 힙정렬 저번주에.. 2020. 6. 5. Union-Find(합집합찾기) Union-Find는 대표적인 그래프 알고리즘 입니다. 바로 '합집합 찾기'라는 이름의 알고리즘인데요. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리기도 합니다. 여러 개의 노드가 존재할때 두 노드가 같은 집합 안에 속했는지, 즉 연결이 되어있는지를 판별하는 알고리즘 입니다. 다음과 같은 노드셋이 있습니다. 모든 노드가 연결되어 있지 않고 자기 자신만을 집합의 원소로 가지고 있는 때입니다. 모든 값이 자기 자신을 가리키도록 만드는 겁니다. 아래 표에선 첫번째 행은 '노드 번호'를 의미하고 두번째는 '부모 노드 번호'를 의미합니다. 즉, 자기 자신이 어떤 부모에게 포함되어 있는지를 의미합니다. 어차피 한 노드에만 연결되어 있으면 다른 노드에도 연결되어져 있게 되는거니깐요. 여기서 부모노드는 값.. 2020. 6. 4. 이전 1 다음 728x90
