hayman42   1년 전

본 문제를 저는 dfs 로 풀었는데 다른 분들것과 시간과 메모리를 비교한 결과 제 코드가 더 안좋다는 것을 확인 할 수 있었는데요,

제 생각엔 dfs 로 하든 bfs 로 하든 알고리즘에선 딱히 다르다고 느껴지지 않았습니다.


집합을 0, 1, 2 로 나누어 0을 방문하지 않은 점들의 집합이라고 하면 현재 점의 집합번호와 다른 0 아닌 번호, 즉 현재 1이면 2, 2면 1로 만들고.

만약 이미 방문 했는데 자신과 똑같다면 실패, 다르면 딱히 더 검사를 안하고 다음으로 넘어가기.

이러한 관점에서는 비슷하다고 생각했는데 제 코드의 시간과 메모리는 다른 똑같은 언어를 쓰신 분들의 것과 비교했을 떄 2~3배 가량 차이가 나네요 ㅠㅠ

혹시 이것이 dfs 가 본 문제에 대해선 bfs 보다 적합하지 않아서인가요? 아니면 제 코드의 문제인가요?

만약 제 코드의 문제라면, 어느 부분에서 문제인지 말씀해 주실 수 있다면 정말 감사하겠습니다.


제가 혼자 하는 것이라 주변에 물어볼 사람이 없어서.. 귀찮으시겠지만 혹시 시간이 나시면 부탁드려요.

djm03178   1년 전

연결리스트가 너무 무거워서가 아닌가 생각됩니다. 실제로 유용한 정보는 num 1개 (4바이트)인데, next 포인터가 8바이트나 되기 때문에 오버헤드가 상당히 큽니다.

게다가 set은 메모리 해제를 해주지 않는 것 같습니다.

doju   1년 전

시간이 오래 걸리는 것은 그래프를 만드는 부분이 아주 비효율적이기 때문입니다. 시간 초과가 나지 않는 것이 신기할 정도네요.
인접 리스트의 끝까지 따라가지 않고 좀 더 빠르게 노드를 추가하는 방법을 생각해 보세요.

hayman42   1년 전

djm님 감사드립니다. 그런데 그렇다고 노드 포인터를 안 쓸순 없는데.. 어찌 해야하나요?

Doju님도 감사드립니다. 제가 생각 했을 땐 중복되는 입력에 대해서 예외처리를 하려고 위 방식을 택 한 것이였는데.. 곰곰히 생각해보니 일정한 좋은 성능을 보장한다는 면에선 말씀해주신 방법이 더 좋겠네요.

djm03178   1년 전

C로 메모리를 적게 사용해서 푸신 분들을 보니 대체로 간선들을 따로 모아 하나의 배열에 저장해두고, 정렬을 해서 접근하는 방법을 쓰셨습니다. 사실 이쪽이나 저쪽이나 좀 귀찮은 일이기는 합니다. 저도 링크드 리스트로 풀었어서 메모리를 많이 먹었었고요.

반면 C++의 경우 주로 vector로 간선 정보를 저장하게 되는데 vector는 원소가 많아지면 자동으로 크기가 늘어나는 동적 배열이라 메모리 오버헤드도 크지 않을 뿐더러 구현이 아주 간편합니다. 그래서 C++ 코드들은 대체로 메모리 사용량도 적고 코드도 간결합니다.

hayman42   1년 전

역시 풀어도 더 배울것만 늘어나네요 ㅋㅋ ㅠㅠ 답변 감사드립니다~

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