creat21   4년 전

안녕하세요.

맞으면 안되는 코드가 맞았다고 나온게 궁금해서 글을 쓰게 됐습니다.

bfs을 queue을 이용해서 구현했습니다. ( 부모 노드에서 +1, -1, *2 값을 queue에 삽입했습니다.)

stl queue는 디폴트 컨테이너가 deque로 최대 255개의 데이터만 삽입이 가능했습니다.

그렇지만 12초만 되더라도 자식 노드의 개수는 355개로 255개를 초과했습니다.

하지만 이러한 코드로 제출해도 맞았다고 해서 이해가 되지 않습니다.

왜 255개 이후의 데이터가 삽입되지 않아도 답에 영향을 주지 않는 지 궁금합니다.


긴 글 읽어주셔서 감사합니다.

evenharder   4년 전

STL은 표준 템플릿 라이브러리(standard template library)입니다. 설마, 언어가 공식적으로 채택한 컨테이너들이, 255개 넘게 push하면 에러를 뱉도록 설계되어있을까요?

deque은 동적 이중 배열 형태로 구현되어 있는 경우가 많습니다. 원소를 추가할 수 없으면 동적으로 더 할당하여 충분한 공간을 확보합니다.

물론 메모리에 충분한 용량이 없으면 에러가 나겠지만, int형 255개로는 택도 없습니다. 어디서 해당 정보를 들으셨는지 궁금합니다.

creat21   4년 전

답변 해주셔서 감사합니다.

제가 디버깅을 하면서 queue에 데이터가 들어간 크기를 보고 의구심을 가지게 됐는데요. 

디버깅 창에서 내부 컨테이너가 deque인 크기가 255를 넘지 않는 게 보였고 내부 컨테이너를 리스트로 변경하니깐 크기가 계속해서 증가하는 걸 확인했습니다. 

djm03178   4년 전

원소를 deque에 많이 삽입하게 되면 그 크기 255짜리의 컨테이너가 추가로 생성되는 식으로 해서 전체 크기가 늘어나게 됩니다.

creat21   4년 전

와 감사합니다. 구글에서 찾아봐도 안나와서 답답했는데 하나 배우고 갑니다.

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