[파이썬 | 자료구조] 1. 자료구조의 시작

1. 자료구조의 시작

1.1 자료구조의 정의 및 분류

정의

• 데량의 데이터를 효율적으로 관리할 수 있도록 하는 데이터의 구조
• 데이터 특성에 따라서 체계적인 데이터 구조화가 필요
• 데이터 구조에 따라서 효율성, 성능이 결정된다
• 프로그램의 목적 및 기능에 따라서 적은 공간과 적은 시간으로 컴퓨터에 자료를 저장하는 방식

분류

1. 단순구조 : 프로그램(언어)에서 제공하는 기본 데이터 타입
2. 선형구조 : 자료들 사이 앞뒤 관계가 1대1 구조
3. 비선형구조 : 자료들 사이 앞 뒤 관계가 계층 혹은 망구조
4. 파일구조 : 보조기억장치에 저장

1.2 추상자료형

정의

기능의 구현 부분을 나타내지 않고, 순수한 기능이 무엇인지 나열한 것을 추상 자료형이라고 한다.

추상 자료형의 필요성

추상 자료형은 구현자와 사용자를 분리해 준다. 라이브러리를 가져다 쓰거나 내장 함수를 사용하는 것도 추상 자료형이 정의되어 있기 때문이다. 또한 추상 자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉 (Information Hiding)이 이루어지게 된다.

정리

사용자는 내부 구현이 어떻게 되어 있는지 알 필요가 없다. 추상 자료형을 보고 목적에 맞게 가져다 사용하면 되는 것이다. 구현자 입장에서는 구현을 위한 기능과 데이터 집합을 나열하는 것이다.

다음 포스팅들에서 자료구조를 구현하게 될텐데, 구현 자료구조의 추상 자료형을 정의하고 시작하게 될 것이다. 정의된 추상 자료형으로 main 함수를 정의해 보고, 추상 자료형을 구현해 볼 것이다.

추상 자료형은 정해진 것이 아니다. 많이 사용되고 있는 형태들은 있지만 자신의 구현 목적에 따라서 추상 자료형은 얼마든 달라질 수 있다.

1.3 알고리즘과 자료구조의 관계

알고리즘의 성능은 자료구조에 종속된다. 즉 효과적인 알고리즘을 위해서는 효과적인 자료구조가 필요하다.

1.4 빅오표기법

시간복잡도의 함수중에서 최고차항만을 표기한다.

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n ^ 2)
6. O(n ^ 3)
7. O(2 ^ n)
8. O(n!)