Chapter 2. Arrays

1. 추상 데이터 타입과 C++ 클래스

1. C++ 클래스

1. 구성
   - 클래스이름
   - 데이터멤버
   - 멤버함수
   - 프로그램 접근 레벨 (public, protected, private)

2. 데이터의 추상화와 캡슐화 (Data Abstraction & Encapsulation)
   - private 또는 protected로 데이터를 선언함으로써 data encapsulation이 가능
   - 필요에 따라 외부에서 데이터를 접근하고자할 때는 Get###() 함수를 쓴다.
   - 외부에서 접근할 때 쓰는 함수는 public으로 하고 그외엔 private/protected 사용

3. 클래스 객체 선언과 멤버 함수의 접근
   (Declaring Class objects and invoking member functions)
   -  class object에 직접 접근 : .
   -  class object에 간접 접근 : -> (포인터이용)

4. 특별한 클래스 기능 (Special Class Oprations)
   - Constructor / Destructor
   - Operator overloading : 동일한 함수이름에 인자를 달리하여 다른 함수로 인식
    (참고)
    Overriding : 상속받은 메소드를 재정의 함으로서 상위클래스와 다른 역할 수행

5. 기타 사소한 거
   - C++ 에서는 struct와 class가 동일하지만, 기본 접근 레벨이 다르다.
     (struct에서는 기본 public / class에서는 기본 private)
   

2. The Arrays as an Abstract data type (추상 데이터 타입의 배열)
   - 클래스 내에 모든 함수가 원형만 존재
   

3. Polynomial Abstract data type
   - 배열을 통한 Abstract data type 구현.

1. Polynomial Representation (다항식 표현)
   방법1. polynomial에 대한 전용 데이터 멤버 정의 (차수배열과 계수 배열)
   방법2. 방법1에서 계수 배열을 pointer化
   방법3. 추가 정의 --- 0이 아닌 항에 대한 정보

2. Polynomial Addtion
   

4. Sparse Maxtrix (희소행렬)

1. Introduction
   - 희소행렬 : 많은 항들이 0인 행렬
   - 0이 아닌 원소만 저장하는 표현 방법을 사용한다면 시간과 공간을 절약할 수 있음
   

2. Representation
   - 기본적인 정보 : 행, 열, 0이 아닌 항 개수 <3원소쌍>
   -  행 순서로 저장, 열 인덱스가 오름차순이 되도록

3. Transposing
   - 전치 : 행렬의 [i][j]에 있는 값을 [j][i]의 값과 바꿈
   - i = j 인 경우 대각선 위의 원소 변경 없음
   - 전치 후의 원소를 저장할 때, 저장할 위치를 알기 어려움.
   - 열 순서로 저장, 행 인덱스가 오름차순이 되도록!

4. Multiplication
   - 희소 행렬의 곱은 더이상 희소행렬이 아닐 수 있음

5. Representation Of Arrays
   - 행우선으로 저장 (= 사전순서 (lexicographic order))

6. The String Abstract data type

1. 문자열 패턴 매치
   알고리즘 1: brute-force
   알고리즘 2: KMP알고리즘