코테 공부 [DFS/BFS]

[ 1. DFS / BFS ]

STACK (LIFO)

DFS는 Stack 이용 [ 사실상 일반 리스트랑 동일 ]

stack.append(n)
stack.pop()

# 최상단 원소부터
print(stack[::-1])
# 최하단 원소 부터
print(stack)

python

DFS

시작 노드를 stack에 삽입하고 방문 처리 (visited[v] = true)

방문 하지 않은 인접노드를 stack에 넣는 과정을 끝까지 반복

⇒ 들어간 노드가 여러 개면 해당 인접 노드가 최고 깊이 까지 탐색이 완료된 이후의 순번 (LIFO)

def dfs(graph, start):
    n = len(graph)
    visited = [False] * n
    stack = [start]

    while stack:
        v = stack.pop()
        if visited[v]:
            continue

        visited[v] = True
        print(v, end=' ')

        for w in (graph[v]):
            if not visited[w]:
                stack.append(w)

graph = [
    [1, 2],
    [0, 3, 4],
    [0, 5],
    [1],
    [1, 5],
    [2, 4]
]

dfs(graph, 0)

python

QUEUE(FIFO)

BFS는 queue 이용 [ 반드시 import deque ]

from collections import deque

queue = deque()

queue.append(n)
queue.popleft()

# 들어온 순서 
print(queue)

#역순으로 바꾼다음에 출력
queue.reverse()
print(queue)

python

BFS

시작 노드를 queue에 삽입하고 방문 처리 (visited[v] = true)

방문 하지 않은 인접노드를 queue에 넣는 과정을 끝까지 반복

⇒ 들어간 노드가 여러 개면 해당 인접 노드가 다음 순번 (FIFO)

from collections import deque

def bfs(graph, start):
    n = len(graph)
    visited = [False] * n
    queue = deque([start])
    
    while queue:
        v = queue.popleft()
        if visited[v]:
            continue

        visited[v] = True
        print(v, end = '')

        for w in (graph[v]):
            if not visited[w]:
                queue.append(w)


graph = [
    [1, 2],
    [0, 3, 4],
    [0, 5],
    [1],
    [1, 5],
    [2, 4]
]

bfs(graph, 0)

python

[ 2. 재귀함수 ]

factorial

n이 1 이하인 경우 return 1

그렇지 않은 경우 return n* f(n-1)

유클리드 호제법 (GCD)

최대공약수 구하는 문제에서 (A>B)
- A를 B로 나눈 나머지가 R이면 GCD(A,B)는 GCD(B,R)

결과적으로 A%B = 0이면 return B

그렇지 않은 경우 GCD(B, A%B)

+ 추가로 두 수가 서로소 라면 최대 공약수 = 1

이는 결국 해당 코드에서 a%b가 1인 값이 도출되서 자동으로 해당 코드에서 b % 1 =0으로 자동 진행

ASHD Dev_Blog

코테 공부 [DFS/BFS]

[ 1. DFS / BFS ]

[ 2. 재귀함수 ]

Tags