자료구조: 스택, 큐, 재귀 함수 [초등학생도 이해하는 파이썬]

 안녕하세요 '코딩 오페라'블로그를 운영하고 있는 저는 'Master.M'입니다. 저는 오늘부터 '초등학생도 이해하는 파이썬파이썬'이라는 주제로 파이썬(python)에 대해 포스팅을 하고자 합니다. 제목처럼 진짜 핵심 내용을 쉽게 설명하는 것을 목표로 하고 있으니 파이썬(python)에 입문하고 싶은 분들은 많은 관심 부탁드립니다. 지금부터 알아볼 내용은 '스택, 큐, 재귀함수'입니다. 

 

 

스택 (stack)

스택

 스택(stack)은 끝이 막혀있는 좁은 주차장과 같습니다. 이 경우 위 그림과 같이 먼저 들어간 차(5번 차)가 가장 나중에 나올 수 있게 되며, 가장 나중에 들어간 차(8번 차)가 가장 빨리 나올 수 있습니다. 때문에 새로운 10번 차가 왔을 때 가장 나중에 들어간 8번 차가 나오고 이 자리를 10번 차가 대신하면 됩니다. 

 

 이러한 구조를 '스택(stack)'이라고 하며, 이는 선입후출(first in last out) 또는 후입선출(last in first out)의 구조를 따릅니다.  

 

위 예제를 파이썬 코드로 구현하면 다음과 같습니다.

"""
stack
"""

stack = []

stack.append(5)
stack.append(4)
stack.append(7)
stack.append(8)
print(stack)

stack.pop()
stack.append(10)
print(stack)

[5, 4, 7, 8]
[5, 4, 7, 10]

append 함수를 이용해 stack list에 차 번호 값을 추가해주고, pop을 이용해 list에서 값을 제거해 줍니다.

이 코드를 실행하면 위와 같은 출력값이 나오는데, 위 의 그림과 같은 값임을 확인할 수 있습니다.

 

 

 

큐 (queue)

큐

 큐(queue)는 스택과 달리 양쪽이 뚫려있는 도로와 같습니다. 위 그림과 같이, 5번 차가 제일 왼쪽에 있을 때 10번 차가 오른쪽에서 추가되면 5번차가 주차장에서 나가게 되고, 새로운 10번차가 맨 오른쪽에 자리 잡게 됩니다. 

 

 이러한 구조를 '큐(queue)'라고 하며, 이는 선입선출(first in first out)의 구조를 따릅니다.

 

위 예제를 파이썬 코드로 구현하면 다음과 같습니다.

"""
queue
"""

from collections import deque

queue = deque()

queue.append(5)
queue.append(4)
queue.append(7)
queue.append(8)
print(queue)

queue.popleft()
queue.append(10)
print(queue)

deque([5, 4, 7, 8])
deque([4, 7, 8, 10])

deque의 append 함수를 사용해 차 번호 값을 오른쪽으로 추가해 주고, popleft함수를 사용해 왼쪽 원소들을 제거해 줍니다. 이 코드를 실행하면 위와 같은 출력값이 나오는데, 위 의 그림과 같은 값임을 확인할 수 있습니다.

 

 

 

재귀 함수 (Recursive Function)

'재귀'라는 말은 "원래 자리로 돌아감"이라는 뜻으로, 재귀함수는 "자기 자신을 통해 다시 자기자신을 호출하는 함수"로 정의됩니다. 

 

def hello(count):
    # count가 0이면 함수 종료
    if count == 0:
        return

    print("Hello", count)

    count -= 1
    hello(count)


hello(5)

 

예를 들어 위와 같은 함수가 바로 '재귀함수'입니다. 여기서 함수 hello 안에 마지막 부분에서 다시 자기 자신인 함수 hello를 호출하므로 함수 hello가 계속 무한이 반복됩니다. 재귀함수의 경우 스택 메모리를 사용하기 때문에, 이렇게 무한이 반복되면 스택 오버플로우가 발생해 문제가 되기 때문에, 이 예제에서는 count라는 변수를 이용해 5번만 출력하도록 하였습니다.

 

Hello 5
Hello 4
Hello 3
Hello 2
Hello 1

 

이렇게 출력이 5번 되는 모습을 확인하실 수 있습니다. 

 

이러한 재귀함수는 반복문(for 문, while 문)과 비슷하지만 다른 점이 있습니다.

• 재귀함수는 반복문에 비해 변수의 수를 줄일 수 있어 가독성이 뛰어남
• 스택 메모리를 사용하기 때문에, 스택 오버플로우(스택 메모리가 꽉 차는 현상)가 발생하여 문제를 일으킬 수 있음
• 연산 속도가 반복문에 비해 느림

 

 

  지금 까지 저희는 '스택(stack), 큐(queue), 재귀함수(recursive function)'에 대해 알아보았습니다. 도움이 되셨나요? 만약 되셨다면 구독 및 좋아요로 표현해 주시면 정말 많은 힘이 됩니다. 궁금한 사항 혹은 앞으로 다루어 주었으면 좋을 주제가 있으시면 댓글 남겨주시면 감사하겠습니다. 저는 '코딩 오페라'의 'Master.M'이었습니다. 감사합니다.