인프런 커뮤니티 질문&답변
작성한 질문수
3-O 15684 시간복잡도 질문드립니다.
작성
·
14
0
안녕하세요 선생님! 결국 시간초과 문제를 해결했긴 했지만, 시간 복잡도를 어떻게 계산하는게 좋을지 궁금해서 질문드리려고 해요.
시간 초과가 났던 코드
http://boj.kr/8fe9f1e620454720a985b58a993d229a
기본적으로 선생님의 설명대로, 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초 정도가 되는거고요.
그래서 제 질문의 핵심은 다음과 같아요.
시간 초과가 났던 코드, 통과한 코드의 시간 복잡도는 어떻게 계산해야하는가? 계산 결과 어떤 시간 복잡도를 가진다고 봐야하는가?
checkedPlayer를 사용한다고 하더라도 최악의 경우에는 300번 가량을 계산해야하는 것은 마찬가지일 것 같은데, 왜 통과되는것인가?
물론 시간복잡도를 완전 정확히 계산할 수는 없지만, loop 횟수나 재귀함수의 호출횟수로 정량화하여 대략 예상하고 싶은데 이 예상치 조차 세워지지 않아서 혼란스러워 질문드렸어요 ㅜㅡㅜ
답변 1
0
안녕하세요 케이님 ㅎㅎ
만약 movePlayer + isSamePosition 를 사용한다면 제 생각에는 300 + 10 = 310 정도를 생각했고, 이로 인해 최종 시간 복잡도는 13억 5000만(450만 * 대략 300) 으로 생각했어요. 이는 13초 정도로 생각했고요.
-> 네 어느정도 정확합니다. 정확히는
가능한 가로선 위치: H × (N-1) = 30 × 9 = 270개 위치
3개 추가: C(270, 3) = 3,258,555가지
3,258,555 × 300 = 약 10억 번 연산
가 됩니다.
다만 그게 꼭 13초일 수는 없습니다. 환경마다 시간은 다르기 때문에 코테에서 만약 1억 ~ 10억 정도의 시간복잡도가 나오면 틀릴 것 같은데 -> 시도 하는 생각을 가지셔야 합니다.
따라서 시간제한1초라고 제한되어있어도 코테에서는 그정도 범위라면 시도해야 합니다.
1번
시간 초과가 났던 코드, 통과한 코드의 시간 복잡도는 어떻게 계산해야하는가? 계산 결과 어떤 시간 복잡도를 가진다고 봐야하는가?
-> 둘 다 최악의 시간 복잡도는 동일하지만 조기종료 때문에 그렇습니다.
2번
if(playerPosition != i) {
ret = false;
break; //최적화 3: 필수!! 이래야 다 계산 안해도 얼른 체크하고 넘어감
}통과되는 코드는 조기종료조건이 있습니다.
시간초과 되는 코드는 조기종료조건이 있는 것 같지만 결국
movePlayer를 통해 모든 경우의 수를 다 진행한 이후
bool isSamePosition(vector<int> & positions){
bool ret= true;
for(int i = 1; i <= n; i++){
if(positions[i] != i){해당 계산된 position을 통해 종료를 하기 때문에 제대로된 조기종료라고 볼 수 없습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.