jinsj1   6년 전

이전 질문 중, chogahui05 님이 아이디어를 구체적으로 주셔서
그 방법대로 짜보려고 했습니다..

하지만, 예상치 못한 메모리 초과를 발견하였고, 어디를 어떻게 손봐야 할지 몰라
질문하게 되었습니다.

간단하게 코드를 말씀드리면,
먼저, 각 노드에 대해 헤밍코드가 1인 값에 대해서만
인접리스트 형식으로 저장하고요
이후에, parent를 저장하는 방식으로 진행됩니다.

chogahui05   6년 전

일단 보이는 건 9번째 줄의 a[i] ^ b[i] 인데요.

몇 %에서 메모리 초과가 뜨시나요?

jinsj1   6년 전

90%에서 메모리초과 라고 뜹니다
빠른 답변 정말 감사드려요ㅠ_ㅠ

chogahui05   6년 전

경로가 없는 경우를 체크해 보셨나요?

chogahui05   6년 전

아무래도 경로가 없는 경우에도 wif 벡터에서 -1이 나올 때 까지 탐색을 하려다 보니

무한 루프가 돌게 되고 그로 인해서 bad_alloc이 발생하는 듯 싶네요.

jinsj1   6년 전

와,,, 정말 감사드립니다!
저도 말씀하신 while 문에서 문제가 발생하는 것 같은 느낌은 들었으나
추측에서 사고가 멈춰버렸었거든요ㅠㅠ

덕분에 해결했구요, 아이디어부터 문제점 해결까지
진심으로 감사드립니다!



chogahui05   6년 전

의외로 경로까지 출력하라는 문제가 꽤 있습니다.

지나온 경로를 출력하라는 문제는 dp에서도 왕왕 보이는 문제인데요.

예를 들어서, 이런 문제도 그런 예지요.

https://www.acmicpc.net/proble...


알고리즘 기본 교재에서도 나오는 것이니까요. 알아두시면 좋을 듯 싶습니다.

jinsj1   6년 전

이래서 노란책이 필요한가봅니다ㅠㅠ
기초를 백준님 온라인 강의로 시작했는데
배운 아이디어를 제대로 습득하지 못한 것인지
기반이 좀 많이 부실합니다..(물론 처음부터 실력이 좋았다면...)

추천 문제까지 제시해주시다니..이런 댓글은 처음입니다!
제안하신 문제도 풀어보겠습니다.
감사합니다!!


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