graph를 만들 때
kyg8821
작성일
23.11.21 17:08
조회수
141
안녕하세요. 선생님 덕분에 멋진 강의를 듣고 있는 학생입니다.이제 유형 1을 다 수강했는데, graph를 초기화할 때 보통 N의 개수가 적으면 불리언 2차원 배열로 선언하고, N의 개수가 많으면 빈리스트로 구성된 2차원 리스트로 선언하는데요.그냥 모든 문제에 빈리스트로 구성된 2차원 배열을 선언하지 않는 이유가 N의 개수가 적으면 배열로 선언하고 조회하는 게 더 빠르기 때문인지 여쭤봐도 될까요?
댓글 1
kyg8821님 안녕하세요 🙂
말씀하신 게 모두 맞습니다! 정리를 하자면 전부 빈 리스트에 append할 수 있습니다. 그래서 풀이를 통일하고 싶다면 이렇게 하는 게 제일 좋습니다!
물론 배열을 접근하는 게 성능이 좋지만, 그만큼 메모리 낭비도 발생하기 때문에 장/단점이 뚜렷합니다. 코딩테스트의 특성상 그 정도 메모리 낭비는 용납되기 때문에 더 빠른 솔루션이 더 좋다고 할 수 있지만, 제 경험 상 빈 리스트를 쓴다고 해서 timeout이 발생했던 적은 없어서 큰 차이는 없다고 봐도 될 것 같아요!
저는 강의를 하는 입장에서 여러 방식을 알려드리는 게 더 유익하다고 판단해서 여러가지 보여드렸는데, 솔루션을 통일하는 게 코딩 테스트 준비에 더 유리하기 떄문에 전부 빈 리스트에 append하는 방식을 쓰는 것도 좋을 것 같아요.
혹시 더 궁금하신 점이나 제 답변 중에 부족한 부분이 있으면 편하게 또 질문 주세요! 오늘도 공부하느라 고생 많으셨습니다 :)
답글