dldyou

최단 경로 알고리즘(1) - floyd-warshall / dijkstra 이전 글과 달리 이번 글에서는 가중치가 음수인 간선에 대해서도 (가중치가 음수인 cycle이 생기는 그래프) 최단 경로를 구할 수 있는 알고리즘을 소개한다. Bellman Ford 첫 번째로 알아볼 벨만-포드 알고리즘이다. 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이며 간선의 가중치가 음수일 때도 경로를 구할 수 있다는 특징을 가지고 있다. 벨만-포드 는 아래와 같이 굴러간다. 모든 간선을 확인하면서 최단 경로를 갱신한다. 1.을 $V$번 반복한다. 만약 $V$번째에서도 최단 경로를 갱신하려 한다면 음수 사이클이 존재한다는 것이다. $V$번째에서도 갱신 시도가 있을 때 음수 사이클이 존재한다는 것의 이유는 $V..

[BOJ 2485번 가로수] 임의의 간격으로 배열 되어있는 가로수들이 모두 같은 간격이 되도록 가로수를 새로 심어야 하는 최소수를 구하는 문제이다. 1 3 7 13 위치에 있다면 1 3 5 7 9 11 13 과 같이 3그루를 심어주면 된다. 심는 가로수가 최소가 되려면 같은 간격이 되었을 때, 그 간격이 최대여야 한다. 즉, 최대공약수 를 구하는 문제이다. 모든 간격들의 최대공약수가 같은 간격이 되었을 때의 간격이 되는 것이고, 심어야 하는 가로수의 수는 간격들을 최대공약수로 나눈 값에 1을 빼준 값을 계속해서 더해가면 구할 수 있다. 그렇다면 최대공약수는 어떻게 구할까? 수학 시간에 최대공약수를 구하는 방법으로는 크게 서로소가 나올 때까지 공약수로 나누기 소인수 분해 후 공통인 것 중 지수가 작은 것 ..

[BOJ 11689번 GCD(n, k) = 1] 문제는 간단하다. 자연수 $n$이 주어졌을 때, $GCD(n, k)=1$ 을 만족하는 자연수 $1\leq k\leq n$ 의 개수를 구하면 되는 문제이다. 그냥 단순히 $O(N)$ 으로 반복문을 전부 돌려보며 카운팅을 하면 안되냐 할 수 있겠지만 $n$ 의 제한을 보면 $1\leq n\leq 10^{12}$ 이다. 만약 이 방식으로 제출했다면 채점 현황에 시간초과 가 찍혀 있을 것이다. 이 문제를 해결하기 위해서는 오일러 피(Euler's phi) 함수를 알아야 한다. 이 함수는 정의 자체가 $n$이 양의 정수일 때, $\phi{(n)}$은 $n$과 서로소인 1부터 $n$까지의 정수의 개수와 같다. 문제의 정의와 완전히 일치하는 것이다! $\phi{..

[BOJ 11401번 이항 계수 3] $\binom{n}{k}$ % 1,000,000,007 을 구하는 문제이다. 결론적으로 이 문제는 모듈러의 성질, 페르마의 소정리와 분할 정복을 이용해 해결 가능하다. 본문에 나오는 $p$는 소수 (1,000,000,007) 임을 인지하자. 우선 페르마의 소정리는 아래와 같다. $p$가 소수이면, 모든 정수 $a$에 대해 $a^p \equiv a\ (mod\ p)$ $p$가 소수이고 $a$가 $p$의 배수가 아니면, $a^{p-1} \equiv 1\ (mod\ p)$ 그런데 이 정리가 왜 필요하냐를 묻는다면 모듈러 산술의 정의를 보자. 위키 모듈러 산술은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. 그리고 다시 돌아와서 우리가 고등학교 때 ..