그래프 탐색 알고리즘 DFS & BFS (1)

그래프 탐색 알고리즘 DFS / BFS

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

1. 스택 / 큐

stack / queue

2. 재귀함수(Recursive Function) 

 

- 자기 자신을 다시 호출하는 함수

- 문자열을 무한히 출력하다 최대 재귀 깊이 초과 메세지가 출력됨

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

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

- 스택에 데이터를 넣었다 꺼내는 것과 같이 작동

 

- 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음

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

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

2-1. 팩토리얼 구현

 

- n! = 1 X 2 X 3 X ... X (n-1) X n

- 수학적으로 0!과 1!의 값은 1

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

 

- 두 개의 자연수에 대한 최대공약수를 구하는 알고리즘

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

- A와 B의 최대공약수 = B와 R의 최대공약수