f52985   2달 전

확률 전이행렬을 A, 초기 확률 벡터(ICN만 1, 나머진 0)를 v라고 하면 Akv 를 구한 뒤 가장 큰 값을 찾는 방법을 사용했는데요,

A를 직접 k번 곱하면 시간복잡도가 N2k, 제곱 방식을 이용해서 구하면 시간복잡도가 N3logk가 나옵니다.


T가 얼마나 큰지는 모르겠지만, 이 두가지 방법 모두 TLE가 걸리네요 ㅠ

이보다도 더 빠르게 계산하기 위해서는 어떻게 접근하면 좋을지 알려줄 수 있나요?

koosaga   2달 전

TLE라고 하니 시간제한이 조금 빡빡해 보이긴 하는군요. 

다만 오더 뒤에 붙어있는 상수를 생각해보면 KN^2가 더 빠르지 않을까 싶습니다. 

wyldecat   2달 전

문제 잘못 이해하신걸 수도 있어요..!! 모든 여행 경로중.. 가장 확률이 높은 경로의 끝에 존재하는 공항이 뭔지 묻는것 같구만요.. 

댓글을 작성하려면 로그인해야 합니다.