시간복잡도 생각해보기 250829

1번째 생각

• 무식하게 생각함.

맨 처음에 드는 생각이 9 x 9 원소를 전부 순회하면서 진행하면 어떨까? 생각함.

• -> 시간복잡도는 9 x 9 x 9 가 아니다.
  9*9 를 한다음에 9번 for문에서 또 재귀를 하는 것이므로,
  9의 9x9승의 시갖복잡도이다.
  즉 어마어마하므로, 아래의 방법은 잘못되었다.
  

확정.

• 확실하게 짚고 넘어가야 하는 부분은 num을 1에서 9까지 중에 결정하는 거는 무조건 필요하다.
  모든 열과 행을 탐색하는 거를 없애야 한다.
  -> 어떻게 하면 좋을까?

2번째 생각.

• 문제를 읽어보면, 0인 원소만 수정하면 된다. Checking하면서 수정을 해나가면서 기존의 0인 카운팅만 동일하면 출력하고 끝이다.
  즉, 0인 원소의 i,j값만 저장해 놓고, 해당 인덱스를 Check 해서 변경, 다음 i,j 진행하는 식으로 백트래킹을 하면
  첫번째 생각보다는 시간복잡도를 훨씬 줄일 수 있을 것으로 생각한다. (첫번째의 9*9 를 곱하는 거를 없앨 수 있다. )

• 정답 코드
  : 만약 num Check가 false 이더라도 다음번 num을 통해서 진행되고, idx 는 누적되는 것이 아니라, 재귀할때마다 다른 값으로 진행하기 때문에 문제 없다.

---

• 아래는 잘못된 내용이다.. 250829

시간초과 발생하는 코드 1번.

• 왜 틀렸을까?
  : 시간복잡도가 9의 3승이다. 즉 대충 1000이다.
  

틀렸다가 나오는 코드 2번.

• -> 왜 틀렸냐면, 방문 처리를 해야 한다. 이미 1번 target완료 되면 1번 으로 하면 안된다.

시간초과 발생하는 코드 3번.

• 뭘 더 줄여야 할까??
  

정답인 코드

• 이렇게 하면 맨 처음 1번코드의 999 의 시간복잡도를 없앨 수 있다.
  

https://www.acmicpc.net/submit/2580/95136485

내 생각

: 전체에 대해서 돌리는 것이 아니라, 이미 정해진 특정값만을 가지고 백트래킹을 하라는 문제인듯 하다.