그래프(Graph)의 표현 방법(인접 행렬, 인접 리스트)과 각각의 장단점을 설명해주세요.

그래프를 표현하는 대표적인 방법으로는 인접 행렬과 인접 리스트가 있습니다.

인접 행렬은 2차원 배열을 사용하여 정점 간의 연결 관계를 표현합니다. 예를 들어, matrix[i][j] = 1은 정점 i에서 정점 j로 가는 간선이 존재한다는 의미입니다. 장점으로는 특정 정점 쌍의 연결 여부를 O(1) 시간 안에 확인할 수 있다는 점이 있습니다. 하지만 모든 정점 쌍에 대한 정보를 저장해야 하므로, 공간 복잡도가 O(V^2)입니다. 따라서 간선이 적은 희소 그래프의 경우 메모리 낭비가 심할 수 있습니다.

반면, 인접 리스트는 각 정점에 연결된 정점들을 리스트 형태로 저장합니다. 예를 들어, 정점 i의 리스트에는 정점 i에서 갈 수 있는 모든 정점들이 저장됩니다. 인접 리스트는 실제 간선 수에 비례하는 공간 복잡도 O(V+E)를 가지므로, 희소 그래프에 효과적입니다. 하지만 특정 정점 쌍의 연결 여부를 확인하려면 해당 리스트를 탐색해야 하므로, 시간 복잡도는 O(V)가 될 수 있습니다. 따라서 간선 탐색 빈도가 높은 경우에는 인접 행렬이 더 효율적일 수 있습니다.