데이터 구조 및 알고리즘: 이진 탐색, 인접행렬, 인접리스트

본 내용은 " 아래에서 3개 주제를 골라 개념 설명하고 예제를 만들어 설명하시오. " 의 원문 자료에서 일부 인용된 것입니다. 2023.11.08

문서 내 토픽

• 1. 이진 탐색

  이진 탐색은 정렬된 배열에서 특정 값을 효율적으로 찾는 검색 알고리즘입니다. 분할 정복 전략을 활용하여 탐색 범위를 반으로 줄이면서 목표값을 찾습니다. 시작점, 중간점, 종료점을 기준으로 중간값을 검사하여 범위를 조정합니다. 예를 들어 배열 [10, 24, 31, 45, 59, 63, 72, 88, 95]에서 63을 찾을 때, 중간값 45와 비교하여 오른쪽 범위로 조정하고, 다시 72와 비교하여 왼쪽 범위로 조정한 후 63을 찾습니다. 대규모 데이터셋에서 검색 작업의 효율성을 크게 증대시킵니다.

• 2. 인접행렬

  인접행렬은 그래프의 노드 간 연결 관계를 2차원 배열로 표현하는 데이터 구조입니다. 각 셀은 두 노드의 연결 상태를 나타내며, 연결되면 1, 미연결이면 0으로 표시합니다. 노드 간 연결이 밀집된 그래프에서 유용하며 두 노드 간 직접 연결 여부를 빠르게 확인할 수 있습니다. 가중 그래프에서는 간선의 가중치를 저장하고 미연결 노드 쌍에는 무한대 값을 할당합니다. 희소 그래프에서는 메모리를 비효율적으로 사용하는 단점이 있습니다.

• 3. 인접리스트

  인접리스트는 각 노드에 연결된 모든 노드의 리스트를 사용하여 그래프의 연결 관계를 표현하는 데이터 구조입니다. 각 노드를 인덱스로 하는 배열에 인접한 노드의 목록을 연결 리스트 형태로 저장합니다. 희소 그래프에서 메모리를 효율적으로 사용하며, 노드 간 연결을 동적으로 추가하거나 제거하는 작업에 유연하게 대처합니다. 예: 노드 1:[2], 노드 2:[1,3], 노드 3:[2,4], 노드 4:[3]. 연결된 노드 수에 비례하는 메모리만 사용하여 공간 복잡도가 낮습니다.

Easy AI와 토픽 톺아보기

• 1. 이진 탐색

  이진 탐색은 정렬된 데이터에서 매우 효율적인 탐색 알고리즘입니다. O(log n)의 시간복잡도로 선형 탐색의 O(n)보다 훨씬 빠르게 원하는 요소를 찾을 수 있습니다. 특히 대규모 데이터셋에서 그 성능 차이가 극적으로 나타납니다. 다만 사전에 데이터가 정렬되어 있어야 한다는 전제조건이 있으며, 동적으로 변하는 데이터에서는 정렬 유지 비용을 고려해야 합니다. 재귀적 또는 반복적 구현 모두 가능하며, 프로그래밍 면접과 실무에서 자주 출제되는 중요한 알고리즘입니다.

• 2. 인접행렬

  인접행렬은 그래프를 2차원 배열로 표현하는 방식으로, 두 정점 간의 연결 여부를 O(1)에 확인할 수 있는 장점이 있습니다. 구현이 직관적이고 간단하며, 특정 간선의 존재 여부를 빠르게 판단해야 할 때 효율적입니다. 그러나 정점의 개수가 n일 때 O(n²)의 공간을 항상 차지하므로, 정점이 많고 간선이 적은 희소 그래프에서는 메모리 낭비가 심합니다. 따라서 밀집 그래프나 정점 개수가 적은 경우에 적합한 표현 방식입니다.

• 3. 인접리스트

  인접리스트는 각 정점마다 연결된 정점들을 리스트로 저장하는 방식으로, O(V+E)의 공간만 필요하므로 희소 그래프에서 매우 효율적입니다. 메모리 사용량이 적고 그래프 순회 알고리즘에 최적화되어 있습니다. 다만 특정 간선의 존재 여부를 확인하려면 O(degree)의 시간이 필요하므로 인접행렬보다 느릴 수 있습니다. 실제 응용에서는 대부분 희소 그래프를 다루므로 인접리스트가 더 자주 사용되며, DFS, BFS 등의 그래프 알고리즘 구현에 매우 적합합니다.