1. 꼭 필요한 자료구조 기초
- 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
- push(데이터 삽입), pop(데이터 삭제)
- 오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 때 발생
- 언더플로: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태
- 스택: 선입후출, 후입선출
- append(): 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입
- pop(): 리스트의 가장 뒤쪽에서 데이터를 꺼냄
- 큐: 선입선출 구조
- 리스트 자료형에 비해 효율적
- 스택과 큐의 장점을 모두 채택한 것
- deque 객체를 list자료형으로 변경하고자 하면 list() 메서드를 이용하면 됨.
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.popleft()- 재귀 함수: 자기 자신을 다시 호출하는 함수
- 스택 자료구조를 이용함
- 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문에
- 코드의 길이가 간결함
2. 탐색 알고리즘 DFS
- DFS: 깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 알고리즘
- 그래프의 구조
- 노드(정점)와 간선으로 표현
- 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것
- 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현
- 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
- 2차원 리스트로 파이썬에서 구현 가능
- 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성
- 모든 노드에 대한 정보를 차례대로 연결하여 저장함.
- 그래프의 구조
INF = 99999999 #무한의 비용 선언
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)- 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장함
- 연결 리스트로 구현
- 2차원 리스트를 이용하면 됨
graph = [[]for _ in range(3)]
#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
#노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0,7))
graph[2].append((0.5))- 인접 리스트 vs 인접 행렬
- 메모리 측면
- 인접 행렬 방식: 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨
- 인접 리스트 방식: 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함
- 인접 리스트 방식이 속도가 더 느림: 특정한 두 노드가 연결되어 있느지에 대한 정보를 얻을 때, 연결된 데이터를 하나씩 확인해야 함.
- 메모리 측면
- 탐색 알고리즘: 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드 방문, 다시 다른 경로 탐색하는 알고리즘
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
- 스택을 사용하지 않아도 됨.
- 데이터의 갯수가 N이라면 시간 복잡도: O(N)
- 재귀함수 사용
def dfs(graph, v, visited):
#현재 노드 방문 처리
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]
]
visited = [False] * 9
dfs(graph, 1, visited)3. 탐색 알고리즘 BFS
- BFS: 너비 우선 탐색
- 가까운 노드부터 탐색하는 알고리즘
- 선입선출 방식인 큐 자료구조 이용
- 탐색 시작 노드를 큐에 삽입, 방문 처리를 함.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 함.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함
- deque 라이브러리를 사용: O(N) 수행시간
- 실제 수행 시간이 DFS보다 좋은 편
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end= ' ')
for i in graph[v]:
queue.append(i)
visited[i] = True
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False]*9
bfs(graph, 1, visited)