[python] 자료구조 - 스택 , 큐 , 재귀함수

 

🎵 탐색

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

• 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다
• 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다.
• DFS와 BFS에 대해 제대로 이해하기 위해서 스택과 큐에 대한 이해가 전제되어야한다.

🎵 자료구조

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

• 스택과 큐를 구성하는 핵심 함수
  • 삽입 (push) : 데이터를 삽입한다
  • 삭제 (pop) : 데이터를 삭제한다
  👉 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야한다.
  • 오버플로 : 저장공간에 데이터가 가득 찬 상태에서 삽입 연산을 수행할 때 발생
  • 언더플로 : 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행할때 발생

 

 

 

---

❤️ 스택 (stack)

☝ 스택은 그릇 쌓기와 비유할 수 있다. 그릇은 아래에서부터 위로 차곡차곡 쌓아야한다. 그리고 항상 위에 있는 그릇부터 먼저 내려야한다. 이러한 구조를 선입후출 (First In Last Out) 구조 또는 후입선출 (Last In First Out)구조라고 한다.

 

 

• 간단한 예제

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

• 👉 삽입(5) → 삽입(2) → 삽입(3) → 삽입(7) → 삭제() → 삽입(1) → 삽입(4) → 삭제()

파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다.

append() 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내오기 때문에 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.

 

 

 

---

❤️ 큐 (queue)

☝ 큐는 대기줄에 비유할 수 있다. 놀이공원에 입장하기 위해 줄을 설때 먼저 온 사람이 먼저 들어가게 된다. 나중에 온 사람일수록 나중에 들어가기 때문에 ‘공정한’ 자료구조라고 비유된다. 이러한 구조를 선입선출(First In First Out) 구조 라고 한다.

• 간단한 예제

  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()
  
  queue
  

  ❓ deque는 스택과 큐의 장점을 모두 채택한 것이다. 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 대부분의 코딩 테스트에서 collections 모듈과 같은 기본 라이브러리 사용을 허용하므로 안심하고 사용해도 괜찮다.
• 👉 삽입(5) → 삽입(2) → 삽입(3) → 삽입(7) → 삭제() → 삽입(1) → 삽입(4) → 삭제()

---

 

 

 

❤️ 재귀함수

☝ 자기 자신을 호출하는 함수 프랙털 구조와 흡사하다.

def recursion_fun(count):
    print('재귀')
    if count==10:return
    
    recursion_fun(count=count+1)

👉 무한히 호출하지 않기 위해서는 중간에 재귀함수의 종료조건을 설정해주어야한다.

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

• 팩토리얼 예제

def factorial(n):
    if n==0 or n==1:
        return 1
    return n*factorial(n-1)

cf ) for문으로 구현해보기

def factorial_for(n):
    result=1
    if n>1:
        for i in range(1,n+1):
            result=result*i
        
    return result

❓ 재귀함수로 구현할때와 for문으로 구현할 때 실행결과는 동일하다. 그렇다면 반복문 대신에 재귀함수를 사용했을 때 얻을 수 있는 장점은 무엇일까?

‼️ 코드가 간결해진다.

‼️ 재귀함수가 점화식을 그대로 소스코드로 옮긴것이다. → 다이나믹 프로그래밍으로 이어지기 때문에 중요하다.