DFS-BFS 기본 #1

1. 알아야할 자료구조

- Stack : FILO

 python에서 list를 이용

stack = []

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

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

********

[4, 1, 7, 5]
[5, 7, 1, 4]

 

- Queue : FIFO

  python에서 list로 구현가능하나 시간 복잡도가 증가하므로 deque자료구조를 이용한다.

from collections import deque

queue = deque()

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

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

********************

deque([3, 2, 7, 8, 1])
deque([1, 8, 7, 2, 3])

 

2. 재귀함수

# 유클리드 호제법을 이용하여 두 개의 자연수에 대한 최대 공약수를 구하라
# 유클리드 호제법
# 두 자연수 A,B에 대하여(A>B) A를 B로 나눈 나머지를 R이라고 하면
# A, B의 최대 공약수는 B와 R의 최대 공약수와 같다.

def GCD(a :int, b: int) -> int:
    if a%b == 0: 
        return b
    else:
        return GCD(b, a%b)

print(GCD(192,162))

******

6