자료구조 핵심 기초

탐색

자료구조

• 대표적으로 스택과 큐가 있음

연산의 종류 및 유의점

• push 연산 : 자료구조에 데이터를 삽입
• 자료구조 내부에 데이터가 가득 차있을 때 push 연산을 시도하면 overflow가 발생한다.

• pop 연산 : 자료구조에 데이터를 삭제
• 자료구조 내부에 데이터가 비었을 때 pop 연산을 시도하면 underflow가 발생한다.

파이썬에서의 스택과 큐

# 스택은 LIFO (Last In First Out)
-   스택은 마지막에 삽입된 요소를 top으로 관리한다. top으로 삽입되고 top으로 삭제된다.

# 파이썬에서의 스택 연산자 -> 파이썬에서는 -1번 인덱스가 top으로 간주된다.
1. append : top에 데이터를 삽입한다.
2. pop : top에 있는 데이터를 삭제한다.

# 큐는 FIFO (First In First Out)
1. 큐는 front과 rear로 이루어져 있다. 결론만 말하면, 데이터는 rear에서 삽입되어 front에서 삭제된다.
2. rear: 데이터가 삽입되는 위치 (enqueue)
3. front: 데이터가 삭제되는 위치 (dequeue)

# 파이썬에서의 큐 연산자
1. append : enqueue 연산으로, rear에 데이터를 삽입한다.
2. popleft : dequeue 연산으로, front에 있는 데이터를 삭제한다.
   (rear와 반대 방향의 위치이므로 pop이 아닌 popleft)

# 공통점
-   스택과 큐 모두, 출력 시 먼저 삽입된 순서대로 출력된다.
-   나중에 삽입된 것부터 출력하고 싶다면, reverse() 메서드를 사용하여 순서를 뒤집어 출력하면 된다.

그래프 이론

• 기본 요소
• node : 어느 지점
• edge : 노드 간 이동 경로
• 두 노드 간 edge로 연결되어 있으면 두 노드는 인접 관계에 있다. (adjacent)
• 인접 관계를 나타내는 방법은 두 가지가 있다.
• 인접 행렬 (adjacent matrix)
• 인접 리스트 (adjacent list)

• 인접 행렬 → for 실행 시간 절약
• 2차원 배열에 각 노드가 연결된 형태를 기록

# 인접 행렬
INF = 999999999

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

print(graph)

# [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

• 인접 리스트 → for 메모리 공간 절약
• 인접 리스트에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

# 인접 리스트
graph = [[] for i in range(3)]

# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph[2].append((0, 5))

print(graph)

# [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

• 두 방법 간 차이점
• 인접 행렬은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비되지만, 인접 리스트에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 비교적 빠르다.
• 인접 리스트는 연결된 정보만을 저장하므로 메모리는 효율적이나 특정한 두 노드의 연결 정보를 얻는 속도가 비교적 느리다.
• 인접 리스트는 연결된 데이터를 하나씩 확인해야 하기 때문이다. → 인접 행렬과 달리 연결 정보에 바로 액세스 불가능하여 앞에서부터 순차적으로 접근해야 한다.

DFS, BFS

DFS

• 스택 자료구조를 이용 → 주로 재귀호출로 구현

• 동작 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 top 노드에 방문하지 않은 인접 노드가 있다면, 방문 처리하고 인접 노드를 스택에 넣는다.
3. 스택의 top 노드에 방문하지 않은 인접 노드가 없다면, 해당 top 노드를 제거한다.
4. 스택에 넣을 노드가 더 이상 없을 때까지 반복한다. (모든 노드를 탐색할 때까지 반복한다.)

• 구현

# DFS 메서드 정의
# 필요한 것
# 1) graph : 인접 행렬 또는 인접 리스트 형태
# 2) v : 최초 탐색하는 노드 (BST의 경우 0)
# 3) visited : 노드 개수만큼의 크기를 가지며, 기본적으로 False로 초기화되어 있는 방문 여부 확인 리스트

def DFS(graph: list, v: int, visited: list):
  # 현재 노드를 방문처리
  visited[v] = True
  print(v, end=' ')
  
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      DFS(graph, i, visited)
      

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False for _ in range(9)]

# 정의된 DFS 메서드 호출
DFS(graph, 1, visited)

BFS

• 큐 자료구조를 이용

• 동작 과정
1. root node를 방문처리 후 큐에 삽입한다.
2. 큐에서 노드를 꺼내고, 꺼낸 노드의 인접한 모든 노드들을 큐에 삽입한다. 이후 꺼낸 노드를 방문처리 한다.
3. 2번 과정을 수행할 수 없을 때까지 (모든 노드가 탐색될 때까지) 반복 수행한다.

• 구현

from collections import deque

# BFS 메서드 정의
def BFS(graph: list, start: int, visited: list):
  # 큐 구현을 위해 deque 메서드 사용
  queue = deque([start])
  
  # 현재 노드를 방문 처리
  visited[start] = True
  
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 요소 하나를 뽑아 출력
    v = queue.popleft()
    print(v, end=' ')
    
    # 뽑은 요소를 방문 처리
    visited[v] = True
    
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True # 큐에 넣으면서 방문 처리
        

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
visited = [False for _ in range(9)]

# 정의된 BFS 함수 호출
BFS(graph, 1, visited)