그래프 짤 때 adjacency matrix vs adjacency list

상세한 답변 정말 감사합니다!

list vs set에서는 visited 를 set 으로 설정하면 True False 말고 visited 안에 해당 노드가 있는지 없는지를 체크하는 것으로 중복을 체크하는 것을 말한 거였어요.

안녕하세요 David님 🙂

질문 하나씩 답변 드릴게요!

1. List vs. Matrix

    

말씀하신대로 List를 사용하는게 메모리에서 훨씬 유리하고 코딩하는 것도 조금 더 간단할 수 있을 것 같아요(물론 코딩 부분은 선호도의 차이일 수도 있지만요). 그에 비해 Matrix는 성능이 더 좋습니다. List는 LinkedList 자료구조와 비슷하게 다음 요소를 하나씩 순차적으로 접근해야되는 반면, Matrix는 특정 위치를 index 기준으로 접근하기 때문에 조금 더 빠른 경향이 있습니다. 대부분의 자료구조들을 볼 때 나타나는 공통점인데, 메모리를 더 쓰면 속도가 빨라지고, 메모리를 아끼려고 하면 속도가 조금 느려집니다 (일종의 trade-off이고 둘다 개선할 수 있는 기술을 혁신이라고 하는 것 같아요).

그런데 코딩테스트/Leetcode 단계에서는 이 둘의 성능 차이가 크게 있냐면 그렇진 않은 것 같아요! 즉, List만 써서 풀어도 문제 없을 거고, 저는 강의를 하는 차원에서 둘다 보여드리기 위해서 이렇게 만들었는데, List만 사용하시는 게 한 풀이만 공부하고 적용하는 것이라 더 쉬울 수도 있습니다!

2. 리스트 안에 리스트 vs. 해시맵 안에 리스트

둘 중 어떤 게 더 보편적인지는 잘 모르겠지만, 둘다 정답이 될 수 있습니다! 제가 C++ 프로그래밍을 먼저 시작해서 2차원/3차원 배열을 쓰는 게 훨씬 쉽다고 느낄 수 있는데요, 문제를 푸는 관점에서는 둘이 동일한 동작을 하기 때문에, 둘 중 원하시는 것을 선택하시면 될 것 같아요!

3. list vs. set

    

이 부분은 제가 이해를 잘못 한 것 같아요. 각 노드에 대한 visited 정보를 list로 관리해야지 해당 노드가 방문 되었는지 아닌지를 판단할 거라서 list를 사용했는데, set는 중복이 없는 자료구조이기 때문에 처음 초기화를 하고나면 False라는 Boolean 변수 하나만 남지 않을까요? 중복이 허용되어야 하는 자료구조라서 set이 잘 맞을지는 모르겠어요! 혹시 제가 잘못 이해한 거라면 다시 한번 질문해주세요!

오늘도 공부하시느라 고생 많으셨습니다 :)