jumpingz   2년 전

큐를 이용하여 완전탐색을 하는 방식으로 구현했는데 계속 런타임에러가 나길래 몇개 예제를 넣어보니까

1234 9999 넣는 순간 터지던데 이런 에러가 발생하더라구요..

DEBUG_ERROR("vector<bool> iterator not dereferencable");

검색해보니까 열거형의 마지막으로 접근할때 발생하는 에러라는데 뭔소리인지 모르겠네요..

해당 코드가 왜 저런 에러를 발생시키는지 알 수 있을까요??

doju   2년 전

메시지는 거창하지만 평범하게 잘못된 인덱스를 참조해서 일어나는 오류입니다. S 연산을 하는 부분의 예외 처리에 실수가 있습니다.

jumpingz   2년 전

감사합니다.. 입력값에 0이 들어오는게 있엇군요.. 덕분에 해결했습니다만 궁금한점이 하나더 있는데

이런 문제의 BigO 는 어떻게 계산해야하는지 알 수 있을까요?? 막연하게 완전탐색이라고해서 무조건 N! 이런건아닐것같은데요..

알려주실수 있나요?

doju   2년 전

일반적인 BFS는 각각의 상태를 한 번씩만 방문하게 되기 때문에 시간복잡도는 O(상태의 개수)가 됩니다. 이 문제의 경우는 상태의 개수가 10000개로 정해져 있다고 볼 수 있습니다.

다만 지금의 구현은 연산 과정을 전부 문자열로 저장하고 있기 때문에 새로운 상태를 방문할 때마다 문자열을 생성 및 복사하게 되고, 이 과정에서 상당한 오버헤드가 발생합니다. 정보를 보다 적게 저장하면서 명령어 나열을 복원할 방법을 생각해 보세요.

jumpingz   2년 전

감사합니다

댓글을 작성하려면 로그인해야 합니다.