20221012

• 응용 프로그램을 설계할 떄 가장 중요하게 고려해야 할 항목 중 하나는 데이터 관리.
• 응용 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면 적절한 자료 구조(Data Structure)를 선택하는 것이 매우 중요.
• 데이터 조작에 적합한 알고리즘을 선택하는 것 또한 최적의 응용 프로그램 동작을 위해 필수적

---

1장 리스트, 스택, 큐

선형 자료 구조(Linear Data Structure)

시간 복잡도(Time Complexity)

• 시간 복잡도는 특정 작업을 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식입니다.
• 따라서 시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 보여줌.
• 서로 다른 연산의 시간 복잡도는 그 내부에서 데이터를 어떻게 저장하여 사용하는가에 딸 달라집니다.

---

자료 구조는 크게 연속된 자료 구조와 연결된 자료 구조로 구분할 수 있다.

---

연속된 자료 구조

• 연속된 자료 구조(contiguous data structures)는 모든 원소를 단일 메모리 청크(chunk)에 저장합니다.

data[0]	data[1]	data[2]	data[3]
BA	BA+sizeof(type)	BA+2*sizeof(type)	BA+3*sizeof(type

BA = 시작주소

sizeof(type) = 원소 하나에 필요한 메모리 크기

• 해당 표에서 각각의 원소는 모두 같은 타입(type)으로 표시됩니다.
• i번째 원소에 접근하려면 BA + i * sizeof(type) 수식을 사용한다.
• 이러한 자료 구조에서는 배열의 전체 크기에 상관없이 앞서 설명한 수식을 이용하여 모든 원소에 곧바로 접근할 수 있다.
• 따라서 데이터 접근 시간은 항상 일정하다.
• → 이러한 경우에는 **빅오(Big-O) 표기법으로 나타내면 O(1)**으로 표시한다.

---

배열의 유형은 크기 정적 배열(static array)와 동적 배열(dynamic array) 두 가지로 나눌 수 있다.

정적 배열

• 정적 배열은 선언된 블록이 끝나면 소멸된다.

동적 배열

• 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있다.

두가지 유형 중 필요에 따라 적절한 배열을 선택하여 사용하면 된다.

int arr[size]; // 정적 배열
int* arr (int*)malloc(size * sizeof(int)); // C 에서 동적 배열
int* arr = new int[size]; // C++ 동적 배열

정적 배열은 스택(stack) 메모리 영역에 할당되기 때문에 함수를 벗어날 때 자동으로 해제된다.

반면 동적 배열은 힙(heap) 영역에 할당되며 사용자가 직접 해제하기 전까지 유지된다.