스택, 큐 알고리즘

탐색 - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 탐색 알고리즘: DFS/BFS 

 

자료구조 - 데이터를 표현 ·관리 · 처리하기 위한 구조 

스택과 큐는 자료구조의 기초 개념으로 삽입과 삭제 함수로 구성됨. 

실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 함.

---

스택

 - 스택은 후입선출구조이다.

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

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) #[5,2,3,1]

 

---

큐

- 큐는 대기 줄에 비유할 수 있다.

- 흔히 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 흔히 '공정한' 자료구조라고 비유된다.

 - 이러한 구조를 선입선출 구조라고 한다.

 

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자.

deque는 스택과 큐의 장점을 모두 채택한 것으로 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 

from collections import deque

queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) #deque([3, 7, 1, 4])
queue.reverse()
print(queue) #deque([4, 1, 7, 3])

---

재귀 함수

 - DFS/BFS를 구현하려면 재귀 함수도 이해하고 있어야 한다. 

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

def recursive_function():
	print("재귀 함수를 호출합니다.")
	recursive_function()
   
recursive_function()

 

이 코드를 실행하면 "재귀 함수를 호출합니다."라는 문자열을 무한히 출력한다.

여기서 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다. 

보통 파이썬 인터프리터는 호출횟수 제한이 있기 때문에 어느 정도 출력하다가 오류 메세지를 출력하고 멈춘다.

따라서 무한대로 재귀 호출을 진행할 수는 없다.

 

#반복적으로 구현한 n!
def factorial_iterative(n):
    result=1
    for i in range(1, n+1):
        result*=i
    return result

#재귀적으로 구현한 n!
def factorial_recursive(n):
    if n<=1:
        return 1
    return n*factorial_recursive(n-1)

재귀 함수 내에서 특정 조건일 때 더 이상 재귀 함수를 호출하지 않고 종료하도록 if문을 이용해 종료 조건을 구현해주어야 한다.

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