로그인 유지
2014. KOI 지역본선 문제 및 해법입니다.
고등부 2번 문제의 시간복잡도가 O(n3)인 이유가
각각의 저울에 대해 O(n)으로 답을 구하고 그걸 n번 실행해서 답 출력을 n번이기 때문인가요, 아니면
출력 시간을 무시하고 각 bfs의 시간복잡도가 O(n2)이여서 그런건가요?
네.. 일단 Floyd 알고리즘이 O(n^3) 입니다. n^2 2차원 배열을 다시 n번 처리해야하기 때문이지요...
이때 Floyd는 동적 계획법을 적용합니다.
이 문제의 경우 BFS를 이용해서도 풀 수가 있는데...
그래프를 2차원 인접행렬로 표현한다면 1회의 BFS가 O(n^2)이고 다시 그러한 BFS를 n번 수행해야하므로 역시 O(n^3) 이지요..
고등부 2번 문제의 시간복잡도가 O(n3)인 이유가
각각의 저울에 대해 O(n)으로 답을 구하고 그걸 n번 실행해서 답 출력을 n번이기 때문인가요, 아니면
출력 시간을 무시하고 각 bfs의 시간복잡도가 O(n2)이여서 그런건가요?