2장 - 배열

목차

• 1. 추상 데이터 타입과 C++ 클래스
• 2. 추상 데이터 타입으로서의 배열
• 3. 다항식 추상 데이타 타입
• 4. 희소 행렬
• 5. 배열의 표현

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

C++에서는 C언어의 struct 도 사용 가능하지만, 명세와 구현을 구별하고(데이터 추상화), 정보를 은닉(데이터 캡슐화) 하기 위해 class(클래스)라고 하는 명시적인 기법을 제공한다. 

 

class는 아래와 같이 네 부분으로 구성된다.

1. 클래스 이름 : ex) Rectangle
2. 데이터 멤버 : 클래스를 만드는 데이타 ex) xLow, height,... -> priavte 영역에 선언된다(for 데이터 캡슐화)
3. 멤버 함수 : 클래스의 객체에 적용할 수 있는 연산의 집합 ex) GetHeight()...                                                     -> 주로 public 영역에 선언되어 priavte에 선언되어 있는 데이터 멤버에 접근 할 때 사용된다.
4. 프로그램 접근 레벨 : 클래스 외부의 프로그램 코드로부터 데이타 멤버와 멤버 함수에 대한 접근 레벨 제어             -> public(공용), protected(보호), private(전용) 세 가지가 존재한다.

이때 class의 객체 선언은 아래와 같이 한다.

Rectangle r, s; // r, s는 Rectangle의 객체들이다.

Rectangle *t = &s; //t는 클래스 객체 s에 대한 포인터이다.

# 포인터를 통해 클래스 객체의 멤버를 접근하기 위해서는 '->'를 사용한다.

 

생성자

• 데이터 멤버들을 초기화
• public(공용)으로 선언
• 생성자 이름은 클래스 이름과 동일하게 해야 됨

ex) Rectangle::Rectangle (int x,..., int w);

     Rectangle r(1,3,6,6);

     Rectangle *s = new Rectangle(0,0,3,4) //동적 할당을 통해 초기화

 

어떠한 생성자라도 존재하면 컴파일러는 묵시 생성자(기정 생성자)를 생성하지 않는다.

즉, 만약 생성자를 선언하지 않았다면 컴파일러는 기정 생성자를 자동으로 만들어서 사용한다. 하지만 생성자를 선언할 경우 사용자에게 기정 생성자를 선언해야 할 책임이 생기는 것이다.

 

파괴자

• ~ 클래스 이름
• 포인터 변수일 때(동적 할당을 통해 생성했을 때) delete 사용

파괴자는 객체가 없어지기 직전에 데이터 멤버들을 삭제하는 멤버 함수로 생성자와 마찬가지로 선언하지 않아도 클래스는 삭제 되지만 만약 클래스 안의 한 데이타 멤버가 다른 객체에 대한 포인터 변수 라면 그것이 지시하던 객체는 사라지지 않는다는 점을 유의해야 한다.

 

연산자의 다중화

우리가 평소에 사용하는 연산자들을 예로 들면 ==, >, < 등등이 있다. 이때 ==을 예로 들어보자. ==은 동등검사 연산자 인데 int형끼리의 동등을 검사할 때와 float형 끼리의 동등을 검사할 때, 또는 더 나아가 Rectangle class 타입의 객체끼리의 동등을 검사할 때는 각각 연산자 ==을 구현하는 알고리즘은 달라야 한다. 만약 사용자가 미리 정해지지 않은, Rectangle타입의 객체끼리 동등 비교를 요구한다면 컴파일러는 에러를 줄 것이다. 이 때 연산자의 다중화가 필요하다.

 

예제 코드는 아래의 (링크 여기다 넣기)에 작성해 놓았다.

 

2. 추상 데이터 타입으로서의 배열

배열은 <index, value>의 쌍의 집합이다.

추상 데이터 타입으로 나타내 보면 생성자, 반환, 저장 등이 있다. 

 

3. 다항식 추상 데이터 타입

다항식은 지수와 계수(coef, exp) 두 가지로 나눠 배열 형식으로 저장할 수 있다.

