알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 5. DFS, BFS - 스택, 큐, 재귀함수

  • 0
  • 0
0
0

1. 자료구조 기초

  • 탐색(Search)
    • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
    • DFS, BFS
  • 자료구조(Data Structure)
    • 데이터를 표현하고 관리하고 처리하기 위한 구조
    • 스택, 큐
    • 삽입, 삭제 함수로 구성된다.
    • [[오버플로]]와 [[언더플로]]도 고민해야 한다.
a. 오버플로

수용할 수 있는 데이터의 크기가 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다.

b. 언더플로

데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생

A. [[스택 (stack)]]

1. Stack

선입후출(FILO), 후입선출(LIFO) 구조

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


# stack  
  
stack = []  
  
stack.append(5)  
stack.append(2)  
stack.append(3)  
stack.append(7)  
a = stack.pop()  
stack.append(4)  
  
print(stack)  
print(stack[::-1])


[5, 2, 3, 4]
[4, 3, 2, 5]

파이썬에서 스택을 이용할 떄는 리스트에 append(), pop() 메소드를 이용하면 스택 자료구조와 동일하게 동작한다.

#자료구조 #스택

B. [[큐 (Queue)]]

1. 큐

선입선출 (FIFO)

입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화


from collections import deque  
  
queue = deque()  
  
queue.append(1)  
queue.append(2)  
queue.append(3)  
queue.append(4)  
a = queue.popleft()  
queue.append(5)  
  
print(queue)  
queue.reverse()  
print(queue)  
print(list(queue))


deque([2, 3, 4, 5])
deque([5, 4, 3, 2])
[5, 4, 3, 2]

deque는 스택과 큐의 장점을 모두 책택한 것.

데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 간단하다.

#자료구조 #큐

C. [[재귀함수 (Recursive Function)]]

1. 재귀함수

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


def recursive_function():  
    print("재귀 함수 호출")  
    recursive_function()  
  
recursive_function()

프랙탈(Fractal) 구조와 흡사

A. 재귀 함수의 종료 조건

재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.


def recursive_function_2(i):  
    if i == 10:  
        return  
 else:  
        print("{0} 번째 재귀 함수에서 {1} 번째 재귀 함수를 호출합니다.".format(i, i+1))  
        recursive_function_2(i+1)  
        print("{0} 번째 재귀 함수를 종료합니다.".format(i))  
  
recursive_function_2(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 번째 재귀 함수를 종료합니다.

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 떄 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다.

a. 팩토리얼

def factorial_iterative(n):  
    result = 1  
  
 for i in range(1, n+1):  
        result *= i  
    return result  
  
def factorial_recursive(n):  
    if n <= 1:  
        return 1  
 return n * factorial_recursive(n-1)  
  
print("반복적으로 구현 : {0}".format(factorial_iterative(5)))  
print("재귀적으로 구현 : {0}".format(factorial_recursive(5)))


반복적으로 구현 : 120
재귀적으로 구현 : 120

반복문 대신에 재귀 함수를 사용했을 때 얻을 수 있는 장점은?

재귀 함수의 코드가 더 간결함. 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문. 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미

  • 팩토리얼을 점화식으로 표현
    • n이 0 혹은 1일 때
      • factorial(n) = 1
    • n이 1보다 클 때
      • factorial(n) = n * factorial(n - 1)

일반적으로 점화식에서 종료 조건을 찾을 수 있다. 재귀 함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해주어야 한다.

재귀 함수는 반복문을 이용하는 것과 비교했을 때 더욱 간결한 형태이다.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #자료구조 #기초 #스택 #큐 #재귀함수

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.