알고리즘
-
위상정렬 Topological SortAlgorithm/Theory 2020. 6. 7. 13:21
목표 - 위상정렬 (Topological Sort)를 이해하고 설명할 수 있다. - 위상정렬의 조건을 알고 언제 어떻게 사용하는지 이해한다. 위상정렬? \ 특정한 순서를 가진 조건에서 사용한다. DAG(방향성 비순환 그래프) 에서만 사용할 수 있다. \ "위상" 이라는 사전적 정의에서 알 수 있듯이, 위상정렬이란 어떤 순서를 가지고 있는 경우에 사용할 수 있는 정렬 방법입니다. 게임을 하는데 어떤 스킬을 익히기 위해 반드시 먼저 배워야 하는 사전스킬이 있죠? 이런 식으로 어떤 순서를 가지고 있을 때 사용합니다. 이 말인즉 위상정렬은 방향성을 가지고 있어야 합니다. 그리고 이 의미를 잘 생각해보면 사이클이 생기면 안된다는 것을 알 수 있습니다. A -> B -> C 순서를 가지고 있어야 하는데 여기서 C ..
-
Algorithm) BOJ) 백준 1676 - 팩토리얼 0의 개수Algorithm/BOJ 2019. 5. 17. 16:06
문제보러가기 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼을 구하는 방법은 다들 아실텐데요, 문제는 수가 조금만 커져도 그 값이 어마어마하게 커진다는게 문제에요ㅠㅠ / 뒤에 숫자 0이 붙는다는 건 무슨 의미일까요? / 2라는 숫자를 20으로 만들려면 어떻게 해야할까를 생각하면 이해가 쉬울 것 같습니다. 한 마디로 10이 곱해진다는 뜻이죠 ! 즉 우리는 팩토리얼에서 10이 몇 개가 있는지를 확인하면 된답니다! 10 = 5 x 2 이므로 5의 개수와 2의 개수를 확인하면 되겠죠? / 그렇다면 2의 개수와 5의 개수는 어떻게 확인할까요? / 먼저 15! 을 한번 예로 들어볼게요, 1 x 2..