꼭 필요한 자료구조 기초
- 탐색 Search
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 대표적인 탐색 알고리즘인 DFS와 BFS
- 자료구조
- 데이터를 표현하고 관리하고 처리하기 위한 구조
- 스택과 큐
- 스택 Stack
- 큐 Queue
- 재귀 함수 Recursive Function
- 자기 자신을 다시 호출하는 함수
- 재귀의 최대 깊이 초과 오류 존재 → 무한대로 호출 불가
- 재귀 함수의 종료 조건
- 반드시 종료 조건 명시 필요
- 없으면 함수가 무한히 호출, 또는 오류 발생
- 재귀 함수 초반에 등장하는 if문이 종료 조건 역할을 수행
- 재귀함수 예제1: 2가지 방식으로 구현한 팩토리얼 예제
# 반복적으로 구현한 n!
def factorial_iterative(n)：
result = 1 # 1 부터 n까지의 수를 차례대로 곱하기
for i in range(n + 1)：
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n)：
if n <= 1： # n이 1 이하인 경우 1 을 반환
return 1
return n * factorial_recursive(n - 1)
# nl = n * (n - 1)!를 그대로 코드로 작성하기
# 수학의 점화식 = 재귀식: 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현
- 재귀함수 예제2: 최대공약수 계산(유클리드 호제법)
def gcd(a,b):
if a%b==0:
return b
else:
return gcd(b,a%b)
print(gcd(192,162))
# 6
- 재귀함수 사용의 주의사항
- 점화식 등의 알고리즘을 간결하게 작성할 수 있음
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임
- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수 히용하는 경우가 많음
탐색 알고리즘 DFS/BFS
- DFS (Depth First Search)
- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 그래프 Graph 의 기본 구조
- 노드 Node (= 정점 Vertex)
- 간선 Edge
- 두 노드가 간선으로 연결 = 두 노드는 인접하다 (Adjacent)
- 그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것
- 프로그래밍에서 그래프는 크게 2가지 방식으로 표현
- 인접 행렬（Adjacency Matrix）: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 무한 INF = 보통 999999999 로 표현
- 연결되어 있지 않은 노드끼리 → 무한의 비용
- 노드 개수가 많을수록 메모리 낭비됨
- 인접 리스트（Adjacency List）： 리스트로 그래프의 연결 관계를 표현하는 방식
- 2차원 연결 리스트 이용
- 메모리 효율적 사용 BUT 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림
- 순회해야하는 경우 메모리 공간의 낭비가 적음
- DFS 알고리즘
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방
문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2.의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
- 방문 처리: 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것
- 가장 깊숙이 위치하는 노드에 닿을 때까지 확인(탐색)
- 일반적으로 인접한 노드 중 방문하지 않은 노드가 여러개 있으면 번호가 낮은 순서부터 처리
# DFS 메서드 정의
def dfs(graph, v, visited)：
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]：
if not visited[i]：
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현（2차원 리스트）
graph = [
[], # 0번째 노드 비우기, 보통 문제에서 노드가 1번부터 시작하기 때문
[2, 3, 8], # 1의 인접 노드는 2,3,8이다
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현（1 차원 리스트）
visited = [False] * 9 # 0번째 index 사용하지 않기 위해 9개로 설정
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5
- BFS (Breadth First Search)
- 너비 우선 탐색
- 선입선출 방식인 큐 자료구조를 이용
- 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2.의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
- 예시: 간선 비용이 모두 동일한 경우, 특정 경로에서의 최단 거리 탐색
- 알고리즘 설명
- 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입
- 큐에 원소가 들어올 때, 위에서 들어오고 아래쪽에서 꺼낸다.
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited)：
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue： # 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
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] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6
DFS/BFS 요약
| |
DFS |
BFS |
| 동작 원리 |
스택 |
큐 |
| 구현 방법 |
재귀 함수 이용 |
큐 자료구조 이용 |
Reference
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저