반응형
알고리즘 재귀반복
-
[ CS 기술면접 ] 알고리즘 예상질문 모음 !공부 !/Computer Science 2022. 5. 22. 01:01
알고리즘 질문 모음 # Adjacency Matrix, Adjacency List, UnionFind, LIS ✅ 인접 행렬과 인접 리스트의 장단점을 서로 비교하며 설명해 주세요. 어떤 경우에 무엇을 사용하는 것이 더 유리한지를 중점으로 설명해주시면 됩니다. 인접행렬의 경우 구현하기 쉬우며 빽빽한 그래프를 구현할때 좋습니다. 어떤 정점과 어떤 정점 사이 간선이 존재하는지 확인하기도 쉽습니다. 하짐나 어떤 점과 연결된 모든 노드를 방문하려면 O(V) 시간만큼이 걸립니다. 또한 공간복잡도가 O(V^2) 로 정점의 개수 V가 커질수록 메모리가 더 많이 필요합니다. 인접리스트의 경우 듬성듬성한 그래프로 구현할때 좋습니다. 어떤 정점에 연결된 다른 모든 정점들을 쉽게 방문할 수 있습니다. 하지만 어떤 정점과 어떤..