python - 자료구조 기초 : DFS/BFS 1탄

탐색 = Search

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

그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸

 

대표적인 탐색 알고리즘

• DFS
• BFS

 

기본 지식 : 스택, 큐, 재귀 함수

---

자료 구조 = Data Structure

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

 

스택과 큐는 자료구조의 기초 개념이다

두 함수로 이뤄진다(Push, Pop)

• Push는 삽입으로, 데이터가 들어감
• Pop은 삭제로, 데이터가 삭제됨

 

실제로는 스택, 큐를 사용시 다른 경우의 수로 오버플로 또는 언더플로를 고려해야함

 

오버플로Overflow 는 특정한 자료구조가 수용할 수 있는 데이터 크기를 이미 가득 찬 상태에서 삽입된 경우에 연산이 수행되면서 발생함

즉, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생

 

언더플로Underflow는 특정한 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산 수행시 데이터가 전혀 없기에 발생함

 

 

---

Stack 스택

박스 쌓기의 일종이다

박스는 아래에서부터 위로 차곡차곡 쌓는다

그리고 아래에 있는 박스를 치우기 위해서 위에 있는 박스를 먼저 내린다

 

이러한 구조를 선입후출First in Last out 구조 또는 후입 선출Last in First Out 이라고 한다

 

stack = []

# 삽입 - 삽입 - 삽입 - 삭제 - 삽입 - 삽입 - 삭제

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

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 스택 최상단 원소부터 출력

출력된 결과

---

큐

대기줄에 비유할 수 있음

먼저 온 사람이 먼저 들어가는 구조

공정한 자료구조라 비유된다

선입선출 구조이다

First in First out

 

# 디큐 라이브러리
from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입 - 삽입 - 삽입 - 삭제 - 삽입 - 삽입 - 삭제
queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(4)
queue.append(5)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력하기
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력하기

queue는 디큐 라이브러리를 사용하자

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

 

---

재귀함수 Recursive Function

자기 자신을 다시 호출하는 함수

 

프랙털 구조와 유사 Fractal

 

 

# 재귀함수
print('재귀함수')

def recursive_function(n):
    _curr, _next= 0, 1
    for _ in range(n+1):
        yield _curr
        _curr, _next = _next, _curr + _next
        
fib = recursive_function(10)

for i, v in enumerate(fib):
    print('피보나치 수열({}) : {}'.format(i, str(v)))

재귀함수

 

def recursive_function1(i):
    # 10번째 출력시 종료되도록 조건 명시
    if i == 10:
        return
    print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
    recursive_function1(i+1)
    print(i, '번째 재귀 함수를 종료합니다')

recursive_function1(1)

 

6번째 라인에서 재귀가 수행되면서 결과는 아래와 같다.

 

---

팩토리얼 - 재귀함수

 

# 팩토리얼 풀기 - 2가지 방법
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
        result *= i
    return result



print(factorial_iterative(4))# 재귀함수를 쓰지 않은 경우

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n-1)

print(factorial_recursive(4)) # 재귀함수를 사용한 경우

결과값은 동일하다.

 

재귀함수 코드가 반복문 보다 간결한 코드이다.

종료 조건은 if 문을 통해 설정한다.

 

또한 if 조건문에 잘못된 입력을 받았을 때, 오류로 인지할 수 있게 만드는 장치도 추가할 수 있을 것이다.(추후에)

 

 

---