탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
DFS와 BFS를 본격적으로 알아보기 전, 두가지의 자료구조를 먼저 살펴보자.
1. 스택 자료구조
: 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조 (입구와 출구가 동일한 형태)
👉 파이썬에서 스택을 사용하기 위해서는 list 자료형을 사용하면 된다.
- 시간복잡도 : O(N)
2. 큐 자료구조
: 먼저 들어 온 데이터가 먼저 나가는 형식의 자료구조 (입구와 출구가 모두 뚫려 있는 형태)
👉 파이썬에서 큐를 사용하기 위해서는 deque 라이브러리를 사용하면 된다.
예) queue.append() -> 원소를 더할 때, queue.popleft() -> 원소를 뺄 때
- 시간복잡도 : O(N)
3. 재귀함수
: 자기 자신을 다시 호출하는 함수
👉 재귀함수가 스택에 담겨져 있어, 종료조건 후 가장 마지막에 담긴 것부터 출력하게 된다.
<예시>
* 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
def recursive_function(i):
# 10번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 10:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)<결과>
1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다.
2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다.
3 번째 재귀함수에서 4 번째 재귀함수를 호출합니다.
4 번째 재귀함수에서 5 번째 재귀함수를 호출합니다.
5 번째 재귀함수에서 6 번째 재귀함수를 호출합니다.
6 번째 재귀함수에서 7 번째 재귀함수를 호출합니다.
7 번째 재귀함수에서 8 번째 재귀함수를 호출합니다.
8 번째 재귀함수에서 9 번째 재귀함수를 호출합니다.
9 번째 재귀함수에서 10 번째 재귀함수를 호출합니다.
9 번째 재귀함수를 종료합니다.
8 번째 재귀함수를 종료합니다.
7 번째 재귀함수를 종료합니다.
6 번째 재귀함수를 종료합니다.
5 번째 재귀함수를 종료합니다.
4 번째 재귀함수를 종료합니다.
3 번째 재귀함수를 종료합니다.
2 번째 재귀함수를 종료합니다.
1 번째 재귀함수를 종료합니다.-
제한없이 재귀함수를 호출한다면, 스택 개체를 따로 만들어서 사용하는 방법이 있다. 하지만, 코딩테스트에서는 일반적인 재귀함수를 사용해도 통과할 수 있도록 출제된다.
-
팩토리얼 구현 예제
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)- 유클리드 호제법(최대공약수 계산)
: 두 자연수 A,B에 대하여(A>B) A를 B로 나눈 나머지를 R이라고 할 때, A,B의 최대공약수는 B와 R의 최대공약수와 같다.
<예시>
def gcd(a, b):
if a%b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192,162))<결과>
6- 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
-> 그래서, 스택을 사용해야할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
출처 : 이것이 취업을 위한 코딩 테스트다 링크텍스트
