15684번 - 사다리 조작
N이 10이고 H가 30이라 가정할 때
dfs경우의 수만 270C3 하면 350만번 정도 나옵니다.
그리고 각 경우의 수마다 사다리를 타서 모두 자기 자신과 같은 숫자로 연결되는 지확인하는데 각 사다리마다 30번씩 10개해서 300번
350만 x 300 = 10억이 나옵니다.
사디리 타다가 일치하지 않는 거 나왔을 때 더 이상 진행하지 않는다고 해도
평균적으로 사다리 10개 중에 5개는 확인해야 한다면 5억번
거의 이정도 연산이 든다고 보이는데요
답은 맞았고 시간은 380ms가 걸렸는데, 어떻게 이 시간 안에 풀린건지 이해가 안되네요??
380ms면 대략 4000만번 연산에 끝났다난 의미 아닌가요?
1억회 연산 = 1초라는 기준은 정확한 게 아닙니다. 수행하는 연산이 매우 간단하다면 10억번은 1초 안에 수행할 수 있습니다.
그럼 간단한 연산이 들어 있는 경우는 시간 복잡도에서 제외하고 시간복잡도를 생각하는게 나을까요?
댓글을 작성하려면 로그인해야 합니다.
sgo8308 2년 전
N이 10이고 H가 30이라 가정할 때
dfs경우의 수만 270C3 하면 350만번 정도 나옵니다.
그리고 각 경우의 수마다 사다리를 타서 모두 자기 자신과 같은 숫자로 연결되는 지확인하는데 각 사다리마다 30번씩 10개해서 300번
350만 x 300 = 10억이 나옵니다.
사디리 타다가 일치하지 않는 거 나왔을 때 더 이상 진행하지 않는다고 해도
평균적으로 사다리 10개 중에 5개는 확인해야 한다면 5억번
거의 이정도 연산이 든다고 보이는데요
답은 맞았고 시간은 380ms가 걸렸는데, 어떻게 이 시간 안에 풀린건지 이해가 안되네요??
380ms면 대략 4000만번 연산에 끝났다난 의미 아닌가요?