개발 공부 블로그

위상 정렬( Topology Sort) 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘 예시 → 선수 과목 선후관계가 정의된 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 이용할 수 있다. 정렬 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. (비순환 유향 그래프여야 한다)

1. 완전 탐색 반복 또는 재귀를 이용한 완전 탐색 2. 조합적 문제 해결 순열/조합/부분비합 3. 백트래킹 - 가지치기 4. 메모이제이션 -동일 작업 반복 수행 시, 직접 자료구조에 그 결과를 저장하고, 재사용 5. 탐욕 알고리즘 - [원문제의 최적해 탐욕적 선택+ 하위 문제의 최적회]임을 증명 6. 서로소 집합 - 유니온 파인드 7. 비선형 자료구조 탐색 - DFS, BFS 8. 그래프 관련 알고리즘 - 최소 신장 트리: Prim, Kruskal- 최단 경로 알고리즘: 다익스트라 9. 분할 정복 알고리즘