공부 : 동빈나 유튜브 < 3. DFS & BFS > + 책 < 이것이 취업을 위한 코딩테스트다 >
탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- DFS/BFS는 대표적은 그래프 탐색 알고리즘
(사전 학습) 자료구조 정리
자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
- 삽입(Push) / 삭제(Pop)
- Overflow와 Underflow를 신경쓰기
1. 스택
- 선입후출(First In Last Out) / 후입선출(Last In First Out) 구조
- 파이썬에서 별도의 라이브러리 없이 리스트로 구현 가능
stack = []
#순서대로 5 2 3 7 삽입 - 삭제 - 1 4 삽입 - 삭제
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() #7이 삭제
stack.append(1)
stack.append(4)
stack.pop() #4가 삭제
print(stack[::-1]) #스택의 최상단 원소부터 출력
2. 큐
- 선입선출(First In First Out)
- 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화 가능
- collection 모듈에서 제공하는 deque 자료구조 사용
- deque는 스택과 큐의 장점을 모두 채택한 것
- 리스트로도 구현이 가능하지만 deque를 사용하는 것에 비해 시간 복잡도가 높다.
- queue 라이브러리를 이용하는 것보다 간단하다.
from collections import deque
queue = deque()
#순서대로 5 2 3 7 삽입 - 삭제 - 1 4 삽입 - 삭제
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() #5 삭제
queue.append(1)
queue.append(4)
queue.popleft() #2 삭제
print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력
#list 자료형으로 출력하려면 list(queue)
+ 재귀함수 - 자기 자신을 다시 호출하는 함수
- 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용
- 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다.
- 재귀함수가 반복문보다 유리할 수도 있고 불리할 수도 있다.
# 재귀함수를 이용한 팩토리얼 예제
def factorial_recursive(n):
if n == 1:
return 1
return factorial_recursive(n-1)*n
print(factorial_recursive(5))
(재귀함수) 최대공약수 계산 (유클리드 호제법) 예제
유클리드 호제법
- 두 자연수 A, B에 대하여 ( A > B ) A를 B로 나눈 나머지를 R이라고 하면
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
# 두 개의 자연수에 대한 최대공약수 구하기
# 유클리드 호제법
def gcd(a, b):
if a % b == 0:
return b
return gcd(b, a % b)
print(gcd(192, 162))
+ 그래프
노드(Node)와 간선(Edge)로 표현, 노드를 정점(Vertex)라고도 부름
- 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것
- 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현
프로그래밍에서 그래프는 크게 2가지 방식으로 표현 가능
- 인접 행렬(Adjacency Matrix)
: 메모리가 불필요하게 낭비 / 정보를 인접 리스트보다 빠르게 얻음
INF = 999999999 #무한의 비용선언
#2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
- 인접 리스트(Adjacency List) : 연결 리스트 이용
: 메모리 효율적 사용 / 정보를 인접 방식보다 느리게 얻음
#행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ 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)
DFS(Depth-First-Search)
- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조를 기초로 한다, O(N)
#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)
#index 0을 사용하지 않는 방향으로 코드 작성됨
# 각 노드가 연결된 정보 표시
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
#각 노드가 방문된 정보를 표현(1차원리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
dfs(graph, 1, visited)
BFS(Breadth-First-Search)
- 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조를 이용한다, O(N)
- 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편
from collections import deque
#BFS 메서드 정의
def bfs(graph, start, visited):
#큐 구현 위해 라이브러리 사용
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
#index 0을 사용하지 않는 방향으로 코드 작성됨
# 각 노드가 연결된 정보 표시
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
#각 노드가 방문된 정보를 표현(1차원리스트)
visited = [False] * 9
#정의된 DFS 함수 호출
bfs(graph, 1, visited)
예제
1. 음료수 얼려먹기
- 처음에 띄어쓰기 없이 받을 때 split을 쓰면 안된다 !!!!!
#00011 int로 받기
list(map(int, input()))
#문자로 각각 받기
list(input())
- 결국 한 블록을 찾을 때는 2중 for문이 들어갔다.
- 내가 짠 코드는 BFS로 조금 복잡/ 유튜브에서는 DFS로 재귀함수를 사용해서 간단한 느낌
2. 미로 탈출
- 미로찾기이기 때문에 BFS로 코드를 작성하는게 맞는 것 같다.
- 근데 나는 DFS로 짰다.
--> 벽이나 범위를 넘어갈 경우에 최대값으로 99999를 설정했다. 이렇게 하는것보다는 BFS가 더 정확한 느낌
코드 정리 : https://github.com/mingxoxo/Algorithm/tree/master/study/BFS_DFS
GitHub - mingxoxo/Algorithm: 알고리즘
알고리즘. Contribute to mingxoxo/Algorithm development by creating an account on GitHub.
github.com
'study > 알고리즘' 카테고리의 다른 글
[알고리즘] 구현 : 시뮬레이션과 완전 탐색 (0) | 2021.11.10 |
---|---|
[알고리즘] DFS/BFS - 백준 1260번/2606번 (0) | 2021.11.09 |
[알고리즘] 이진탐색 (0) | 2021.11.04 |
[알고리즘] 그리디(Greedy) 알고리즘 (0) | 2020.10.11 |
[알고리즘] 파이썬 문법 복습 (0) | 2020.09.24 |