공부 정리

* 에라토스테네스의 체 고대 그리스의 수학자인 에라토스테네스가 발견한 소수(1과 자기자신으로만 나누어지는 수)를 찾는 방법이다. 내용은 다음과 같다. - 알고리즘 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 5. 자기 자신을 제외한 3의 배수를 모두 지운다. 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 7. 자기 자신을 제외한 5의 배수를 모두 지운다. 8. 위 과정을 계속 반복하면 원하는 구간의 모든 소수가 남는다. 이 때, 100까지의 소수를 구할 때 어디까지 위의 방법을 반복해야 할까? 예를 들어서 17의 배..

* 위상 정렬이란? 위상 정렬(topological sorting/ topological ordering)은 유향 그래프의 꼭지점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 하려면 반드시 그래프가 유향 비사이클 그래프(DAG : Directed Acyclic Graph)여야 한다. 그렇다면 만약 트리는 위상정렬을 할 수 있을까? 정답은 할 수 있다이다. 그러나 DAG가 트리라고 할 수 있는가? 정답은 아니다이다. 그러니까 DAG의 부분집합에 트리가 있는 것이라고 생각하면 된다. * Pseudocode L ← 정렬된 요소를 담은 빈 리스트 S ← 진입차수가 없는 노드들 while S is not empty do remove a node n from S add n to L for e..