02_Array & Struct

02_Array & Struct
- C 배열: 08_Arrays & Strings
- C 구조체: 17_struct, union, enum
- 자료구조 배열
- 응용: 희소 행렬, 다항식
06_List
- C 포인터/동적 할당
- 연결 구조: 05_Pointer & Linked Structure
1. 배열 리스트
2. 단순 연결 리스트
3. 이중 연결 리스트

1. Array

1.1. Time Complexity

Array	Search	Best	Average	Worst
Unsorted	Linear Search	$O (1)$	$O (n)$	$O (n)$
Sorted	Binary Search	$O (1)$	$O (lo g n)$	$O (lo g n)$
Sorted	Interpolation Search	$O (1)$	$O (lo g (lo g n))$	$O (n)$

Binary Search의 Best Case는 탐색의 관점에서 $O (1)$ , 탐색 차수의 관점에서 $O (lo g n)$
Interpolation Search는 직선 형태의 균등 분포에서 $O (lo g (lo g n))$ , 불균등 분포에서 $O (n)$
Insert/Delete: $O (n)$

1.2. Features

연속된 메모리 공간에 저장됨
- → Random Access(임의 접근): 빠른 인덱스 접근 가능
- → 메모리 접근 패턴이 일정해 캐시 친화적
(동적 배열 제외) 크기 고정
- → 메모리 낭비 가능성
- → 삽입/삭제 시 데이터 이동 발생 (삽입/삭제가 빈번하면 부적합)

1.3. Applications

기본적인 자료구조 구현
다차원 데이터 처리
인덱스 접근을 활용하는 비디오 프레임 버퍼
자주 변경되지 않는 정적 데이터 저장

1.4. 배열의 탐색

1. 배열의 탐색

2. 구조체

Lab. 희소 행렬 표현

희소 행렬(Sparse Matrix)
- 대부분의 항이 0인 행렬
효율적 표현
- 2차원 배열 전체를 저장하는 대신,
- 0이 아닌 요소만 <행, 열, 값>의 구조체 배열로 저장하여 메모리를 절약

3. 배열과 구조체의 응용 : 다항식 프로그램

3.1. 다항식의 표현 방법

다항식 $p (x) = a_{n} x^{n} + \dots + a_{0}$ 을 컴퓨터로 표현하는 두 가지 방법을 비교

방법 1: 모든 계수 저장 (배열)
- 배열의 **인덱스를 차수(지수)**로, 값을 계수로 사용
- 장점: 구현이 간단함
- 단점: $10 x^{1000} + 1$ 처럼 차수는 높은데 항이 적은 경우, 0인 계수들을 위해 많은 메모리가 낭비됨
방법 2: 0이 아닌 항만 저장 (구조체 배열)
- 구조체에 (계수, 차수) 쌍을 저장하고, 이 구조체들의 배열로 다항식을 표현
- 장점: 희소 다항식의 경우 메모리 공간을 훨씬 절약할 수 있음
- 단점: 덧셈 등의 연산 구현이 방법 1보다 조금 더 복잡함

3.2. 다항식 덧셈 알고리즘

두 다항식 A와 B의 최고차항부터 비교하며 덧셈을 수행하여 새로운 다항식 C를 만든다.
1. A의 차수 > B의 차수: A의 항을 C에 추가
2. A의 차수 < B의 차수: B의 항을 C에 추가
3. A의 차수 == B의 차수: 계수를 더해서 C에 추가 (단, 계수의 합이 0이면 추가하지 않음)