그래프 짤 때 adjacency matrix vs adjacenc... - 인프런

안녕하세요 정말 강의 잘 듣고 있습니다. 저는 코딩을 영어로 공부하고 있는데 지금까지 봤던 문제들 중에서 graph 를 짜는 부분에서 adjacency matrix 와 adjacency list 두 종류를 쓰셨는데 강의에서 말씀하신 부분을 보면 모든 면에서 adjacency list 가 더 낫지 않나요? 특히나 메모리를 적게 쓰는 부분과 더 짜기가 쉽다는 부분에 있어서요. adjacency marix 가 adjacency list 보다 선호되는 케이스가 혹시 있는지 궁금해서 질문 드립니다. 그리고 adjacency list 를 만드실 때 리스트 안에 리스트를 만드는 설정을 하셨는데 혹시 해시맵에 리스트를 넣어서 하는 게 더 보편적인건가요?

추가) 아 그리고 visited 는 list 에 False 로 채워넣는것 대신에 set() 으로 하는 게 더 메모리에 좋을까요?

안녕하세요 David님 🙂

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

List vs. Matrix

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

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

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

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

list vs. set

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

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

인프런 커뮤니티 질문&답변

그래프 짤 때 adjacency matrix vs adjacency list