[이코테]DFS&BFS

스택 구현

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1])
print(stack)

 

큐 구현

from collections import deque

#큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)   #먼저 들어온 순서대로 출력
queue.reverse()   #역순
print(queue)   #나중에 들어온 원소부터 출력

오른쪽으로 들어와서 왼쪽으로 나간다고 이해하면 된다.

큐의 경우도 리스트로 구현이 가능하지만, 시간적으로 리스트보다 deqeue을 사용하는 것이 좋다.

 

재귀함수

팩토리얼 구현

#반복적으로 구현한 n!
def factorial_iterative(n):
  result = 1
  #1부터 n까지의 수를 차례대로 곱하기
  for i in range(1, n+1):
    result *= i
  return result

#재귀적으로 구현한 n!
def factorial_recursive(n):
  if n<=1:   #n이 1이하인 경우 1을 반환
    return 1
  #n! = n*(n-1)!를 그대로 코드로 작성하기
  return n * factorial_recursive(n-1)

#각각의 방식으로 구현한 n! 출력
print('반복: ', factorial_iterative(5))
print('재귀: ', factorial_recursive(5))

 

최대공약수 계산(유클리드 호제법)

def gcd(a, b):
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

print(gcd(192, 162))

---

DFS(Deapth-First Search)

깊이 우선 탐색

스택 자료구조(혹은 재귀 함수)를 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

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)

 

BFS(Breadth-First Search)

너비 우선 탐색

큐 자료구조를 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

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]:
      if not visited[i]:
        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)

 

 

 

<출처>

이것이 취업을 위한 코딩 테스트다 with 파이썬

https://youtu.be/7C9RgOcvkvo

https://data-marketing-bk.tistory.com/entry/DFS-%EC%99%84%EB%B2%BD-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC