Iriton's log

참고 자료 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 위상정렬(Topological sorting) 유향 그래프의 꼭짓점(vertex)들이 변(side)의 방향을 거스르지 않도록 나열하는 것이다. 알고리즘 1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾는다. 2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제한다. 3. 아직 그래프에 꼭짓점이 남아 있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다. 이해를 위해 사진과 함께..

Greedy Algorithm 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최선이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종 해답에 도달하는 알고리즘이다. 참고자료 탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나 ko.wikipedia.org 최적해를 구하기 위한 조건 1. 탐욕스런 선택 조건(greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것 2. 최적 부분 구조 조건(optimal substructure): 최적해가 부분문제에 대해서도 최적해라는 것 ..