인프런 커뮤니티 질문&답변

안녕하세요 선생님! 결국 시간초과 문제를 해결했긴 했지만, 시간 복잡도를 어떻게 계산하는게 좋을지 궁금해서 질문드리려고 해요.

• 시간 초과가 났던 코드
  http://boj.kr/8fe9f1e620454720a985b58a993d229a

• 통과 됐던 코드
  http://boj.kr/864f7c65db52442bada271fe193a2ec3

기본적으로 선생님의 설명대로, 300C3 == 대략 4,500,000(450만) 은 반드시 든다고 가정했어요.

이때, 두 코드의 차이점은 다음과 같아요.

• movePlayer + isSamePosition 함수를 각기 사용하는가

• checkedPlayer 함수 하나를 사용하는가

만약 movePlayer + isSamePosition 를 사용한다면 제 생각에는 300 + 10 = 310 정도를 생각했고, 이로 인해 최종 시간 복잡도는 13억 5000만(450만 * 대략 300) 으로 생각했어요. 이는 13초 정도로 생각했고요.

하지만 checkedPlayer 함수를 사용하는 순간, 중간에 break 할 수 있어 300까지 계산할 일은 거의 없겠지만.. 정말 최악의 최악일 경우 n-1 player의 맨 h 행까지 계산해야할 수도 있을거라고 생각했어요. 그럼 결국 300까지 계산하게 되는거고, 이 또한 시간 복잡도가 13초 정도가 되는거고요.

그래서 제 질문의 핵심은 다음과 같아요.

1. 시간 초과가 났던 코드, 통과한 코드의 시간 복잡도는 어떻게 계산해야하는가? 계산 결과 어떤 시간 복잡도를 가진다고 봐야하는가?

2. checkedPlayer를 사용한다고 하더라도 최악의 경우에는 300번 가량을 계산해야하는 것은 마찬가지일 것 같은데, 왜 통과되는것인가?

물론 시간복잡도를 완전 정확히 계산할 수는 없지만, loop 횟수나 재귀함수의 호출횟수로 정량화하여 대략 예상하고 싶은데 이 예상치 조차 세워지지 않아서 혼란스러워 질문드렸어요 ㅜㅡㅜ