선발대 강의) 재귀함수, DFS와 BFS

깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색과 너비 우선 탐색이 있다.

 

그래프: 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

그래프를 탐색한다는 것은, 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

 

깊이 우선 탐색	너비 우선 탐색
최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을 경우 옆으로 이동	최대한 넓게 이동한 다음 더이상 갈 수 없을 때 아래로 이동
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색	루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
스택 또는 재귀함수로 구현	큐를 이용해서 구현

 

 

재귀함수: 스스로 호출하는 함수

유의할 점: 종료조건, 끝도 없이 호출되어서는 안 된다. 언젠가는 실행이 멈춰야 한다.

 

• 종료조건이 없을 경우, 에러발생한다.

RecursionError: maximum recursion depth exceeded while calling a Python object

def recursion(n):
   print(n)
   recursion(n+1)

recursion(1)

 

• 최대 재귀 깊이: 재귀함수를 최대로 호출할 수 있는 횟수 파악하기

import sys

print(sys.getrecursionlimit())

# 1000번 까지 가능

 

그렇다면, 재귀로 풀 수 있는 문제를 어떻게 눈치챌 수 있을까!!!

 

REASON 1. 문제 푸는 전체 과정을 펼쳐 생각해보았을 때, 문제 풀이 과정의 일부분이 문제를 푸는 전체 과정과 유사하다.

REASON 2. 문제풀이 과정에서 비슷한 논리가 꼬리에 꼬리를 무는 형태..!!

 

 

예시 1. 16팩토리얼의 값을 구하시오.

def factorial(n):
    if n <= 0 :
        return 1
    return n * factorial(n-1)

print(factorial(16))

 

 

예시 2. 피보나치 수열 12번째 항을 구하시오.

def fib(n):
    if n==1:
        return 0
    if n==2:
        return 1
    return fib(n-1)+fib(n-2)

print(fib(12))

 

 

예시 3. 파스칼 삼각형의 8번째 줄 리스트로 출력하는 함수 만들기

# 파스칼삼각형
def pascal(n):
    if n==1:
        return [1]
    else:
        return [1] + [(pascal(n-1)[i])+(pascal(n-1)[i+1]) for i in range(n-2)] +[1]
    

print(pascal(8))