시간 복잡도 질문

안녕하세요 큰돌님

게임 문제를 풀다 시간초과가 나서 질문드립니다.

해당 문제는 50 * 50 배열에 4방향의 경우의 수를 고려해야하니 4 ^ 50의 시간복잡도가 걸릴텐데

최악의 경우 배열의 값이 전부 1이여야할거라고 생각했습니다.

그런데 이때는 순환하는 경우여서 앞서 계산한 시간복잡도보다 훨씬 일찍종료될거라고 판단하였는데요

제가 시간복잡도 계산을 정확하게 한것일까요?

제 코드에서 시간초과가 발생하는 케이스는 어떤게 있을까요?

dp가 너무 어렵네요...ㅠㅜ

친절한 답변 항상 너무 감사드립니다!

안녕하세요 sol님 ㅎㅎ

이문제지문을 볼까요?

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

이걸기반으로 사실 이 sol님이 질문하신 "시간이 많이 걸리는 예제"를 찾기란 좀 힘이 듭니다.

최악의 경우 배열의 값이 전부 1이여야할거라고 생각했습니다.

그런데 이때는 순환하는 경우여서 앞서 계산한 시간복잡도보다 훨씬 일찍종료될거라고 판단하였는데요

>> 네 맞습니다.

예를 들어

1111

이렇게 1로만 주어진다라고 했을 때 어차피 무한루프를 먼저 찾으면 그대로 종료기 때문에 빠를 것도 같고 그렇기 때문이죠.

그냥 어림잡아서 계산하는게 좋습니다. 말씀하신대로 4^50이 맞습니다. 다만, 실제로 그러한 경우의수를 확인해보면 더 작아질 수 있겠죠.

dp가 너무 어렵네요...ㅠㅜ

>> 이렇게 생각하면 쉽습니다. 완탐으로 해보자 >> 문제 최대범위를 보니까 시간복잡도 초과할 거 같은데?? >> 이거 배열에 담을 수 있을까? >> dp

이런식으로 하시면 됩니다. 간단하게 생각하세요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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