dusrlf13   3년 전

파이썬으로 동일하게 코드를 짰다가 시간초과로 C++로 작성해보았습니다. 에디터 상에서 답은 확실히 C++코드가 빨리 나오긴 하는데 채점해보니 둘다 시간초과 뜨는 것은 마찬가지네요... 어느 부분에서 개선하면 좋을지 리뷰 부탁드립니다!

plan222   3년 전

놓을 수 있는 자리인지 판단하는 함수인 Promising이 너무 오래걸리는 것 같습니다.

굳이 모든 판을 훑지 않아도 빠르게 판별할 수 있는 방법이 있습니다.

예를들어 특정 세로줄에 퀸이 존재하는지 기록하는 배열을 만들어서 해당 줄을 보면 바로 알 수 있겠지요.

대각선도 마찬가지 방법으로 해결 하실 수 있을겁니다.

dusrlf13   3년 전

답글 감사합니다.

하나만 더 여쭤봐도 될까요?


nqueen 문제는 보통 일차원 배열로 각 행에 있는 퀸의 열만 저장해서 판별을 하는 방법이 정석이던데

말씀해주신 방법대로 promising을 개선하면 2차원 배열 선언으로도 해결이 가능할지 궁금합니다.

plan222   3년 전

제가 말한 방식은 2차원 배열이 필요 없는 방식입니다.

특정 가로줄, 세로줄, 대각선줄마다 퀸이 최대 1개 존재하므로 2차원 배열을  1차원으로 압축시켜 빠르게 확인 할 수 있게 하는 것이죠.


2차원 배열을 그대로 사용하고 싶으시다면 대각선을 확인하는 과정에서 모든 판을 훑는게 아니라, 양 대각선 쪽만 탐색하는 식으로 좀더 최적화가 가능하긴 합니다.

제 코드가 0.9초 정도 걸려서 통과했었는데 그것보다 최대 16배정도 느리니까 통과하기 애매하지 않을까 생각이 듭니다.


dusrlf13   3년 전

답글 감사합니다.

참고해보겠습니다.

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