자료구조 기초 - 탐색, 스택, 큐, 재귀함수

탐색(search)

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

 

그래프, 트리등 자료구조안에서 탐색을 활용하는데 탐색 알고리즘으로서는 DFS, BFS 등이 있다.

DFS, BFS를 이해하기 전에 스택과 큐, 재귀함수를 간단히 정리 하고 넘어가자

 

자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조

대표적으로 스택(stack), 큐(Queue)가 있다.

이둘의 구조는 공통적으로 핵심함수 2가지로 이루어져 있다.

- 삽입(push) : 데이터를 삽입한다.

- 삭제(pop) : 데이터를 삭제한다.

 

이외 오버플로우(특정한 자료구조가 수용할 수 있는 데이터의 크기를 넘어선 삽입연산시 발생)

언더플로우(자료구조에 데이터가 전혀 없는 상태에서 삭제연산을 수행하면 없는 데이터를 삭제해야 하므로 발생)

등을 고려해야한다.

 

스택

쌓기 나무를 생각하면 쉬운데 먼저 쌓은 나무가 가장 나중에 나오고(선입 후출 First In Last Out)

가장 늦게 쌓은 나무가 가장 먼저 나오는(후입 선출 Last In First Out) 구조로 불리운다.

 

stack

위 stack 그림을 이해하면

빈 스택 -> 삽입 1 -> 삽입2 -> 삽입3 -> 삭제3 순이다.

이를 파이썬으로 표현하면

stack = []
print(stack)

stack.append(1)
print(stack)
stack.append(2)
print(stack)
stack.append(3)
print(stack)
stack.pop()
print(stack)

위와 같다.

append('인수')함수는 가장 뒤에서 삽입, pop()함수는 가장 뒤에서 부터 삭제를 하는 기능이 있으므로 간단한 리스트로

stack을 표현할 수 있다.

 

큐(Queue)

큐는 보통 대기하는 줄을 표현한다. 즉 가장 먼저온 사람이 가장 먼저 들어간다. 가장 나중에 온사람이 가장 나중에 들어간다. 선입선출(First In First Out)구조로서 공정한 자료구조이다.

위 그림을 이해하면 

빈 큐 -> 삽입1 -> 삽입2 -> 삭제1

이를 파이썬으로 표현하면

from collections import deque
queue = deque()
print(queue)

queue.append(1)
print(queue)
queue.append(2)
print(queue)
queue.popleft()
print(queue)

# deque에서는 queue가 stack처럼 표현되기 때문에 실제 큐처럼 보이려면 역순으로 표현
queue.reverse()
print(queue)

deque 자료구조는 리스트에 비하여 원소 추가 제거의 시간복잡도가 O(1)으로 리스트는 가장 앞의 원소를 추가, 제거하기 위해 필요한 시간복잡도가 O(N)에 비하여 월등히 작아 효율적이다.-(리스트는 스택과 비슷하므로)

 

하지만 인덱싱, 슬라이싱등의 기능은 활용할 수 없다. 

함수로는 

 

popleft() : 첫 번째 원소를 제거할 때

pop(): 마지막 원소를 제거할 때

appendleft(x) : 원소 x를 첫 번째 인덱스에 삽입 할때

append(x) :원소 x를 마지막 인덱스에 삽입 할 때

 

즉, deque 자료구조는 함수 활용에 따라 스택과 큐를 구현할 수 있다.

 

재귀함수

DFS와 BFS를 이해하고 구현하려면 재귀함수가 필요하다.

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

def recursive_fuc(count):
    if count >= 5 or count < 0:
        return count
    print("재귀 함수 호출")
    count += 1
    # 자기 자신을 호출
    recursive_fuc(count)

recursive_fuc(0)

count가 0보다 작거나 5보다 크거나 같으면 재귀함수가 종료 되고 반환된다.

위와 같은 재귀함수의 종료 시점이 없다면 무한히 재귀되게 되는데 이때

 

파이썬의 인터프리터의 호출 횟수 제한을 넘게되면서 위와 같은 에러가 난다.

 

보통 재귀함수는 스택의 구조와 비슷하다. 가장 늦게 호출된 함수가 종료되어야 가장 첫번째로 호출된 함수가 종료된다.

즉 가장 늦게 호출된 함수가 실행되고 있으면 나머지 이전에 호출된 함수들은 닫혀있지 않다는 뜻이다.

함수자체는 메인 메모리에서 실행될 때 스택과 같은 구조에서 실행된다. 내부적인 자료구조가 동일하다.