자료구조 & DFS

자료구조란?

데이터를 저장하거나 관리하는 방법
크게 선형 구조와 비선형 구조로 나눌 수 있다.

자료구조는 코딩테스트와 실무에서 시간복잡도를 줄이는 핵심 도구이기 때문에 반드시 이해해야 함.

선형 구조

1. 배열 (Array)

   • 인덱스로 접근 가능 → 검색 속도가 빠름
   • 하지만 자료 수정/삭제가 잦으면 비효율적
   • 시간복잡도:
     • 조회: O(1)
     • 삽입/삭제: O(n)

2. 연결 리스트 (Linked List)

   • 노드들이 포인터로 연결된 형태
   • 삽입/삭제가 잦을 때 효율적
   • 시간복잡도:
     • 특정 노드 검색: O(n)
     • 삽입/삭제: O(1) (단, 해당 위치를 알고 있을 때)

3. 스택 (Stack, LIFO)

   • Last In First Out (마지막에 넣은 데이터가 먼저 나온다)
   • 예시: 함수 호출, 되돌리기(Undo)
   • 구현: append(), pop()

4. 큐 (Queue, FIFO)

   • First In First Out (먼저 넣은 데이터가 먼저 나온다)
   • 예시: 은행 대기열, 프로세스 스케줄링
   • 구현: collections.deque 활용

비선형 구조

1. 트리 (Tree)

   • Node(노드) : 데이터를 저장하는 공간
   • Root(루트) : 최상위 노드
   • Leaf(리프) : 자식이 없는 노드
   • 특징
     • 부모-자식 관계
     • 단방향 연결
     • Cycle 없음
   • 대표적인 예시: 이진 탐색 트리 (Binary Search Tree, BST)
     • 왼쪽 자식 < 부모 < 오른쪽 자식
     • 검색 속도가 O(log n)

2. 그래프 (Graph)

   • 트리 구조가 아닌 더 일반적인 형태
   • 양방향 가능, Cycle 가능
   • 표현 방식: 인접 행렬 / 인접 리스트
   • 활용 예시:
     • 네트워크 경로 탐색
     • 지도 최단 경로 (Dijkstra, Floyd-Warshall)
     • 소셜 네트워크 관계

🔹 그래프 표현 방법

1. 인접 행렬

• 장점: 구현이 직관적, 두 노드 간 연결 여부 확인이 빠름 O(1)
• 단점: 메모리 낭비 (간선이 적을 경우 비효율적)

name = 'ABCDEF'
arr = [
  [0,1,1,0,0,0],
  [0,0,0,1,1,0],
  [0,0,0,0,0,1],
  [0,0,0,0,0,0],
  [0,0,0,0,0,0],
  [0,0,0,0,0,0]
]

2. 인접 리스트

장점: 메모리 효율적 (간선이 적을 경우 유리)

단점: 특정 간선 존재 여부 확인은 느림

arr = [[1,2],
       [3,4],
       [5],
       [],
       [],
       []]

DFS (Depth First Search, 깊이 우선 탐색)

• 한 방향으로 끝까지 탐색한 뒤, 다시 돌아와 다른 경로 탐색
• 재귀 함수를 활용하는 경우가 많음
• 중복 방문 방지 → visited 배열 사용
• DFS의 시간복잡도
  1. 인접 행렬: O(V^2) (V: 정점 수)
  2. 인접 리스트: O(V+E) (V: 정점, E: 간선 수)

-> 따라서 간선이 많은 밀집 그래프(dense graph)는 인접 행렬, 간선이 적은 희소 그래프(sparse graph)는 인접 리스트가 효율적입니다.

• 인접 행렬 DFS

name = 'ABCDEF'
def dfs(now):
    print(name[now], end=' ')
    for i in range(6):
        if arr[now][i] == 1:
            dfs(i)

dfs(0)  # A부터 탐색

• 인접 리스트 DFS

# 인접 리스트 DFS

arr = [[] for _ in range(N)]
for _ in range(M):
    s, e = map(int, input().split())
    arr[s].append(e)

def dfs(now):
    print(now, end=' ')
    for nxt in arr[now]:
        dfs(nxt)