Python

41. PYTHON - 추상화 자료 유형 파악하기

ITSEONG 2022. 11. 23. 18:21

일반적으로 추상화는 공통적인 핵심 함수를 사용해 복잡한 시스템을 정의하는 개념이다.

일반적인 자료구조에 추상화개념을 적용한 것이 추상화 자료 유형이다.

추상화 자료 유형은 쓸모 없는 디테일을 숨겨서 사용자가 일반적인 인터페이스를 사용하게 되므로 더 깔끔하고 단순한 코드로 알고리즘을 구현할 수 있다는 장점이 있다.

 

벡터(Vector)

벡터는 데이터를 저장하는 일차원 자료 구조이다. 파이썬에서 제공하는 여러 자료 구조 중 가장 인기가 많다.

  • 벡터 생성방법
  • 파이썬의 리스트 사용하기 : 가장 손쉬운 방법이다.

  • numpy 배열 사용하기 : 벡터를 생성하는 또 다른 방법은 numpy 배열을 사용하는 것입니다.

스택

스택은 일차원 리스트를 저장하는 선형 자료구조이다. 스택은 저장할 요소들을 후입 선출 또는 선입 후출 방식으로 다룰 수 있다.

  • 스택과 관련된 연산
  • isEmpty : 스택이 비어있다면 True를 반환한다.
  • push : 새 요소를 스택에 추가한다.
  • pop : 최근에 추가한 요소를 스택에서 제거하고 이를 반환합니다.

스택의 시간 복잡도

빅오 표기법을 이용해 스택이 사용하는 연산의 시간 복잡도는

연산작업 시간복잡도
push O(1)
pop O(1)
size O(1)
peek O(1)

size는 스택이 담고 있는 요소의 개수를 반환하며, peek는 스택의 맨 위에 위치한 아이템을 삭제하지 않고 접근한다. 위 네 가지 연산의 기능은 스택 크기에 좌우되지 않는다.

 

활용사례 : 실행 취소 기능은 스택을 사용하는 예이다.

 

스택과 마찬가지로 큐도 n개의 요소를 저장하는 일차원 자료구조이다. 요소는 선입선출 형식으로 추가되고 제거된다.

트리

알고리즘에서 트리는 계층적 데이터를 저장할 수 있는 기능 때문에 유용한 자료 구조중 하나이다.

알고리즘을 설계하는 동안 우리는 저장하거나 처리해야 하는 데이터 요소 사이의 계층 관계를 표현하는데 필요한 모든 곳에서 트리를 사용한다.

 

  • 트리의 유형 
  • 이진트리(binary tree) : 트리의 최대 차수가 2인 트리를 이진트리라고 한다. 
  • 정 트리(full tree) : 정 트리의 노드들은 모두 같은 레벨을 가진다. 즉 노드의 차수와 트리의 차수가 동일하다.
  • 포화 트리(perfect tree) : 포화 트리는 정 트리의 특수 형태로 모든 리프 노드가 동일한 레벨을 가진다. 
  • 순서 트리(ordered tree) : 특정한 기중에 맞추어 자식 노드들이 정렬된 트리를 순서 트리라고 한다. 왼쪽부터 오른쪽으로 오름차순으로 정렬된 트리인 경우, 동일한 레벨에 있는 노드들이 가진 값은 왼쪽에서 오른쪽으로 갈수록 증가한다.
반응형