최소 평균 지연 사이클 찾기
자바스크립트 코딩테스트 문제로 min-mean-cycle 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
방향 그래프에서 간선 하나당 평균 지연이 가장 작은 사이클을 찾아보세요.
문제 설명
n개의 서버와 방향 통신 경로 정보 edges가 주어집니다.
각 간선은 [from, to, latency] 형태이며, from 서버에서 to 서버로 이동할 때 latency만큼의 지연이 발생한다는 뜻입니다.
사이클은 한 서버에서 출발해 하나 이상의 간선을 따라 이동한 뒤 다시 같은 서버로 돌아오는 경로입니다. 사이클의 평균 지연은 사이클에 포함된 latency 합 / 사이클 간선 수입니다.
모든 사이클 중 평균 지연이 가장 작은 값을 찾아, 기약분수 문자열 "분자/분모" 형태로 반환하는 minimumAverageLatencyCycle 함수를 작성하세요.
제한사항
1 <= n <= 601 <= edges.length <= 30000 <= from, to < n0 <= latency <= 100000- 그래프에는 사이클이 최소 1개 이상 존재합니다.
- 같은 두 서버 사이에 여러 방향 간선이 있을 수 있습니다.
- 반환값은 최소 평균 지연을 기약분수 문자열로 표현한 값입니다.
예시
- 입력:
n = 4,edges = [[0, 1, 4], [1, 2, 2], [2, 0, 3], [1, 3, 10], [3, 1, 2]]-> 출력:"3/1" - 입력:
n = 3,edges = [[0, 1, 8], [1, 0, 2], [1, 2, 1], [2, 1, 2]]-> 출력:"3/2" - 입력:
n = 4,edges = [[0, 1, 5], [1, 2, 1], [2, 0, 1], [2, 3, 2], [3, 2, 2], [0, 3, 10]]-> 출력:"2/1" - 입력:
n = 5,edges = [[0, 1, 100], [1, 0, 100], [2, 3, 1], [3, 4, 10], [4, 2, 1], [1, 2, 50]]-> 출력:"4/1"
힌트
- 가장 짧은 경로를 찾는 문제처럼 보이지만, 목표는 총합이 아니라 평균입니다.
k개의 간선을 사용해 어떤 정점에 도착하는 최소 비용을 DP로 저장해 보세요.- Karp 알고리즘은
n개 간선까지의 최단 경로 DP만으로 최소 평균 사이클을 계산할 수 있습니다.
해설
단순히 비용 합이 가장 작은 사이클을 고르면 틀릴 수 있습니다. 간선 2개의 합이 10인 사이클보다 간선 3개의 합이 12인 사이클이 평균으로는 더 작을 수 있기 때문입니다.
이 문제는 Karp의 최소 평균 사이클 알고리즘으로 풀 수 있습니다.
dp[k][v]를 k개의 간선을 사용해서 정점 v에 도착하는 최소 비용이라고 둡니다. 모든 정점에서 출발할 수 있으므로 dp[0][v] = 0으로 시작합니다.
그다음 k = 1부터 n까지 모든 간선을 보며 다음 값을 갱신합니다.
dp[k][to] = Math.min(dp[k][to], dp[k - 1][from] + latency)
n개의 간선을 사용해 어떤 정점 v에 도착하는 최단 비용이 있다면, 그 경로 안에는 반드시 사이클이 포함될 수 있습니다. Karp 공식은 정점 v에서 끝나는 경로들을 이용해 그 정점에 관련된 최소 평균 사이클 후보를 계산합니다.
정점 v의 후보 평균은 다음 값입니다.
max over k = 0..n-1 of (dp[n][v] - dp[k][v]) / (n - k)
각 정점마다 이 값을 구하고, 그중 가장 작은 분수가 전체 최소 평균 사이클입니다.
정답을 비교할 때는 소수를 만들지 않는 것이 좋습니다. a / b < c / d는 a * d < c * b로 비교할 수 있습니다. 최종 분수도 최대공약수로 나누면 "분자/분모" 형태의 기약분수로 만들 수 있습니다.
시간 복잡도는 n번의 DP 단계마다 모든 간선을 확인하므로 O(n * edges.length)입니다. 공간 복잡도는 dp 테이블에 O(n^2)이 필요합니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.