p.386 Chapter 17 Q38 정확한 순위 Time complexity 질문

[hy2850]

안녕하세요.

이 문제 해설을 보니까, "노드 개수 N 이 최대 500이니까, O(N^3) 복잡도를 가지는 플로이드-워셜 알고리즘을 써서 풀 수 있다" 라고 되어있습니다. 근데, N^3은 최대 1억2500만 정도가 되고, 파이썬의 속도가 1초에 약 2,000만번 연산이니까 (p.108에서 언급), 문제 제한시간인 1초 내로는 O(N^3) 알고리즘으로는 풀기 힘들지 않나요?

속도를 넉넉히 잡아서 C++처럼 1초에 1억번 연산이라고 쳐줘도, 각종 오버헤드를 고려하면 플로이드-워셜로는 풀기 힘들 것 같은데요. 어떻게 생각하시나요?

[ndb796]

안녕하세요, @hy2850 님!

좋은 질문 감사합니다.

정확한 순위 문제에서는 노드의 개수 N이 최대 500이 될 수 있습니다. 그래서 말씀하신 대로 단순히 1억 2,500만 정도의 연산 횟수를 고려할 수 있습니다.

다만 교재에서는 보수적으로 "1초에 2,000만 번 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다."라고 소개하고 있지만, 실전에서 플로이드 워셜 유형의 문제가 출제될 때는 대개 PyPy3를 사용할 수 있도록 하거나 시간 제한을 5초가량으로 늘리는 방식으로 파이썬 사용자를 고려해주는 경우가 많습니다.

실제로 이번 2021 K사 공채 코딩 테스트에서 플로이드 워셜을 활용해 쉽게 풀 수 있는 문제가 출제되었는데요. (책의 9장 미래 도시 문제와 접근 방법 및 아이디어가 사실상 동일한 문제였습니다.) K사의 경우 파이썬 사용자를 고려하기 때문에, 시간 제한이 넉넉하여 파이썬으로 작성한 코드로 통과할 수 있던 사례였습니다.

감사합니다. 나동빈 드림