[자료구조] 자료구조 기초 : 스택 / 큐 / 재귀함수

 

자료구조 (Data Structure)

자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.

대표적으로는 스택, 큐가 존재하는데, 삽입, 삭제 두 핵심 함수로 구성된다.

• 삽입 (Push) : 데이터를 삽입
• 삭제 (Pop) : 데이터를 삭제

오버플로 (Overflow) : 특정 자료구조가 데이터를 저장할 수 있는 공간이 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 즉, 저장공간보다 데이터가 많을 때 발생한다.

언더플로 (Underflow) : 특정 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생한다. 

 

 

스택 (Stack)

스택은 한 쪽 끝에서만 데이터 삽입/삭제가 가능한 선입후출 구조(LIFO - Last In First Out)으로 되어 있다.

파이썬에서는 스택 구현을 리스트 또는 deque 라이브러리로 한다.

 

큐(Queue)

큐는 양쪽에서 데이터 삽입/삭제가 가능한 선입선출 구조(FIFO - First In First Out)으로 되어 있다.

파이썬에서는 큐 구현을 위해 deque 라이브러리를 사용한다.

 

참고

2021.05.27 - [파이썬 Python] - [파이썬 Python] collections 라이브러리 / deque / Counter

[파이썬 Python] collections 라이브러리 / deque / Counter

 

 

재귀함수 (Recursive Function)

재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.

재귀함수는 종료 조건을 명시하지 않으면, 자기 자신을 무한대로 호출하기 때문에 종료 조건을 반드시 설정해야 한다.

 

재귀함수의 대표적인 예제로는 팩토리얼(factorial) 이 있다.

팩토리얼

• 기호는 느낌표(!) 를 사용하며, 1부터 자기자신까지 곱해준 값을 의미한다.
• n! = 1 * 2 * 3 * … * (n-1) * n
• 1! = 1   (수학적 약속)
• 0! = 1   (수학적 약속)

규칙(점화식)

5 ! = 5 * 4 * 3 * 2 * 1 = 5 * 4 !

4 ! = 4 * 3 * 2 * 1 = 4 * 3 !

3 ! = 3 * 2 * 1 = 3 * 2 !

2 ! = 2 * 1 = 2 * 1 !

1 ! = 1 (다음 팩토리얼이 없으므로 종료)

 

규칙이 n ! = n * (n-1)! 임을 알 수 있다.

 

알고리즘

그럼 5 ! 을 구해보자.

 

5 ! 을 구하는 함수 호출

5 ! = 5 * 4 !

→ 4 ! 을 구하는 함수 호출 

4 ! = 4 * 3 !

→ 3 ! 을 구하는 함수 호출

3 ! = 3 * 2 !

→ 2 ! 을 구하는 함수 호출

2 ! = 2 * 1 !

→ 1 ! 을 구하는 함수 호출

1 ! = 1 (종료 조건)

→ 1 ! 을 구하는 함수 종료 후 2 ! 을 호출하는 함수로 돌아간다.

2 ! = 2 * 1 = 2

→ 2 ! 을 구하는 함수 종료 후 3 ! 을 호출하는 함수로 돌아간다.

3 ! = 3 * 2 = 6

→ 3 ! 을 구하는 함수 종료 후 4 ! 을 호출하는 함수로 돌아간다.

4 ! = 4 * 6 = 24

→ 4 ! 을 구하는 함수 종료 후 5 ! 을 호출하는 함수로 돌아간다.

5 ! = 5 * 24 = 120

→ 5 ! 을 구하는 함수 종료

 

코드

# 팩토리얼 함수

def factorial(n):
    if n <= 1:					 # 종료조건 명시
        return 1
    return n * factorial(n-1)

print(factorial(5))

120

위의 예제에서 불 수 있듯이 재귀함수는 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료된다. 따라서, 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용함을 알 수 있다.

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

 

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년