[알고리즘] DFS & BFS (1)

* 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다.

---

출처

동빈나 이코테

 

 

 

■ 탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 탐색 알고리즘 : DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

 

---

■ DFS와 BFS를 하기 전에 알아야 할 자료구조

스택, 큐

 

 

● 스택 자료구조

- 먼저 들어온 데이터가 나중에 나가는 선입후출의 자료구조

- 입구와 출구가 동일한 형태로 시각화할 수 있다.

 

 

■ 스택 구현 예제(Python)

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
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) # 최하단 원소부터 출력

append와 pop은 시간 복잡도가 상수시간 만큼 든다여기서 stack[::-1]은 처음부터 끝까지 -1의 간격으로 배치한다는 의미이다.

 

---

 

● 큐 자료구조

- 먼저 들어 온 데이터가 먼저 나가는 선입선출의 자료구조

- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다.

 

 

■ 큐 구현 예제(Python)

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()
queue.append(1)
queue.append(4)
queue.popleft()

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

리스트로 큐를 작성할 수 있지만 시간복잡도가 더 많이 들어서 비효율적이다.

그래서 덱 라이브러리 사용!!

 

---

 

■ 재귀 함수(Recursive Function)

DFS를 실질적으로 구현하고자 할 때 자주 사용되는 방법

자기 자신을 다시 호출하는 함수를 의미

 

 

■ 재귀 함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시

(종료조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.)

def recursive_function(i):
	# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100
    	return
    print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다')
    recursive_function(i + 1)
    print(i, '번째 재귀함수를 종료합니다.')
    
recursive_function(1)

1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다 ~ 99 번째 재귀함수에서 100 번째 재귀함수를 호출합니다

99 번째 재귀함수를 종료합니다. ~ 1 번째 재귀함수를 종료합니다.

 

 

처음에는 1에서 99번째 까지 재귀함수를 호출합니다는 이해했지만 99에서 1번째 재귀함수를 종료합니다. 의 반복은 이해를 하지 못하였다. 재귀함수에 대해서 찾아보다가 알게 되었다.
함수가 호출될 때 공간이 할당되고 종료하면서 해제되는 메모리 영역을 call stack이라 나타낸다. 함수가 호출(call)되면 스택 프레임이 append(메모리 할당) 되고 함수가 종료되면 스택 프레임이 pop(메모리 할당 해제) 되므로 반복하게 된다.

 

 

■ 팩토리얼 구현 예제

● n! =  1 x 2 x 3 x ··· x (n - 1) x n

● 수학적으로 0! 과 1! 의 값은 1입니다.

# 반복적으로 구현한 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! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

 

 

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

● 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘(유클리드 호제법)

● 유클리드 호제법

    두 자연수 A, B에 대하여 (A> B) A를 B로 나눈 나머지를 R이라고 하자

    이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

단계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

 

 

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

 

 

■ 재귀 함수 사용의 유의 사항

● 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능

(단, 이해하기 어려운 형태의 코드가 될 수 있으니 신중하게 사용)

● 모든 재귀 함수는 반복문을 이용하여 동일한 기능으로 구현 가능

●  재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음

●  컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다

    - 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음

 

 

 

 

참고

https://targetcoders.com/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98-%EC%98%88%EC%A0%9C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0/

재귀함수 예제로 이해하기, 3가지 규칙 - 타깃코더스