다항식을 ADT로 나타내 보면 아래와 같다.

class Polynomial{
public:
	Polynomial(); 
    //생성자, 다항식 p(X)=0 을 생성
    
    Polynomial Add(Polynomial poly);
    //다항식 *this와 poly의 합을 반환
    
    Polynomial Mult(Polynomial Poly);
    //다항식 *this와 poly의 곱을 반환
    
    for Eval(float f);
    //다항식 *this에 f를 대입한 값을 계산하여 그 결과를 반환
}

추상 데이터 타입은 말 그대로 추상적으로 나타낸 코드이다. 이를 직접 구현하고 컴파일하려면 생각보다 쉽지 않다는 것을 알 수 있다. 

다항식의 구현은 아래의 링크에 구현해 놓았다. 

4. 희소 행렬

행렬은 많은 물리적 문제에서 일어나는 수학적 객체라고 한다. 

일반적으로 m개의 행과 n개의 열을 가진 행열을 m by n matrix라 하고 이 행렬은 mn개의 원소를 가진다.

이때 m=n 인 행렬을 정방 행렬(Square Matrix)라고 한다.

 

행렬은 a [m][n]과 같이 주로 2차원 배열로 표현한다. 

이때 m*n개의 원소들 중 많은 수의 원소들이 0이라면 이러한 행렬을 희소 행렬(Sparse Matrix)이라 한다.

희소 행렬을 살펴보는 이유는 평범한 행렬들과 다루는 방식에 차이가 있기 때문이다.

 

수많은 원소 중 대부분이 0이라면 0이 아닌 원소만을 다루기에는 평범하게 다루는 방식은 매우 낭비가 심하다.

예를 들어 1000만 개의 원소중 100개만이 0이 아닌 원소라면 이 행렬을 저장하기 위해 1000만의 메모리 공간과 연산 시 1000만 단위의 시간이 필요하지만, 내가 다뤄야 하는 건 100개의 원소뿐이다.

이러한 희소 행렬의 특정 표현법을 개발하기 위한 ADT를 구현해보면 아래와 같다.

 

class SparseMatrix{
public:
	SparseMatrix(int r,int c,int t);
    //생성자, r행 c열, t개의 0이 아닌 원소를 가진 희소행렬 생성
    
    SparseMatrix Transpose();
    //*this의 모든 3원소 쌍의 행과 열의 값을 서로 교환하여
    //얻은 SparseMatrix 반환(전치 행렬 반환)
    
    SparseMatrix Add(SparseMatrix b);
    //*this행렬과 b행렬을 더할 수 있다면 더한 값을 반환
    //더하지 못한다면(크기가 다르다) 예외 발생
    
    SparseMatrix Multiply(SparseMatrix b);
    //*this행렬과 b행렬을 곱할 수 있다면 곱한 값을 반환
    //곱하지 못한다면 예외 발생
}

희소 행렬의 구현 역시 ADT와 다르게 쉽지 않다. 

희소 행렬의 구현은 아래 링크에 구현해 놓았다

 

5. 배열의 표현

우리는 주로 1,2차원 배열을 사용하지만 n차원의 배열 역시 필요하다.

배열을 표현하는 방법 두 가지를 보자면 행 우선, 열 우선 방법이 있다.

 

행 우선에 대해 예를 들면

a [2][3][2][2]라 할 때,

 

a [0][0][0][0], a [0][0][0][1], a [0][0][1][0], a [0][0][1][1]

a [0][1][0][0], a [0][1][0][1], a [0][1][1][0], a [0][1][1][1]

                                .

                                .

                                .

a [1][2][0][0], a [1][2][0][1], a [1][2][1][0], a [1][2][1][1]

 

위의 예를 통해 배열의 가장 오른쪽 인덱스부터 변하는 것을 알 수 있는데 이를 숫자로 나타내면

0000, 0001,..., 1210,1211 즉 행 우선에 대한 동의어가 사전 순서 임을 알 수 있다.

 

Rectangle, Polynomial 실제 구현 코드 링크

https://github.com/kimtaehyun98/-

kimtaehyun98/-