탐색
많은 양의 데이터중에 원하는 데이터를 찾는 과정
대표적인 그래프 탐색 알고리즘 DFS/BFS
스택 자료구조
먼저 들어 온 데이터가 나중에 나가는 자료구조 선입후출
입구와 출구가 동일한 형태 EX 박스쌓기
삽입과 삭제
파이썬의 리스트 자료형
append
pop
사용하면 스택과 같다
큐 자료구조
먼저 들어 온 데이터가 먼저 나가는 자료구조 선입선출
입구와 출구가 모두 뚫려 있는 터널과 같은형태
큐 구현을 위해 deque 라이브러리 사용
from collections import deque
queue = deque()
원소 추가
append
원소 삭제
popleft
역순으로 바꾸기
reverse
재귀 함수 Recursive Function
자기 자신을 다시 호출하는 함수
DFS를 구현할 때 자주 사용
파이썬은 재귀 함수의 깊이를 초과하면 오류가 난다
종료 조건을 명시하지 않으면 오류가 발생
스택과 비슷하게
처음 시작된게 제일 마지막에 종료된다
팩토리얼 구현 예제
def a(n):
if n <= 1:
return 1
return n * a(n - 1)
print(a(5))
유클리드 호제법 예제 (최대공약수 계산)
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
수학적으로 정의된 점화식과 같은 형태를 간단히 코드로 변환해줌
다른사람이 어려운 형태의 코드가 될 수 있음
모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현 가능
재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다
DFS depth-first search
깊이 우선 탐색
깊은 부분을 우선적으로 탐색하는 알고리즘
DFS는 스택 자료구조(혹은 재귀 함수)를 이용
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph, 1, visited)
가장 깊은 곳 우선 탐색
BFS breadth-first search
너비 우선 탐색
가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 이용한다
최단 경로 문제에 효과적으로 사용가능하다
문제 음료수 얼려 먹기
문제 미로 탈출
DFS BFS 너무 어렵다...
