자료구조 기초 - Python

이미 자료 구조와 알고리즘을 C로 다 배운 상태이지만, 코딩 테스트를 파이썬으로 준비하고 있기 때문에 복습차원에서 파이썬으로 다시 한번 정리 해보기로 하였다.

탐색

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

• 대표적인 탐색 알고리즘으로 DFS, BFS가 존재하고 해당 알고리즘을 제대로 이해하기 위해서는 스택과 큐에 대한 이해가 전제되어 있어야 한다.

자료 구조

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

• 스택과 큐가 가장 기본적이며 삽입, 삭제 함수로 구성된다.

  • cf. 오버플로와 언더 플로를 고민해야한다.
  
  

  스택

  출처: https://www.programiz.com/dsa/stack

• 선입후출(FILO) 구조 또는 후입선출(LIFO) 구조이다.

• python 구현

  stack = []
  
  # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  stack.append(5)
  stack.append(2)
  stack.append(3)
  stack.append(7) 
  stack.pop()
  stack.append(1)
  stack.append(4)
  stack.pop()
  
  print(stack)        # 최하단 원소부터 출력
  print(stack[::-1])  # 최상단 원소부터 출력
  
  출력:
  [5, 2, 3, 1]
  [1, 3, 2, 5]

  • 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없이 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료 구조와 동일하게 동작한다.

큐

출처: https://harsh05.medium.com/queue-data-structure-a-comprehensive-guide-137d7c02a4b7

• 선입선출(FIFO) 구조이다.
  

• python 구현

  from collections import deque
  
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque()
  
  # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  queue.append(5)
  queue.append(2)
  queue.append(3)
  queue.append(7)
  queue.popleft()
  queue.append(1)
  queue.append(4)
  queue.popleft()
  
  print(queue)  # 먼저 들어온 순서대로 출력
  queue.reverse()  # 다음 출력을 위해 역순으로 바꾸기
  print(queue)  # 나중에 들어온 원소부터 출력
  
  출력:
  deque([3, 7, 1, 4])
  deque([4, 1, 7, 3])
  

  
  

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

  출처: https://www.geeksforgeeks.org/deque-in-python/

  • deque는 스택과 큐의 장점을 모두 채택한 것이다.

  • 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조이다.

  • list(deque)하면 리스트형으로 자료형이 변환된다.

재귀 함수

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

recursive_function()

출력:
'재귀함수를 호출합니다' 무한 출력

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

• 재귀함수를 호출할 때는 종료 조건을 꼭 명시해야 한다.

• 재귀함수는 스택을 이용해 수행된다.

  • 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

• 스택 자료 구조를 활용해야 하는 경우 DFS와 같이 대부분 재귀함수를 이용해서 간편하게 구현할 수 있다.

• 반복문을 사용하는 것보다 재귀함수를 이용해 로직을 구현할 때 더 간결하게 표현이 가능하다.

해당 글은 다음 도서의 내용을 정리하고 참고한 글임을 밝힙니다. 보다 자세한 내용은 아래 책에서 확인할 수 있습니다. 나동빈, ⌜이것이 취업을 위한 코딩 테스트다 with 파이썬⌟, 한빛미디어, 2020, 604쪽