일반적으로 추상화는 공통적인 핵심 함수를 사용해 복잡한 시스템을 정의하는 개념이다.
일반적인 자료구조에 추상화개념을 적용한 것이 추상화 자료 유형이다.
추상화 자료 유형은 쓸모 없는 디테일을 숨겨서 사용자가 일반적인 인터페이스를 사용하게 되므로 더 깔끔하고 단순한 코드로 알고리즘을 구현할 수 있다는 장점이 있다.
벡터(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) : 특정한 기중에 맞추어 자식 노드들이 정렬된 트리를 순서 트리라고 한다. 왼쪽부터 오른쪽으로 오름차순으로 정렬된 트리인 경우, 동일한 레벨에 있는 노드들이 가진 값은 왼쪽에서 오른쪽으로 갈수록 증가한다.
반응형
'Python' 카테고리의 다른 글
43. python - 검색 알고리즘 (0) | 2022.11.28 |
---|---|
42. PYTHON - 정렬 알고리즘 (1) | 2022.11.24 |
40. PYTHON - 자료구조 파악하기 (0) | 2022.11.23 |
39.PYTHON - 알고리즘 검증하기 (0) | 2022.11.17 |
38. PYTHON 알고리즘 - 성능 분석하기 (0) | 2022.11.17 |