Algorithm/일반

다익스트라 알고리즘다익스트라 알고리즘은 그래프 내 특정 정점에서 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다.인공위성 GPS와 같은 다양한 분야에서 많이 사용된다.그래프의 간선에 음수 가중치가 있다면 사용할 수 없지만, 현실에는 일반적으로 음수 가중치가 존재하지 않으므로 다익스트라가 효과적이다.간선 가중치가 음수인 그래프에서는 ~벨만-포드 알고리즘~ 같은 다른 방법을 사용해야 한다.구현하기 (C++)vector dijkstra(int start) { vector dist(n + 1, LLONG_MAX); dist[start] = 0; priority_queue> pq; pq.push({0, start}); while (!pq.empty()) { int cost = -pq.top(..

로그를 사용하면 곱셈을 덧셈으로 변환할 수 있기 때문에 큰 수의 자릿수를 효율적으로 구할 수 있다.그러나 로그를 사용하는 것은 정확한 값이 아닌 자릿수만 구하는 경우에만 유용하다. 로그를 이용한 자릿수 계산수의 자릿수를 구하기 위해서는 그 수가 10의 몇 승에 가까운지를 알아내야 한다.예를 들어 100은 $10^{2}$이므로 3자리 숫자이고, 9999는 $10^{3.X...}$ 이므로 4자리 숫자이다.수 N의 자릿수를 구하는 방법은 다음과 같다.자릿수 =  $ \left \lfloor log10​(N) \right \rfloor+1 $이 원리를 사용하여 곱셈 연산을 로그의 덧셈으로 바꿀 수 있다. 예시백준 12179아래에 쓰여있는 문제를 읽기보다 링크에 들어가 예제와 힌트를 읽는게 문제를 이해하기 훨씬 ..