[알고리즘] 자료구조 기초 (스택, 큐, 재귀함수)

탐색이란?

 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 

대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 둘을 이해하기 위해서는 기본 자려구조인 스택과 큐에 대한 이해가 되어야 한다.

 

자료구조란?

 자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초개념으로 다음의 두 핵심적인 함수로 구성된다.

 

• 삽입(push) : 데이터를 삽입한다.
• 삭제(pop) : 데이터를 삭제한다.

 

 추가로 스택과 큐를 사용할 때에는 언더플로(underflow)와 오버플로(overflow)를 고려해야한다.

오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 반면 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로가 발생한다.

---

스택

 스택은 아래에서부터 위로 차곡차곡 쌓는 형태이다. 아래에 있는 걸 꺼내기 위해서는 위에 있는 걸 먼저 꺼내야 아래에 있는걸 꺼낼 수 있는데 이러한 구조를 선입후출(FILO) 구조 또는 후입 선출 구조라고한다.

 

 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용하지 않고 사용할 수 있다. 파이선의 기본리스트에서 append()와 pop()을 사용하면 스택 자료구조와 동일하게 수행된다. append() 메서드는 리스트의 가장 뒤에 값을 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내게된다.

---

큐

 큐는 대기줄에 비유할 수있다. 먼저 들어온 것이 먼저 나가는 형태이다. 나중에 들어온 것일 수록 나중에 나가게 되는데 이러한 구조를 선입선출(FIFO)구조라고 한다.

 

 파이썬에서 큐를 구현할 때에는 collections 모듈에서 제공하는 deque를 사용하여 구현할 수 있다. deque()를 사용하면 popleft() 메서드를 통해 가장 먼저들어온 데이터를 가장 먼저 꺼낼 수 있다.

---

재귀 함수

 DFS와 BFS를 구현하기 위해서는 재귀함수도 이해하고 있어야한다. 재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.

재귀 함수는 수학에서 언급되는 프랙털 구조(삼각형이 무한히 존재하는 구조)와 흡사하다. 

 재귀함수를 사용할 때에는 종료조건을 꼭 명시해야한다. 자칫 종료 조건을 명시하지 않는다면 재귀 함수가 무한히 호출될 수 있다.

 

 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 따라서 스택 자료구조를 활용해야하는 상당수의 알고리즘은 재귀함수를 이용하여 간편하게 구현될 수 있다. ex_) DFS

 

 재귀 함수를 사용하는 대표적인 예제로는 팩토리얼이 있다. 팩토리얼을 파이썬 코드로 반복적으로 구현한 방식과 재귀적으로 표현한 방식을 비교해보자.

#반복적으로 구현
def factorial_iter(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)

재귀함수가 코드가 더 간결해진 것을 볼 수 있는데 이유는 재귀함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문이다. 

 

팩토리얼에 대한 수학적 점화식은 아래와 같다.

1. n이 0 or 1 일 때 : 1
2. n이 1보다 클 때 : n*factorial(n-1)