3-O 시간복잡도 계산 질문

작성한 질문수 2

0

안녕하세요 원재님 ㅎㅎ

300개중 3개 뽑는 확률 X (추가된 가로선에 대해 정답인지 탐색하는 횟수 -> 대략적 n*h)

>> 네 맞습니다.

문제를 볼까요?

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

>> N * H는 최대 300입니다.

즉,

문제의 N * H의 최대는 300이며 따라서 전체적인 최대시간복잡도는 300(사다리확인) * 300C3(사다리뽑기 : 450만) := 10억정도가 됩니다. 완탐으로 생각했을 때 원래는 안된다고 생각하는게 맞고 백트래킹으로 어떻게든 줄여볼까 하면서 들어가야 하는 문제입니다.

(참고로 나중에 다른 알고리즘을 다 배운후라면 "다른 알고리즘을 적용할게 없네? 백트래킹이 최선의 알고리즘인걸?"라고 하면서 들어가야 하는 문제입니다.)

이부분에 대한 설명이 좀 빠진 거 같은데 제 설명의 허점을 파악하실 정도로 정말 잘 생각하셨습니다. ㅎㅎ

이 부분은 문제 내의 보완 설명부분으로 추가하도록 하겠습니다.

또 질문 있으시면 질문 부탁드립니다. 

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

감사합니다.