1비트를 하나의 전구 라고 생각하자. 전구의 상태는 ON,OFF 두가지만 존재한다 ON = 1 , OFF = 0 으로 가정하면 1비트(전구 하나)를 통해 표현할수 있는 경우의 수는 2가지 이다 용량이 아닌 표현의 최소 단위이다

2. 4비트

4비트 전구가 4개인 상태를 살펴보자 다음과 같은 4개의 전구를 통해 특정한 2진수를 만들었다 2진수 0101을 10진수로 바꾸기 이전에 10진수에 수의 표현 방식을 살펴보자

1비트는 용량의 최소단위로 사용된다

2.1 10진수 표현법

우리가 흔히 사용하는 진법은 10진법이다 예를 들어 1232라는 숫자를 통해 10진법을 알아보자 1232는 크게 천의자리,백의자리 십의자리 ,일의 자리로 나뉜다 이것을 수식으로 표현하면 2진수도 똑같이 각각의 자리수에 값을 곱해서 더하는 방식으로 10진수로 변환할 수 있다

2.2 2진수 => 10진수

그림1 에서 나온 0101을 10진수로 바꿔보자

3. 1바이트

1바이트는 8개의 비트의 묶음이다

1byte = 8bit 그렇기에 1바이트는 2^8 = 256가지의 경우를 가진다 1바이트는 영문 1글자를 저장할수 있는 메모리 크기이다 (한글은 1글자에 2바이트가 필요한데 한글과 영문의 글자수가 다르기떄문)

1GB(기가 바이트)는 2^30바이트 이다 또한 단위 체계가 2^10을 기준으로 분류된다

as는 별칭으로 열의 별명 이다

2.INNER JOIN

기본적으로 JOIN은 벤다이어 그램 이다. 테이블의 공통 부분을 합쳐준다

3.FULL OUTER JOIN

FULL OUTER JOIN은 테이블의 데이터를 합쳐버린다 만일 한쪽 테이블에만 존재하는 데이터가 있을경우 반대편에는 NULL을 채워넣어 버린다

4.LEFT OUTER JOIN ,RIGHT OUTER JOIN

여기서 조금 더 생각해 보자 이럴 경우 테이블 A에만 존재하는 레코드만 출력할수 있다

5.UNION

유니온은 단순히 두 테이블의 값을 더하는 것이다 FULL OUTER JOIN 같은 벤다이어그램이 아닌 단순히 상자 2개를 쌓는 것이다

1_1. Min

열에서 제일 작은 값을 출력 해주는 집계 함수

1_2. Max

열에서 제일 큰 값을 출력 해주는 집계 함수

1_3. Avg

열에서 평균 값을 출력 해주는 집계 함수

1_4. Round

열에서 반올림 해주는 집계 함수

1_5. Sum

열에서 평균 값을 더하기 출력 해주는 집계 함수

GROUP BY

GROUP BY 절은 특정 열의 값에 따라 데이터를 그룹화 한다 그룹화된 데이터에 대해 집계 함수를 사용하여 결과를 계산할 수 있다 주로 집계 작업에 사용되며, 집계 함수를 사용하여 그룹화된 데이터의 통계를 계산한다

Having

그룹화된 데이터 중에서 특정 집계 결과를 가진 그룹을 선택하려면 HAVING 절을 사용한다 HAVING 절은 GROUP BY 절 다음에 나오며, 그룹화된 데이터에 대한 조건을 검사한다

SELECT는 테이블에 원하는 열을 불러온다

1_1 문법

SELECT 열_이름 FROM 테이블 이름

1번 그림 처럼 원하는 테이블에 이름과 테이블에 열이름을 통해 데이터에를 조회 가능하다

테이블의 모든 열을 조회하고 싶다면 별표 기호를 사용하면 된다

2. SELECT DISTINCT

2_1 문법

SELECT DISTINCT 열_이름 FROM 테이블 이름

DISTINCT는 열에서 중복값을 처리할떄 사용한다 고유한 값의 종류를 알고 싶을때 사용한다

3. COUNT

3_1 문법

SELECT COUNT (열_이름) FROM 테이블 이름

열에 갯수를 알려준다

5번 같이 DISTINCT와 COUNT를 이용해 값의 종류 값을 알수있다

4. SELECT WHERE

4_1 문법

SELECT DISTINCT 열_이름 FROM 테이블 이름

AND말고도 OR,NOT이 존재한다

5. ORDER BY

5_1 문법

SELECT DISTINCT 열_이름 FROM 테이블 이름
ORDER By 열_이름 ASC ,(혹은 DESC) // ASC 오름차순 DESC 내림차순

데이터를 정렬한다

6. LIMIT

6_1 문법

SELECT DISTINCT 열_이름 FROM 테이블 이름
LIMIT 숫자

출력할 데이터 갯수를 정할 수 있다

7. BETWEEN

7_1 주의

SELECT * FROM payment
WHERE payment_date BETWEEN '2007-02-14' AND '2007-02-15'

특정 기간내에 검색을 할때에는 범위에 신경써야 한다 sql에서 2007-02-15 같은 경우 2007년 2월 15일 00시 00분 00 초가 기준이다 그렇기에 기간검색은 신경쓰자

8. IN, NOT IN

8_1 문법

SELECT  열_이름 FROM 테이블 이름
WHERE 열_이름 IN (데이터)

특정 값을 지닌 열을 출력해 준다

9. LIKE, ILIKE

SELECT * From 테이블 WHERE 열 LIKE '패턴'

패턴에는 %,가 존재한다 %는 '모든 문자' _는 '한 글자' 

-** 1. 가상함수** -** 2. 가상함수 테이블**

1.가상함수

1_1.가상함수 기본 문법

가상함수는 virtual 예약어를 앞에 붙여서 선언한 메서드를 말한다 가상함수는 기본적 으로 자기부정을 전제로 작동 한다. 자기부정 이란 파생형식에서 virtual로 정의한 메서드를 재정의하면 과거의 정의가 완전히 무시 된다

virtual 반환형식 메서드이름;

예시

virtual void PrintData();

1_2.가상함수의 호출

코드를 보며 이야기 해보자

using namespace  std;;

class MyData
{
public:

    virtual void PrintData()
    {
        cout << "MyData(기본형식): " << m_nData << endl;
    }

    void TestFunc()
    {
        cout << "****TestFunc****" << endl;

        PrintData();
        cout << "**********" << endl;
    }

protected:
    int m_nData = 10;
};

class MyData_Ex : public MyData
{
public:
    virtual void PrintData()
    {
        cout << "MyData(파생):" << m_nData * 2 << endl;
    }

private:

};

//사용자코드
int main(void)
{
    MyData_Ex a;

    a.PrintData();

    MyData& b = a;

    b.PrintData();

    a.TestFunc();

    return 0;
}

출력결과 MyData(파생):20 MyData(파생):20 TestFunc MyData(파생):20

사용자 코드에서 3가지 경우에 대해 생각해 보자

1.파생 클래스 인스턴스 에서 재정의 메서드를 호출 하는 경우 첫 번쨰로 생각 해볼것은 실형식이다 virtual 메서드는 실 형식을 따르기 떄문이다 당연히 파생 형식을 따르므로 파생 클래스의 PrintData()가 호출된다.

2.참조 형식이 기본 클래스, 실 형식이 파생 클래스인 경우 역시 생각 해볼 것은 실형식이 무엇인지다 MyData& b = a 여기서 참조 형식은 MyData 지만 실형식은 MyDataEx 다 그렇기에 역시 실형식인 파생 클래스의 PrintData()가 호출된다

3.파생클래스에서 기본 클래스 메서를 호출할때 기본클래스 메서드 안에 virtual 메서드를 호출 하는 경우 a.TestFunc()를 호출하면 기본 클래스에 TestFunc()메서드를 호출한다 그러면 TestFunc() 메서드안에 Virtual PrintData()메서드를 호출하는데 이경우 호출되는 PrintData()메서드는 실 형식(파생 클래스)을 따라 정의 된 PrintData()메서드를 호출한다. 조금 더 생각해보자 기본 클래스에서 TestFunc()메서드에서 virtual메서드를 호출하는것을 시간의관점에서 생각해보면 PrintData()를 기본 클래스에서 정의 할때는 분명히 과거에 일이다 하지만 호출되는 PrintData()는 기본클래스 입장에서 미래에 일이다

즉 가상 함수는 호출하는 것이 아니라 호출 되는 것으로 이것은 called by frameWork 라고 한다.

1_3.소멸자 가상화.

기본적으로 클래스 기본 형식에 대한 포인터를 통해 파생 클래스 인스턴스를 참조할 수 있다.

MyData *pData =  new MyData_Ex;

이렇게 파생클래스를 이용해 동적 생성한 객체를 참조할 때 메모리 누수 문제가 발생할수 있다 코드를 통해 살펴보자

class MyData
{
public:
    MyData()
    {
        m_pszData = new char[32];
    }

    ~MyData()
    {
        cout << "기본 클래스 소멸자 호출!!" << endl;
        delete m_pszData;
    }
private:
    char* m_pszData;
};

class MyData_Ex : public MyData
{
public:
    MyData_Ex()
    {
        m_pnData = new int;
    }

    ~MyData_Ex()
    {
        cout << "파생 클래스 소멸자 호출" << endl;
        delete m_pnData;
    }

private:
    int* m_pnData;
};

//사용자코드
int main(void)
{
    MyData* pData = new MyData_Ex;

    delete pData;

    return 0;
}

출력결과 기본 클래스 생성자 호출 파생 클래스 생성자 호출 파생 클래스 소멸자 호출

위 코드에서 사용자 코드에서 delete 연산을 실행하면 참조형식에 소멸자만 호출되고 실 형식의 소멸자가 호출되지 않는다!!. 생성자는 일반 메서드 => 일반 메서드는 참조형식을 Virtual은 실 형식을 따른다

이문제를 해결하기 위해서 소멸자 가상화를 해야한다

virtual ~MyData()
    {
        cout << "기본 클래스 소멸자 호출!!" << endl;
        delete m_pszData;
    }

출력결과 기본 클래스 생성자 호출 파생 클래스 생성자 호출 파생 클래스 소멸자 호출 기본 클래스 소멸자 호출 !!

3.순수 가상 클래스

3_1.순수 가상 클래스 특징

순수 가상 클래스는 "순수 가상 함수"를 멤버로 가진 클래스를 의미한다

virtual int GetData() const = 0;

순수 가상 함수는 선언은 미리 해두지만 정의는 미래에 하도록 미뤄둔 함수다. 순수 가상 함수는 반드시 파생 클래스 에서 재정의 해야한다. 또한 순수 가상 클래스 인스턴스를 선언하거나 동적으로 생성할수없다

//초기 개발자
class MyInterface
{
public:
    MyInterface()
    {
        cout << "MyInterface()" << endl;
    }

    virtual int GetData() const = 0;
    virtual void SetData(int nParam)  = 0;

};

//후기 개발자
class MyData :public MyInterface
{
public:
    MyData()
    {
        cout << "MyData()" << endl;


    }

    virtual int GetData() const
    {
        return m_nData;
    }

    virtual void SetData(int nParam)
    {
        m_nData = nParam;
    }
private:
    int m_nData = 0;
};




//사용자코드
int main(void)
{
    MyData a;
    a.SetData(5);
    cout << a.GetData() << endl;

    return 0;
}

출력결과 MyInterface() MyData() 5

파생 클래스 인스턴스를 생성하니 호출자 순서에 의해서 기본 클래스 -> 파생 클래스 순으로 호출 된것을 볼수 있다 . 그리고 virtual 메서드는 실형식을 따르므로 실형식인 파생 클래스의 재정의된 메서드가 호출 되고 실행 된것을 확인 할 수있다

3_2.순수 가상 메서드의 활용

순수가상메서드의 특징은 어렵지 않게 정리할 수 있었다 그렇다면 왜?순수 가상 메서드를 이용하는지에 대해 이야기 해보자 예시를 들기위해 잠깐 컴퓨터와 USB에 대해 이야기 해보겠다 대부분의 컴퓨터는 USB를 인식할 수 있는 인터페이스를 지니고 있다. 왜 USB 인터페이스를 컴퓨터가 가지고 있을까? USB 인터페이스를 만들어서 다른 기기들과에 연결을 하기 위해서 인터페이스를 구축한다. 즉 다른 장치와 상호작용을 위해 가장 보편적인 인터페이스를 구축한다 이 논리를 객체지향 프로그래밍에 적용해 보자

//초기 개발자
class MyObject
{
public:
    MyObject()
    {

    }
    virtual ~MyObject()
    {

    }

    virtual int GetDeviceID() = 0;

protected:
    int m_nDevice;
};

//초기 개발자가 만든 함수
void PrintID( MyObject *pobj)
{
    cout << "Device ID:" << pobj->GetDeviceID() << endl;
}

//후기 개발자가 만든 클래스
class MyTv : public MyObject
{
public:
    MyTv(int nID)
    {
        m_nDevice = nID;
    }

    virtual int GetDeviceID()
    {
        cout << "MyTV::GetDeviceID()" << endl;
        return m_nDevice;
    }

};

class MyPhone : public MyObject
{
public:
    MyPhone(int nID)
    {
        m_nDevice = nID;
    }

    virtual int GetDeviceID()
    {
        cout << "Myphone::GetDeviceID()" << endl;
        return m_nDevice;
    }

private:

};



//사용자코드
int main(void)
{
    MyTv a(5);
    MyPhone b(10);

    ::PrintID(&a);
    ::PrintID(&b);

    return 0;
}

다음 코드에서 MyObject 클래스는 추상클래스 이다 추상 클래스는 그자체를 인스턴스로 만들수 없다 말그대로 추상이기 떄문이다 하지만 추상메서드를 상속받아 만든 phone,tv는 각각의 인스턴스를 만들고 인스턴스의 주소를 넘겨 각각의 PrintID()의 실인수로서 작동하게 한다 즉** 가상 함수는 추상 자료형으로 참조 하더라도 언제나 실 형식을 메서드가 호출 될수 있다**

• 1.상속
• 2.재정의
• 3.생성자 소멸자

1.상속

1_1 상속이란

상속은 3가지 관점에서 정의 할 수 있다. 1.코드를 재사용 하는 방법 2.규모의 확장 3.관계의 한가지 유형

객체지향 프로그래밍에서 개발자는 유지보수 를 최대한 신경 써야한다 그점에서 상속은 미래에 개발을 진행할 개발자를 위해서 라도 제대로 규정해야 한다

1_2 상속의 기본 문법

상속은 다음과 같이 코드를 작성한다

class 파생클래스이름 : 접근제어지시자 부모클래스 이름

예를 들어 다음과 같이 작성할수 있다

class MyDataEx : public MyData

이제부터 상속의 특징을 공부하고 코드를 통해 어떻게 실행되는지 살펴보자 먼저 3가지 특징을 알고 가자 1.파생 클래스의 인스턴스가 생성될 떄 기본 클래스의 생성자도 호출 된다 2.파생 클래스는 기본 클래스의 멤버에 접근 가능하다.단 Private 선언된 클래스 멤버는 접근 불가 3.사용자 코드에서는 파생 클래스의 인스턴스를 통해 기본 클래스 메서드 호출이 가능하다

실제 코드와 출력 결과를 통해 알아보자

//초기 개발
class MyData
{
public:
    MyData()
    {
        cout << "MyData()" << endl;
    }

    ~MyData()
    {

    }

    int GetData()
    {
        return m_nData;
    }

    void SetData(int nParam)
    {
        m_nData = nParam;
    }


protected:
    void PrintData()
    {
        cout << "MyData::PrintData()" << endl;
    }
private:
    int m_nData = 0;
};

//상속 클래스
class MyDataEx : public MyData
{
public:
    MyDataEx()
    {
        cout << "MyDataEx()" << endl;
    }
    ~MyDataEx()
    {

    }

    void TestFunc()
    {
        PrintData();
        SetData(5);
        cout << MyData::GetData() << endl;
    }

private:

};




//사용자 코드
int main(void)
{
    MyDataEx data;

    //기본  클래스(MyData) 멤버의 접근
    data.SetData(10);
    cout << data.GetData() << endl;

    //파생 클래스(MyDataEx) 멤버의 접근
    data.TestFunc();
    return 0;
}

** 출력결과** MyData() MyDataEx() 10 MyData::PrintData() 5

출력결과 에서 MyData클래스의 생성자(기본 클래스 생성자)가 호출 된것이다 출력 결과를 보면 기본 클래스 생성자가 파생 클래스 생성자 보다 먼저 호출 된것으로 보이지만 파생 클래스 생성자가 먼저 호출되지만 실행이 나중에 되버린다.

이러한 동작 과정 때문에 우리가 한 가지 주의 해야 하는게 있다 부모형식 멤버를 파생 형식 생성자 에서 절대 초기화 하면 아니 된다 오직 생성자는 객체 자신을 초기화 해야한다

data.SetData(10);, data.TestFunc(); 코드 같은 경우 파생 클래스에 직접적으로 상위 클래스의 private멤버의 접근 할 수 없지만 위와 같이 메서드를 통해 접근이 가능하다

2.메서드 재정의

2_1 메서드 재정의 개념

메서드 재정의는 오버라이드 라고도 불린다. 기본적으로 재정의는 기존의 것을 무시 한다 기존 클래스 메서드를 새롭게 대체 한다고 생각하면 된다

2_2 메서드 재정의 문법과 특징

//초기 개발
class MyData
{
public:
    MyData()
    {
    }

    ~MyData()
    {

    }

    int GetData()
    {
        return m_nData;
    }

    void SetData(int nParam)
    {
        m_nData = nParam;
    }

private:
    int m_nData = 0;
};

//상속 클래스
class MyDataEx : public MyData
{
public:
    MyDataEx()
    {
    }
    ~MyDataEx()
    {

    }

    void SetData(int nParam)
    {
        if (nParam < 0)
            MyData::SetData(0);
        if (nParam > 10)
            MyData::SetData(10);
    }

private:

};




//사용자 코드
int main(void)
{
    MyData data;

    MyDataEx data_new;

    data.SetData(15);
    data_new.SetData(15);

    cout << data.GetData() << endl;
    cout << data_new.GetData() << endl;
    return 0;
}

출력결과 15 10

기본 클래스 에서 SetData를 정의했다 그리고 파생 클래스 에서 SetData를 재정의 했다 사용자 코드에 기존 클래스 인스턴스의 메서드랑 파생 클래스 인스턴스의 메서드는 이름은 같지만 정의가 다르기 떄문에 당연히 출력 값이 다른게 보인다. 우리는 여기서 조금 더 생각을 확장해 보자 일단 파생 클래스의 SetData를 다음처럼 바꾸면 어떻게 될까?

    //바꾸기 전
    void SetData(int nParam)
    {
        if (nParam < 0)
            MyData::SetData(0);
        if (nParam > 10)
            MyData::SetData(10);
    }

    //바꾼 후
    void SetData(int nParam)
    {
        if (nParam < 0)
            SetData(0);
        if (nParam > 10)
            SetData(10);
    }

위와 같이 소속 클래스 명시를 하지 않으면 기본적 으로 아래 함수는 재귀호출 함수가 되버린다. 그렇기에 ** 파생 형식에서 기본 형식의 동일 메서드를 호출하려면 소속 클래스를 명시하자 **

2_3 참조형식과 실 형식

앞서 코드에서 사용자 코드를 조금 변경 하겠다

//사용자 코드
int main(void)
{
    MyDataEx data;

    MyData &rdata = data;

    rdata.SetData(15);
    cout << data.GetData() << endl;
    return 0;
}

출력결과 15

MyDataEx를 MyData 형식으로 참조 했다. 파생형식을 기본형식 으로 참조하는 것은 가능하다 여기서 중요한 건 출력 값 15이다 값이 15가 나왔다는 것은 기본 클래스의 SetData가 호출되었다는 것을 의미한다. 메서드가 호출되는 기준은 다음과 같다 1.메서드가 일반 =>접근형식 2.메서드가 Virtual => 실형식 즉 접근형식이 기본 클래스 이므로 파생 클래스를 참조 했다고 하나 접근형식을 따라서 메서드가 호출된다

참고로 포인터 참조를 통해서도 호출이 가능하다

//사용자 코드
int main(void)
{
    MyData *pclass = new MyDataEx;
    pclass ->SetData(15);


    cout << pclass->GetData() << endl;
    delete pclass;
    return 0;
}

3.상속에서의 생성자 소멸자

3_1 생성자 소멸자 호출

앞서 잠깐 생성자에 호출과 실행 순서에 대해서 알아봤는데 여기서 조금 더 구체적으로 살펴보자 다음과 같은 상속관계가 있다고 생각해 보자. 생성자와 소멸자의 관계는 다음 같다

1.C클래스 인스턴스를 선언하면 생성자 호출 순서는 C,B,A 이다 2.하지만 가장 먼저 실행되는 생성자는 C가 아니라 A다 3.C클래스 인스턴스가 소멸하면 C 클래스의 소멸자가 가장 먼저 호출되고 실행된다 4.즉 생성자는 호출과 실행 순서가 역순이고 소멸자는 같다

• 1.연산자 다중 정의를 하는 목적
• *2.연산자 함수의 활용 *

1.연산자 다중 정의

c++ 개발자는 기본적으로 사용자에 입장에서 코드를 작성해야 한다. 사용자가 사용하기 쉬운 코드는 추상성,직관성,편리성이 높은 코드를 의미한다 다음 코드를 보자

    MyClass a;
    a.Append(3, int);

    MyClass a;
    a += 3; 

둘다 기존 a에 3을 추가하는 내용이지만 사용자 입장에서는 두 코드의 난이도는 다르다. 그렇기에 우리는 사용자가 더욱 잘 소프트웨어를 사용할수 있게 클래스의 연산자 다중 정의를 통해 여러 기능을 제공해야 한다

2.연산자 함수 활용

연산자 함수는 연산자를 호출할 수 있는 메서드 이다 기본적인 예시 코드를 살펴보자

class CMyData
{
public:
    CMyData()
    {

    }

    CMyData(int number)
        :m_nData(number)
    {

    }
    ~CMyData()
    {

    }

    operator int()
    {
        return m_nData;
    }

    int operator+(CMyData rhs)
    {
        this->m_nData = this->m_nData + rhs.m_nData;
        return m_nData;
    }

    void operator=(int nParam)
    {
        m_nData = nParam;
    }

private:
    int m_nData = 0;
};


//사용자 코드
int main(void)
{
    CMyData a(3);
    CMyData b(4);

    CMyData c;
    c = a + b;

    cout << c << endl;

    c = 4 ;

    cout << c << endl;
}

출력결과 7 4

앞서 코드에서 중요하게 봐야할 부분은 c = a+b , c=4 ** 부분이다 두 코드는 사용자 입장에서 연산자 처럼 보이지만 정확히 *함수 *이다. 그렇기에 기본 연산으로 만든 함수는 절대로 **실패 해서는 안된다. 그렇기에 사용자에 맞춰 예외처리 등이 필요하다.

여기서 생각을 조금 더 확장해 보자

만약 다음처럼 코드 작성되면 어떻게 될까?

a = b = 5;

당연히 오류가 발생한다 b = 5는 우리가 int 값을 매계변수 로 받는 연산자를 정의했지만 a = b 는 클래스를 매계변수로 하는 연산자를 정의하지 않았다. 그러면 위에 문제를 해결하는 방법에 대해 알아보자

첫번쨰로 int 값을 반환하도록 연산자를 정의하는것이다

void operator=(int nParam)
    {
        m_nData = nParam;
    }

*기존코드 *

int operator=(int nParam)
    {
        m_nData = nParam;
        return m_nData;
    }

바뀐 코드

이렇게 바꾸면 정상적으로 출력이 되는것을 확인할수 있다. 하지만 이러한 방식에도 문제점이 존재한다 b=5까지는 정상적으로 연산자를 진행하면 된다 하지만 b=5가 반환하는 값은 int다 그렇다면 a=b는 엄연히 클래스대 클래스 연산인데 int반환 연산자로 호출이 된다.

그렇기에 연산자를 하나더 정의 하자

CMyData operator=(CMyData rhs)
    {
        m_nData = rhs.m_nData;
        return m_nData;

    }

클래스 반환 연산자

이렇게 바꾸면 b=5는 int형 연산자로 a=b는 클래스형 연산자로 제대로 작동한다 하지만 여기서 임시객체 문제를 마주하게 된다 클래스 반환 연산자를 살펴 보면 기본적으로 클래스 인스턴스를 2개를 임시객체로 만든다 (매개변수로 받은 rhs 1개 , return 으로 만드는 클래스 1개) 임시객체는 성능저하에 원인으로 지금부터 임시객체 문제 해결을 위해 2가지를 바꿔보자

-** 1.함수의 매개변수가 클래스인 경우 무조건 참조로 받는 것이 좋다**

CMyData operator=(const CMyData& rhs)
    {
        m_nData = rhs.m_nData;
        return m_nData;

    }

함수의 매개변수 클래스를 참조형으로 받으면 불필요한 임시객체를 만들지 않아도 된다. 참고로 참조형으로 받을떄 const도 세트로 붙여주자 !!

• 2.참조 반환을 이용하자

  CMyData& operator=(const CMyData& rhs)
    {
        m_nData = rhs.m_nData;
        return *this;
  
    }

  우리가 대입을 하기위해서 operatro=에 복사본을 만든 다음에 대입을 할필요가 없다. 기본적으로 operator= 자체를 참조 반환을 통해 인스턴스를 줄일 수 있다

• 임시객체
• r참조
• 이동 생성자

1.임시객체

1-1.임시 객체란?

임시 객체는 식별자가 부여되지 않은 객체를 의미한다 이름이 없는 객체로서 코드 형태에서 직접적으로 확인 하기는 어렵다 간단한 그림을 통해 임시 객체를 알아보자 int a를 선언과 동시에 초기화 하는 단순한 상황이다 임시객체를 알기 전까지 저 과정에서 int형 인스턴스는 a,3,4 총3개이다 하지만 실제로 더하는 과정에서 3,4에 연산 결과인 7이 임시객체로 생성된다.

1_2.임시객체의 생명주기

위에 그림에서 임시객체 7은 언제 생성되고 소멸 될까? 3+4 연산이 진행될때 생성되고 7을 a에 대입하고 소멸할 것이다 생성될때 호출 연산의 끝에서 소멸을 한다.

1_3.임시객체의 문제점

임시객체가 생성되면 내가 모르는 인스턴스가 생성 되는것이다 인스턴스가 생성이 되면 당연히 메모리와 성능에도 영향을 주게된다 임시객체를 고려하지 않고 설계를 한다면 위에 상황은 분명 60MB다 하지만 임시객체로 인해 최대 80MB까지 올라가게 된다

2.R_vlue 참조

이러한 문제를 해결하는 방법으로 r_vlue참조가 있다 형식앞에 &&붙여서 참조하는 형태로 상수형 참조이다 그렇기에 연산의 결과값을 참조하기 위해 사용한다.

예를 들어 위에 그림에서 T_1을 참조해서 연산을 진행한다면 임시객체 T_1을 생성할 필요없이 프로그래밍을 만들수 있다

2_2 r-vlue참조 사용하기

r참조는 연산에 따라 생성된 임시객체 입니다 라고 생각하자 우리가 앞서 매개변수 형식이 클래스을 경우 참조형식을 활용하라고 한것처럼 외우자

    int&& data = 3 + 4;
    int data2 = 3 + 4;

    cout << data << endl;
    cout << data2 << endl;

출력결과 7 7

int&& data =7 이랑 다를게 없다 하지만 클래스를 매개변수로 할경우 r참조를 활용하면 불필요한 임시객체를 줄일수 있다 이동 생성자를 통해 더욱 알아보자

3.이동 생성자

1_1 이동생성자란?

우리가 복사생성자를 선언할떄 매개변수에 l참조 형식으로 &을 붙여서 선언했다면 이동생성자는 &&을 붙여 r참조를 통해 선언한다. 복사 생성자가 클래스 멤버 안에 포인터의 값 자체를 복사하는 생성자라면 이동 생성자는 매개변수 클래스의 포인터의 주소만 복사하는 방식으로 메모리를 절약한다

• 1.복사 생성자
• 2.깊은 복사와 얕은 복사

1.복사 생성자

1.1복사 생성자

복사 생성자는 객체의 복사본을 생성할 떄 호출되는 생성자다 복사 생성자는 기본적으로 컴파일러가 알아서 만든다 그렇기에 필요한 경우가 아니라면 만들 필요가 없다 하지만 필요한 경우에 만들지 않으면 대참사가 발생한다 필요한 경우란 *클래스 내부에서 메모리를 동적 할당 및 해제하고 이를 멤버 포인터 변수로 관리하는 경우이다 * 말이 굉장히 어렵다 쉽게 쉽게 설명해 보겠다

복사 생성자의 문법은 간단하다 클래스이름(const 클래스이름& rhs); 기본적인 약속이 존재한 먼저 const는 무조건 붙여라 외워라 두번쨰로 매개변수 이름으로 rhs는 for int i 같은 존재다.

//제작자 코드
class test
{
public:
    test(int a)
    {
        number = a;
    }

    test(const test& rhs)
    {
        cout << "복사 생성자 호출 !!" << endl;
        this->number = rhs.number;
        cout << number << endl;
    }


private:
    int number;
};



//사용자 코드
int main(void)
{
    test a(10);
    test b(a);


    return 0;
}

출력결과 복사 생성자 호출 !! 10

복사 생성자도 1장에서 배운 생성자 처럼 클래스 인스턴스가 복사 생성될때 호출 되는것을 확인 할수 있다. 그리고 우리가 생각 했던 대로 10이 출력 된것을 볼수 있다 그렇다면 다음 코드를 살펴보자

//제작자 코드
class test
{
public:
    test(int a)
    {
        number = new int(a);
    }

    ~test()
    {
        delete number;
    }

    int GetData()
    {
        return *number;
    }

private:
    int* number = nullptr;
};



//사용자 코드
int main(void)
{
    test a(10);
    test b(a);

    cout << a.GetData() << endl;
    cout << b.GetData() << endl;


    return 0;
}

출력결과 10 10 우리가 생각한 출력결과가 호출 되었지만 위에 코드를 실행하면 오류가 발생한다 깊은 복사와 얕은 복사의 문제를 해결하지 못한 코드라서 메모르 해제 과정에서 문제가 생긴다

2.깊은 복사 얕은 복사

깊은 복사 얕은 복사는 매우 중요하기에 천천히 그림을 통해 설명하겠다

//사용자 코드
int main(void)
{
    int pa = new int;
    *pa = 10;

    int pb = new int;
    *pb = pa;

    delete pa;
    delete pb;


    return 0;
}

위에 코드가 실행되면 메모리 에서 그림과 같은 구조가 형성된다

pa와 pb가 각각의 동적 생성한 int 인스턴스가 있다. 설명을 위해 a,b라 부르겠다 1번 그림처럼 pa 가 a를 가리키고 pb가 b를 가리키면 정상적이다 하지만 pb가 pa를 얕은 복사 하면서 인스턴스 b는 접근 불가능한 메모리 영역이 되어버렸다. 심지어 그림 2에서 a가 메모리 영역을 해제한 다음 pb가 메모리를 해제하면 심각한 오류가 발생한다 (해제할수 있는 메모리가 없는데 해제를 하니깐) 그렇다면 어떤식으로 깊은 복사를 할수 있을까 간단하다 pb = pa; * 를 *pb = ** *pa;로 바꾸면 된다

그러면 이제 앞선 코드를 복사 생성자를 이용해 수정해 보자

//제작자 코드
class test
{
public:
    test(int a)
    {
        number = new int(a);
    }

    test(const test& rhs)
    {
        number = new int;
        *this->number = *rhs.number;

    }

    ~test()
    {
        delete number;
    }

    int GetData()
    {
        return *number;
    }

private:
    int* number = nullptr;
};



//사용자 코드
int main(void)
{
    test a(10);
    test b(a);

    cout << a.GetData() << endl;
    cout << b.GetData() << endl;


    return 0;
}

2_2 대입 연산자

대입 연산자 = 클래스 에도 기본적으로 적용된다.

int main(void)
{
    test a(10);
    test b(5);

    b = a;
    cout << a.GetData() << endl;
    cout << b.GetData() << endl;


    return 0;
}

** b = a;** 처럼 대입을 할수있다 하지만 컴파일러가 기본적으로 제공하는 대입 연산자는 얕은 복사를 하기 떄문에 문제가 발생한다. 그렇기에 대입 연산자를 정의해줘야 한다 대입 연산자의 기본 문법은 단순하다 *클래스이름& operator=(const 클래스이름& rhs) * 현재 코드에서 대입 연산자를 정의하면 다음과 같다

test& operator=(const test& rhs)
    {
        *number = *rhs.number;
        return *this;
    }

위와 같이 대입 연산을 정의해주면 클래스 인스터스에 대입 연산이 제대로 적용된다.

2_3 변환 생성자

변환 생성자는 개발자 모르게 호출되면서 동시에 불필요한 임시객체를 만들어 버린다 다음 예제를 살펴보자

//제작자 코드
class CTestData
{
public:
    CTestData(int nParam)
    {
        cout << "CTestData(int)" << endl;
    }
    CTestData(const CTestData & rhs    )
    {
        cout << "CTestData(const CTestData &)" << endl;
    }

    int GetData() const
    {
        return m_nData;
    }

    void SetData(int nParam)
    {
        m_nData = nParam;
    }

    ~CTestData()
    {
        cout << "소멸자 생성" << endl;
    }


private:
    int m_nData = 0;
};


void TestFunc(CTestData param)
{
    cout << "TestFunc(): " << param.GetData() << endl;
}

//사용자 코드
int main(void)
{
    TestFunc(5);

    return 0;
}

출력결과 CTestData(int) TestFunc(): 5 소멸자 생성

천천히 코드를 살펴보면 출력결과가 굉장히 이상하다는 것을 느낄수 있다 사용자 코드 어디에도 클래스 인스턴스를 생성한 적이 없는데 생성자와 소멸자가 호출 된것이다 어떻게 이런일이 가능할까? 지금 이러한 현상이 바로 변환 생성자 때문에 일어난 일이다 그렇다면 언제 변환 생성자가 호출 되었을까? TestFunc(5); 에서 Test의 원형을 보면 void TestFunc(CTestData param) 매계변수가 클래스 형식임을 확인할수 있다 즉 변환 생성자 는 TestFunc(5);을 TestFunc(CTestData(5));로 변환 시켜 버린다 그렇기 떄문에 변환 생성자는 내가 원치 않아도 임시객체를 만들어 생성 소멸자를 호출한다 그렇기에 우리는 지금부터 2가지 약속을 할것이다 1.매개변수로 클래스를 넘길때는 참조형으로 넘길것 ** **2.변환 생성자에는 explicit을 붙여서 묵시적 형변환을 차단해라 그렇다면 다음과 같이 코드를 수정해야한다

void TestFunc(CTestData& param)
{
    cout << "TestFunc(): " << param.GetData() << endl;
}

explicit CTestData(int nParam)    
{
    cout << "CTestData(const CTestData &)" << endl;
}

2_4 허용되는 변환

클래스가 변환 생성자를 제공하면 두 형식 사이에 호환성이 생긴다 예시로 int 5가 형변환을 통해 CTest 클래스로 형변환 된것을 앞서 살펴 봤다 하지만 CTest가 int 형이 될수 없으므로 반쪽짜리 형변환이 된다 그렇기에 지금부터 CTest가 int형 으로 형변환 시키는 방법에 대해 알아보자

형변환 연산자 문법 operator int(void){return m_ndata}

그러면 다음과 같이 형변환이 가능하다

//사용자 코드
int main(void)
{
    CTestData a(5);
    cout << a;

    return 0;
}

출력결과 5

이처럼 클래스를 int형으로 형변환 시킬수 있다

• 1.클래스
• 2.생성자와 소멸자
• 3.메서드

1.클래스

1-1 객체지향 프로그래밍

C++에 중요한 특징인 객체지향 이라는 것이 무엇인지 알아보자 C의 절차지향과 C++의 객체지향이 차이를 코드를 통해 알아보자

//제작자 코드
typedef struct UserData
{
    int age;
    char name[10];
}UserData;

//사용자 코드
int main(void)
{
    UserData USER = { 20,"철수" };
    printf("%d,%s", USER.age, USER.name);

    return 0;
}

일반적인 C 예제 이다. 지금부터 자신을 완전히 사용자에 입장에서 생각해 보자 나는 유저데이터를 이용해야 한다 유저데이터를 사용하기 위해서는 유저데이터 안에 나이와 이름이 들어있다는 사실을 알아야 하고 각각의 데이터의 유형에 맞춰서 출력해 줘야한다. 사용자가 사용하기에 굉장히 번거롭다 이제 C++ 코드를 살펴보자

//제작자 코드
class UserData
{
public:
    int age;
    char name[10];

    void Print()
    {
        printf("%d,%s",age,name);
    }
};

//사용자 코드
int main(void)
{
    UserData USER = { 20,"철수" };
    USER.Print();

    return 0;
}

C와 출력되는 결과는 같다 하지만 사용자 입장에서 볼때 직관적이고 편리하다 코드에 유지보수에 관점에서 직관성과 편리함은 굉장히 중요하다 그렇기에 우리가 C++에 객체지향 프로그램에 중요성을 공부한다

2.생성자와 소멸자

2-1생성자와 소멸자에 대한 개념

생성자와 소멸자는 클래스 객체가 생성 및 소멸될 떄 자동적으로 호출되는 함수이다

class MyClass
{
public:
    MyClass() //생성자
    {

    }
    ~MyClass() //소멸자
    {

    }

};

기본적으로 클래스를 선언 하면 다음과 같이 클래스는 생성자와 소멸자를 디폴트로 가지고 있다. 그렇다면 생성자와 소멸자가 각각 어떻게 호출되는지 살펴보자

    //제작자 코드
class MyClass
{
public:
    MyClass() //생성자
    {
        cout << "생성자 호출" << endl;
    }
    ~MyClass() //소멸자
    {
        cout << "소멸자 호출" << endl;
    }

};



//사용자 코드
int main(void)
{
    cout << "시작" << endl;
    MyClass a;
    cout << "끝" << endl;



    return 0;
}

실행결과 시작 생성자 호출 끝 소멸자 호출

생성자는 클래스 객체가 생성될때 호출되고 소멸자는 선언된 블럭 범위가 끝나면 호출된다 소멸자에 호출에 대해 조금 더 알아보자 기본적으로 main함수에서 클래스 객체를 생성하면 객체 또한 지역 변수다 그렇기에 지역변수에 특성상 선언 블럭범위에서만 값이 유호하기에 범위를 끝나는 시점에서 소멸자가 호출된다.

생성자 호출자의 특징 정리

• 1.Main 함수 호출전에 생성자 소멸자가 호출될수 있다.
• 2.생성자는 다중 정의할 수 있지만 소멸자는 다중 정의할 수 없다
• 3.생성자 소멸자는 생략할 수 있으나 컴파일러가 자동으로 만든다

2-2 클래스 동적 객체 생성과 소멸

클래스 인스턴스는 new 연산자를 사용해 동적으로 생성 소멸할 수 있다.

int main(void)
{
    MyClass* a = new MyClass;

    delete a;

    MyClass* b = new MyClass[3];

    delete[] b;


    return 0;
}

동적으로 생성과 소멸시 조금 더 직관적으로 생성자와 소멸자에 호출 시점을 확인할 수 있다. 물론 동적으로 할당한 메모리를 해제 해야한다

2-3 생성자 다중 정의

오늘 공부한 3장 내용에 핵심이라고 할수있는 생성자 다중 정의 이다 앞서 잠깐 설명한것처럼 생성자는 다중 정의가 가능하다

    add(int a) //생성자_1
    {
        cout << a << endl;
    }

    add(int a , int b) //생성자_2
    {
        cout << a + b << endl;
    }

    int main(void) 
   {
    add num_1(3);
    add num_2(3, 4);

    return 0;
   }

출력 결과 3 7

add 클래스의 생성자가 2개로 다중정의 되있다 그렇기에 사용자가 클래스 객체를 다양하게 생성해서 원하는 값을 출력할수 있다

3.메서드

3_1 메서드의 개념

메서드의 사전적 정의는 방법이다 하지만 이러한 설명은 다소 재미가 없으니 비유를 통해 말하자면 인간이라는 객체가 메서드 달리기,걷기,점프,던지기 등등 여러가지 가지고 있는것이다. 객체가 수행할 수 있는 다양한 기능이라고 생각하자.

3_2 this 포인터

this 포인터는 작성 중인 클래스의 인스턴스에 대한 주소를 가리킨다

//제작자 코드
class UserData
{
public:
    int age;
    char name[10];

    void Print()
    {
        printf("%d,%s",age,name);
    }
};

Print()메서드 안에서 this 포인터가 작동한다. 다만 우리눈에 보이지 않을 뿐이다

void Print()
    {
        printf("%d,%s", this->age, this->name);
    }

사실 Print()함수는 this가 포함된 위와같은 코드로 존재한다 우리가 UserData 클래스에 인스턴스를 하나만들면 인스턴스 내에서 this 포인터는 인스턴스 자기 스스로의 주소를 나타낸다는 뜻이다 그렇기에** 똑같은 클래스 인스턴스 라도 this 포인터의 값은 다르다**

3_3 상수형 메서드

상수형 메서드는 형식이 간단하다 클래스 뒤에 const 형한정어만 붙여주면 된다. 상수형 메서드는 읽기만 가능하고 쓰기는 불가능 한데 쉽게 설명해서 GetData()와 같이 단순히 값을 반환하는 메서드에 사용하면 된다 하지만 add()같이 값을 더하는 메서드에는 사용하면 쓰기가 불가능 하다

const를 얼마나 잘쓰냐가 고수와 하수를 가른다.

3_4 정적 멤버

정적 멤버는 전역 변수에 가깝다. 전역변수는 특정 인스턴스를 선언하지 않아도 직접 접근 가능한것 처럼 정적 멤버들도 클래스 인스턴스 없이도 직접 접근이 가능하다

상속은 올바르게 활용하면 재사용성과 확장성이 좋은 프로그램을 만들수 있다 그렇다면 상속 이란 무엇일까? 우리가 흔히 아는 상속이라는 단어는 상속자를 떠올리기 쉽다 흔히 부모가 자식에게 재산이나 무언가를 상속하는걸 상상하기 쉬울거다 그렇다면 프로그램에서는 어떻게 상속이 이루어질까?

1-1.클래스 상속

2개의 클래스가 A,B가 존재한다고 생각해 보자 B가 A에게 상속 받았다면 B와A의 관계를 그림으로 살펴보자 이러한 관계를 문장으로 표현하면 A클래스가 B클래스 에게 상속했다 ,B클래스가 A클래스에게 상속 받았다

그럼이제 본격적으로 상속을 어떻게 프로그램에서 활용 할수있을지 알아보자 하나의 상황을 가정해보자 우리는 마트를 운영하는데 VIP시스템을 도입하려고 한다. 그럼이제 프로그램을 만들어 보자 손님 클래스와 VIP클래스를 생성한다 손님과 VIP클래스에게 동일하게 사용되는 멤버변수가 있다 우리가 상속을 활용하지 않는다면 우리는 손님 클래스를 정의하고 나서 VIP를 클래스를 정의할때 똑같은 코드를 써줘야 한다 이것은 굉장히 비효율 적인 방식이다 그렇다면 상속을 이용하면 어떻게 될까? VIP클래스의 정의가 훨씬 깔끔해 졌다

1-2 상속의 주의점

상속받은 클래스는 상위 클래스의 멤버변수와 메소드를 활용할수있다 하지만 여기서 주의할점이 있다 그것은 상위 클래스에서 private를 통해 변수 메소드를 만들면 하위 클래스는 접근할수 없다. 이를 해결하기 위해 protected을 활용하면 된다 private와 같이 외부접근을 막지만 하위클래스에서의 활용은 가능하게 한다

2.상속에서 클래스 생성과 형 변환

하위 클래스가 생성될때 상위 클래스의 생성자가 먼저 호출됩니다 즉 VIP클래스를 생성하면 먼저 손님 클래스의 멤버변수가 힙 메모리에 생성되고 난후 VIP멤버 변수가 생성됩니다 참고로 private선언된 경우에도 메모리 공간에 존재하지만 접근 자체가 불가능 한것이다

2-1.형 변환

하위 클래스는 상위 클래스보다 일반적으로 더 많은 기능을 가지고 있다 하위 클래스가 상위 클래스 에게 상속을 받기 떄문이다 그렇다면 하위 클래스를 상위 클래스로 형 변환 하면 어떻게 될까? 위 그림을 보면 VIP클래스를 생성하면 다음과 같은 메모리 구조로 나타나다 하지만 VIP클래스를 손님 클래스로형변환 하면 손님 클래스의 메모리에만 접근할수있게된다

2-2.메서드 오버라이딩

메서드 오버라이딩이란 상위 클래스의 메서드를 하위 클래스에서 재정의 하는것을 말한다 예를 들어 손님 클래스에는 쿠폰이 없다 그렇기에 값을 계산하는 메서드는 쿠폰 할인율을 고려하지않고 정의 하면 되지만 VIP클래스는 쿠폰 할인율이 존재하기에 메서드를 재정의 해줘야할 필요가있다

2-3.가상 메서드

손님 클래스와 A라는 메서드가 있고 VIP클래스에서 A를 오버라딩한 메서드가 있다 VIP 클래스를 손님 클래스로 형변환후 A메서드를 호출 하면 어떤 A가호출 될까? 답은 오버라이딩 된 A메서드가 호출된다. 이것은 메서드가 멤버변수와는 다른 메모리 구조를 지니기 떄문이고 이 메모리를 가상 메모리라고 부른다 즉 손님 클래스 에서 A는 VIP 클래스에서 A와 다른 메모리 구조에 위치한다

지역 변수의 사용 범위는 블록 내부로 제한 되므로 다른 함수에서는 사용할수 없다

void assign(void);


int main(void)
{
    int a = 0;

    assign();
    printf("main 함수 a : %d\n",a);


    return 0;
}

void assign(void)
{
    int a;

    a = 10;
    printf("assign 함수 a :%d\n", a);
}

위와 같이 assign함수와 main함수 두군데 에서 a라는 정수형 변수가 사용되었다 하지만 출력 값은 assign함수 a는 10 main 함수 a 는 0이 된다 둘의 결과가 같지 않은 이유는 다음과 같다

main 함수 a와 assign 함수 a는 이름만 같을 뿐 서로다른 독립적인 저장 공간을 갖는다

1-1.지역 변수의 장점

• 1.메모리를 효율적으로 사용가능하다

지역 변수는 함수의 호출이 끝나면 운영체제가 자동적으로 저장 공간을 회수하기 하기 떄문에 공간을 유지하지 않아도 된다

• 2.디버깅이 유리하다

지역 변수는 사용 범위가 제한되기 떄문에 문제가 있는 값을 발견 및 수정이 쉽다

1-2.블록 안에서 사용하는 지역 변수

int main(void)
{
    int a = 10;
    int b = 20;

    printf("교환 전 a와 b의 값 : %d ,%d\n ", a, b);
    {

        int temp;

        temp = a;
        a = b;
        b = temp;
    }

    printf("교환 후 a와 b의 값 : %d ,%d\n ", a, b);


    return 0;
}

코드를 실행 하면 교환 전 a,b는 10,20 교환후 20,10이다 지역 변수가 main 함수에서 호출 되면 main 함수 블록 전체에서 사용할수 있다 하지만 변수가 둘 이상이면 가까운 블록 변수를 사용하게 된다

int main(void)
{
    int a = 10;
    int b = 20;

    printf("교환 전 a와 b의 값 : %d ,%d\n ", a, b);
    {

        int a = 20;
        int b = 10;
        int temp;

        temp = a;
        a = b;
        b = temp;
    }

    printf("교환 후 a와 b의 값 : %d ,%d\n ", a, b);


    return 0;
}

a,b가 main함수 안에 블럭 안에서 생성되면 새로운 a,b는 블럭 안에서 사용할수있다

2.전역 변수

전역 변수는 함수 밖에서 호출하면 된다 함수에 포함되지 않으므로 사용 범위 제한이 없다 하지만 전역 변수와 이름이 같은 지역 변수가 함수내에 존재한다면 함수는 지역 변수를 우선적으로 사용한다

3.정적 지역 변수

정적 지역 변수와 일반 지역 변수의 차이는 메모리 존재 기간에 따라 다르다

void static_func(void)
{
    static int a = 0;
    a++;
    printf("%d\n", a);

}

void func(void)
{
    int a = 0;
    a++;
    printf("%d\n", a);
}

두개의 함수를 main함수에서 각각 3번씩 호출 했다고 가정하면 정적 변수를 사용한 함수는 1,2,3 을 일반 지역 변수를 사용한 함수는 1,1,1을 출력할거다 여기서 두개의 차이점이 나타난다 정적 지역 변수는 지역 지만 메모리 할당과 유지는 전역변수와 같다

배열은 자료형이 같은 변수를 메모리의 연속적 으로 할당한다 char ary[3]이라는 배열을 선언했다고 가정해 보자 그림을 통해 살펴보자 char형 변수의 크기는 1바이트 라면 각각의 배열 요소의 주소는100,101,102 번지가 된다 배열명 ary는 첫 번째 배열의 요소의 주소 값 이면선 첫 번쨰 배열 요소를 가리킨다 *ary = ary[0] 이고 ary = 100 이다

1-1.배열명으로 배열 요소 사용하기

주소값은 특별한 연산 규칙을 가진다 주소 + 정수 => 주소 + (정수 * 변수의 크기) 코드를 통해 알아보자

int ary[3];
    int i = 0;
    *(ary) = 10;
    *(ary + 1) = 20;
    *(ary + 2) = 30;

    for (i = 0; i < 3; i++)
    {
        printf("%3d", *(ary + i));
    }

실행을 해보면 10 20 30이 정상적으로 출력된다 주소값 연산 규칙을 적용해서 살펴보면 ary 주소값이 100이라 가정한다면 ary +1 => 100(ary 주소값) + 1 * 4(int의 크기) 따라서 ary + 1 =104로 두번째 배열요소의 주소값을 의미한다 ary[1] (배열 요소 표현식) <=> *(ary +1) (포인터 연산식)은 표현이 다를뿐 같은 뜻을 의미한다

1-2.배열명 역할을 하는 포인터

배열의 이름은 주소값 이므로 포인터를 이용해 저장할수 있다 이를 통해 포인터를 배열처럼 사용할수 있다 코드를 살펴보자

int main(void)
{
    int ary[3];
    int* pary = ary;

    //포인터 연산식
    *(pary) = 10;
    *(pary + 1) = 20;
    *(pary + 2) = 30;

    for (int i = 0; i < 3; i++)
    {
        printf("%d\n", *(pary + i));
    }

    //배열 연산식
    pary[0] = 100;
    pary[1] = 200;
    pary[2] = 300;

    for (int i = 0; i < 3; i++)
    {
        printf("%d\n", pary[i]);
    }


    return 0;
}

실행결과 10 20 30 100 200 300으로 정상으로 출력된다 포인터를 이용해 배열명을 저장하면 포인터는 포인터 연산 혹은 배열 표현식을 이용해 배열요소에 접근할수 있다

1-3.배열명과 포인터의 차이

• 1.sizeof 연산 값이 다르다 배열명 사용 => 배열 전체 크기 포인터 사용 => 포인터 하나의 크기

• 2.변수와 상수의 차이 배열명은 상수이고 포인터는 변수다

오늘은 단순한 정렬에 대해 공부한 내용을 정리하려고 한다. 오늘은 단순 정렬 3가지에 대해 알아보자

• ** 1.버블 정렬**
• ** 2.선택 정렬**
• 3.삽입 정렬

1.버블 정렬

그림과 같이 3,1,4,2 순으로 저장된 배열이 있다 이것을 오름차순 으로 정렬 하는 과정을 살펴보자 그림에서 본것처럼 첫 번째 값과 두 번째 값을 비교해서 우선순위에 따라 교환한걸 확인할수있다 그다음 에는 두 번째와 세 번째 그다음 세 번쨰와 네 번쨰를 비교한다 그림은 3번째 비교가 진행이 되고 난후의 배열의 모습을 표현한거다 우리가 알수 있는것은 버블 정렬이 한번 하고나니 배열의 끝에는 최고로 큰수가 와있다는 사실이다 그말은 두번째 진행에서는 더이상 네 번째 요소는 신경쓰지 않고 나머지 세 개만 신경써주면 된다

1-1.버블 정렬 코드

#include <stdio.h>

void BubbleSort(int arr[], int n)
{
    int i, j;
    int temp;

    for(i=0; i<n-1; i++)
    {
        for(j=0; j<(n-i)-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

코드 단계에서 c기본 문법서에서 많이 봐운 구조로 쉽게 코드를 분석할수 있었다

1-2버블 정렬 성능평가

자료구조에 처음으로 나와있는 내용이 성능평가 였다 성능을 평가하는 두가지 요소는 1.시간 복잡도 2.공간 복잡도

버블정렬 에서 복잡도는 비교의 횟수 와 이동의 횟수 복잡도를 가진다 앞서 우리가 본 그림에서 배열 n개는 몇번의 비교와 이동을 했을까 ? 이동은 경우에 따라 달라지지만 비교의 횟수는 최고의 상황과 최악의 상황에서 같다 (n-1) + (n-2) + (n-3) ........ 등차수열의 값을 계산하면 알수있다 결론은 버블 정렬의 빅-오는 항상 n^2을 가진다는 것을 알수있다

2.선택 정렬

그림에서 처럼 배열에 3,1,4,2 순으로 데이터가 있다고 생각하자

첫 번째 값과 나머지 중에 가장작은 값 교환해 준다

그림처럼 1,3이 교환 되었다 그러면 1은 더이상 비교해줄 필요가 없다 버블 정렬에서처럼 나머지 3개에서 두번째와 나머지들중 가장 작은 것과 교환해 주면 된다

2-1.선택 정렬 코드

#include <stdio.h>

void SelSort(int arr[], int n)
{
    int i, j;
    int maxIdx;
    int temp;

    for(i=0; i<n-1; i++)
    {
        maxIdx = i;    // 정렬 순서상 가장 앞서는 데이터의 index

        for(j=i+1; j<n; j++)   // 최소값 탐색
        {
            if(arr[j] < arr[maxIdx])
                maxIdx = j;
        }

        /* 교환 */
        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp;
    }
}

코드를 분석해 보면 첫번째 for 문에서 int가 1부터 시작함을 알수있다. 저런 이유는 선택 정렬에서 1번째는 비교할 필요가 없기때문이다

3.삽입 정렬

똑같이 3,1,4,2 순으로 배열이 있다고 생각해보자 삽입 정렬에서 배열의 첫번째는 정렬이 완료된 영역으로 생각해보자 두번째 데이터를 정렬 영역에 비교와 동시에 넣어준다 똑같이 나머지 비정렬 영역에 있는 것들도 정렬 영역에 ** 비교와 동시에 삽입** 해주면 된다

3-1.삽입 정렬 코드

#include <stdio.h>

void InserSort(int arr[], int n)
{
    int i, j;
    int insData;

    for(i=1; i<n; i++)
    {
        insData = arr[i];   // 정렬 대상을 insData에 저장

        for(j=i-1; j>=0 ; j--)
        {
            if(arr[j] > insData) 
                arr[j+1] = arr[j];    // 비교 대상 한 칸 뒤로 밀기
            else
                break;   // 삽입 위치 찾았으니 탈출!
        }

        arr[j+1] = insData;  // 찾은 위치에 정렬 대상 삽입!
    }
}

우선순위 큐의 이해

우선순위 큐 라고해서 앞서 배운 큐를 떠올리는건 당연하지만 우선순위 큐와 큐는 큰 차이점이 있기에 다른 개념이라고 생각하는 것이 쉽다 가장 큰 차이점으로는 큐는 줄서기로 먼저 줄을 선사람이 먼저 입장하는 거라면 우선순위 큐는 응급실을 떠올리면 된다 감기환자 보다 교통사고 환자가 더 먼저 치료를 받는것처럼 우선순위에 따라 데이터를 접근한다

우선순위 큐의 구현 방법

• 1.배열을 기반으로 구현
• 2.연결 리스트 기반 구현
• 3.힙 기반 구현

1.배열을 기반으로 구현

배열을 기반으로 우선순위 큐를 구현 하는 방법은 간단하게 우선순위가 높은 데이터를 배열 앞쪽에 차곡차곡 위치시키면 된다 하지만 배열을 기반으로 구현하는 방식의 큰 단점은 데이터를 삽입하거나 삭제 과정에서 배열에 데이터들을 한칸씩 전부 이동시켜 줘야한다는 것이다 또한 데이터 추가시에 모든 데이터와 우선순위를 비교해야 하는 문제가 발생할 가능성이 있다

2.연결 리스트 기반 구현

연결리스트도 배열과 마찬가지로 우선순위가 높은 데이터를 앞쪽에 연결하는 방식으로 구현할수 있다 하지만 배열 기반과 마찬가지로 문제점을 가지는데 배열처럼 데이터를 추가 삭제시 한칸씩 이동해야 하는 문제는 없지만 역시 추가시 모든 데이터와 우선순위를 비교해야 하는 상황이 생길수 있다

3.힙 기반 구현

힙은 이진트리 이면서 동시에 완전 이진 트리이다 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다

힙은 그림에서 처럼 우선순위에 따라서 데이터를 위치 시킬수 있는 자료구조 입니다.

위로 올라 갈수록 값이 커지게 할수 있고 (최대 힙) 반대로 값이 작아 질수 있다( 최소 힙)

힙에 특징을 활용해서 우선순위 큐를 구현 할수있다

힙 데이터 추가

힙 = 우선순위 큐 라고 생각하는 것은 무리가 있다 물론 저 둘이 환상의 콤비임은 틀림이 없기에 동일시 할수 있지만 결코 같지 않음을 알아놓자 최소 힙을 기준으로 정리해 보자 그림처럼 최소 힙이 존재해 있다 여기서 최소 힙의 조건을 정리해 보자

1.자식노드 데이터의 우선순위 <= 부모 노드 데이터 우선순위 2.완전이진트리 이다

위 그림에서 데이터 "2"를 추가하는 과정을 그림으로 이해해 보자

1.새로운 데이터는 우선순위가 제일 낮다고 가정하에서 "마지막 위치"에 저장한다

2.부모 노드와 우선순위를 비교해서 자리를 바꿔준다 (2는 5보다 우선순위가 높음으로 자리가 바꿀것이다)

3. 2번 과정을 계속 반복해 준다

   이렇게 해서 데이터의 추가 과정을 그림으로 알아봤다 그림으로 설명한 내용을 100%코드로 그대로 옮기지는 않을것을 알아두고 있자

   힙 데이터 삭제

   우선순위 큐에서의 삭제는 "가장 높은 우선순위 데이터 삭제" 를 의마한다

   데이터를 삭제하고 난 후로도 완전 이진트리 구조를 유지해야 한다.

   1.가장 높은 우선순위 데이터를 삭제한다 2.마지막 노드를 루트 노드의 자리로 옮긴다 (여기서 마지막이란 마지막 레벨의 가장 오른쪽에 위치한 노드이다)

4. 두개의 자식노드 중에 우선순위가 높은 자식 노드와 비교후 자리를 바꾼다

5. 3의 과정을 계속 반복한다

힙의 구현

배열을 이용해서 힙을 구현해 보자 여기서 우리는 몇가지 힙의 규칙을 살펴보자

• 왼쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 X 2
• 오른쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 X 2 + 1
• 부모 노드의 인덱스 값 = 부모 노드의 인덱스 값 ÷ 2

힙의 구조체

코드

typedef struct _heapElem
{
    int pr;    // 값이 작을수록 높은 우선순위 높다
    int data;
} HeapElem;




typedef struct _heap
{
    int numOfData;
    HeapElem heapArr[100];
} Heap;

HeapElem은 트리의 노드를 의미하고

Heap은 이제 노드 구조체 배열을 가지는 구조체다

지금부터는 앞에서 그림으로 설명한 데이터 추가 삭제 과정을 코드로 구현한것을 정리해 보자

코드

 //1번
 void HeapInit(Heap * ph)
{
    ph->numOfData = 0;
}
 //2번
int HIsEmpty(Heap * ph)
{
    if(ph->numOfData == 0)
        return TRUE;
    else
        return FALSE;
}
 //3번
int GetParentIDX(int idx) 
{ 
    return idx/2; 
}
 //4번
int GetLChildIDX(int idx) 
{ 
    return idx*2; 
}
 //5번
int GetRChildIDX(int idx) 
{ 
    return GetLChildIDX(idx)+1; 
}
 //6번
int GetHiPriChildIDX(Heap * ph, int idx)
{
    if(GetLChildIDX(idx) > ph->numOfData)    // 자식 노드가 없다면
        return 0;

    else if(GetLChildIDX(idx) == ph->numOfData)    // 왼쪽 자식 노드가 마지막 노드라면
        return GetLChildIDX(idx);

    else   // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교
    {
        if(ph->heapArr[GetLChildIDX(idx)].pr 
                        > ph->heapArr[GetRChildIDX(idx)].pr)
            return GetRChildIDX(idx);
        else
            return GetLChildIDX(idx);
    }
}
 //7번
void HInsert(Heap * ph, HData data, Priority pr)
{
    int idx = ph->numOfData+1;
    HeapElem nelem = {pr, data}; 

    while(idx != 1)
    {
        if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
        {
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
            break;
    }

    ph->heapArr[idx] = nelem;
    ph->numOfData += 1;
}
 //8번
HData HDelete(Heap * ph)
{
    HData retData = (ph->heapArr[1]).data;    // 삭제할 데이터 임시 저장
    HeapElem lastElem = ph->heapArr[ph->numOfData];

    int parentIdx = 1;    // 루트 노드의 Index
    int childIdx;

    while(childIdx = GetHiPriChildIDX(ph, parentIdx))
    {
        if(lastElem.pr <= ph->heapArr[childIdx].pr)
            break;

        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
    }

    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}

1번 코드

 //1번
 void HeapInit(Heap * ph)
{
    ph->numOfData = 0;
}

힙을 초기화 하는 코드이다

2번 코드

 int HIsEmpty(Heap * ph)
{
    if(ph->numOfData == 0)
        return TRUE;
    else
        return FALSE;
}

ph->numOfData은 힙에 저장된 데이터의 갯수(노드 갯수)를 의미한다

3,4,5번 코드

 //3번
int GetParentIDX(int idx) 
{ 
    return idx/2; 
}
 //4번
int GetLChildIDX(int idx) 
{ 
    return idx*2; 
}
 //5번
int GetRChildIDX(int idx) 
{ 
    return GetLChildIDX(idx)+1; 
}

int idx은 인자로 넘겨주는 노드의 인덱스 값이다 int idx 1은 루트 노드를 의미한다 int idx에 따라 왼쪽, 오른쪽,부모노드의 인덱스 값을 반환한다

6번 코드

 //6번
int GetHiPriChildIDX(Heap * ph, int idx)
{
    //6-1번
    if(GetLChildIDX(idx) > ph->numOfData)    // 자식 노드가 없다면
        return 0;
    //6-2번
    else if(GetLChildIDX(idx) == ph->numOfData)    // 왼쪽 자식 노드가 마지막 노드라면
        return GetLChildIDX(idx);
    //6-3번
    else   // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교
    {
        if(ph->heapArr[GetLChildIDX(idx)].pr 
                        > ph->heapArr[GetRChildIDX(idx)].pr)
            return GetRChildIDX(idx);
        else
            return GetLChildIDX(idx);
    }
}

6-1번 자식 노드가 없는 경우

ph->numOfData가 의미하는 바는 완전이진트리의 마지막 노드의 인덱스 값을 의미한다 5번 인덱스 노드의 왼쪽에는 자식 노드가 존재하지않는다 그렇기에 존재하지 않는 자식노드의 인덱스 값은 어떻게든 마지막 인덱스 값보다는 큰상황이 나올수 밖에 없다

6-2번 왼쪽 자식 노드가 마지막 노드라면

int idx값으로 2를 준다면 6-2번 코드로 진행될거다 여기서 보면 4번인덱스와 마지막 인덱스 넘버가같음을 확인할수있다

6-3번 왼쪽 자식과 오른쪽 자식중에 우선순위가 더높은 인덱스 넘버를 반환하라는 뜻이다

7번 코드

//7번
void HInsert(Heap * ph, HData data, Priority pr)
{
    int idx = ph->numOfData+1;
    HeapElem nelem = {pr, data}; 

    while(idx != 1)
    {
        if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
        {
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
            break;
    }

    ph->heapArr[idx] = nelem;
    ph->numOfData += 1;
}

앞서 그림에서 설명한것처럼 추가한 힙의 데이터를 힙의 마지막에 위치시킨다 동시에 값과 우선순위를 가지는데 그것을 부모노드와 계속 비교해서 자리를 조정해 간다

8번 코드

 //8번
HData HDelete(Heap * ph)
{
    int retData = (ph->heapArr[1]).data;    // 삭제할 데이터 임시 저장
    HeapElem lastElem = ph->heapArr[ph->numOfData];

    int parentIdx = 1;    // 루트 노드의 Index
    int childIdx;

    while(childIdx = GetHiPriChildIDX(ph, parentIdx))
    {
        if(lastElem.pr <= ph->heapArr[childIdx].pr)
            break;

        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
    }

    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}

8번 코드는 우리가 그림으로 삭제에 과정을 살펴볼때와 코드의 구현은 약간의 차이가 있다 그림에서는 먼저 첫번쨰 인덱스의 값을 삭제하고 마지막 노드를 첫번째로 옮기지만 실제로 코드를 보면 마지막 노드를 1번 노드로 옮겨서 진행하지 않는것을 확인할수 있다

HeapElem lastElem = ph->heapArr[ph->numOfData];

이 코드를 보면 마지막 인덱스 정보를 따로 저장해 둔것을 확인할수있다

마치며

힙을 공부해 본것을 간단하게 정리해 봤는데 정리에 과정을 거치면서도 비선형 구조 공부가 조금씩 어려워 지고 있음을 느낀다 앞으로 남은 내용들도 천천히 제대로 이해해 나가면 좋겠다

순회의 세 가지 종류

- 1.중위 순회 (루트 노드를 중간에)

- 2.후위 순회 (루트 노드를 마지막에)

- 3.전위 순회 (루트 노드를 먼저)

위의 3가지 방식을 통해 이진 트리의 순회가 이루어 진다 그렇다면 높이가 2이상인 이진 트리는 어떻게 이루어 질까? 바로 재귀적 구현으로 가능하다

순회의 재귀적 표현

우리는 중위 순회를 기준으로 천천히 정리해 나가보자 우리는 그림과 같이 다음 코드를 천천히 진행시켜 가며 재귀 순회를 정리해 보자

코드

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;

    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

(action함수는 루트 노드의 데이터값을 출력하는 역활을 한다) 코드의 진행 순서를 말로 풀어보자 간다한게 3가지 과정이다

1.왼쪽 서브 트리를 순회하라 2.루트 노드를 순회하라 3.오른쪽 서브 트리를 순회하라 위의 표현은 교과서 표현이니 내가 정의한 방식대로 조금 다듬자면 트리라고 생각하지 말고 1개의 노드로서 생각해보자

말로서 위 그림 트리를 접근해 보겠다

먼저 위에 코드가 진행되면 루트노드 A를 기준으로 왼쪽 노드인 B에 접근할것이다 그러면 B에 접근한 순간 재귀함수의 호출로 인해 이번에는 루트노드 B를 기준으로 왼쪽에 있는 Q에 접근할것이다 마찬가지로 Q에 접근시 재귀함수가 호출되면서 루트 노드 Q를 기준으로 왼쪽에 접근 할것이다 그순간 탈출 조건에 의해서 루트 노드 Q 에대한 함수는 끝난다 그러면 루트 노드 B의 왼쪽 진행이 끝나게 된다 그러고 나면 B에 데이터 값을 반환하고 루트 노드 B에 오른쪽인 W에 접근 하면서 ....

이런식으로 말 장난 같은 행위를 계속 해나가면 재귀함수를 이용해 이진 트리를 순회할수있다 재귀함수의 이해는 개인에 따라 재귀적 사고를 통해 익숙해 지는것을 책에서도 지향 한다 그렇기에 나는 일부 과정을 말로 정리함으로써 내가 생각한 재귀적 과정을 정리했다

마치며

정리 하는 글을 벨로그의 포스팅 하는것은 내가 배운 지식을 남에게 설명할수 있을정도로 이해하기 위해서 스스로의 공부를 위해 시작했지만 요번글을 쓰면서 참으로 글과 그림으로 남에게 설명하기가 참 어려운(내 기준) 내용도 참 많겠구나라는 생각이 들며 그때마다 내가 전달하고 이해한 내용을 부족하지만 솔직히 정리하자고 생각하게된 계기가 되었다

요번에는 이진트리의 구현에 대해 공부한 내용을 정리하려고 한다 비선형 자료구조에 대해 계속 공부하면서 확실히 선형 자료구조 보다 어렵다고 생각하지만 차근차근 배운것들을 정리해 나가보니 개념에 대해 조금씩 이해가 가고있다

이진 트리의 구현

이진트리의 종류

이진트리는 크게 2가지 종류로 구현이 가능하다

- 1.연결 리스트 이진 트리 - 2.배열 기반 이진 트리

각각이 어떻식으로 구현 되는지에 대해 알아보자

1.연결 리스트 이진 트리

그림을 보면 연결 리스트 기반 이진트리는 구현은 그림으로 볼때 직관적으로 이해하기가 쉽다 루트 노드 A가 B,C를 그리고 노드B가 D,E를 가키키게 만들어서 이진 트리를 구현한다

2.배열 기반 이진 트리

연결 리스트 기반 이진 트리와의 차이점을 살펴보자 먼저 이진 트리 노드 위의 숫자가 적혀있는것을 볼수있고 그 숫자를 기반으로 배열에 데이터를 저장한것을 확인할수있다 여기서 우리가 한 가지 집고 갈것은 배열의 첫번째 배열에는 값을 비워 두었다는 것이다 이것은 배열 이진 트리의 구현에서 첫번째를 비워두는 것이 여러모로 편하기 때문이다

이진 트리의 구조체 정의

typedef int BTData;

typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
} BTreeNode;

위 코드는 이진 트리 관련 헤더파일에서 이진 트리 구조체와 관련된 코드를 가지고 온거다 여기서 우리가 재밌게 생각해 볼것은 노드의 정의 자체가 자료구조의 정의를 의미한다 는점이다 우리가 자료구조를 공부 하면서 구현에 있어 노드와 자료구조를 각각 구분하여 구조체를 정의해 왔다 (예시 스택 에서 노드와 스택을 각각 구분함) 하지만 연결 리스트 기반 이진 트리에서는 노드 자체가 이진트리를 표현하고 있다 우리가 A라는 노드를 한개 생성했다고 가정하고 각각의 left와 right에 null 값을 넣었다고 가정한다면 위 그림처럼 이진트리가 형성되었다는 사실을 알수있다

이진 트리의 ADT 정의

1.BTreeNode * MakeBTreeNode(void); -이진 트리 노드를 생성하고 주소값을 반환 한다.

2.BTData GetData(BTreeNode * bt); -노드에 저장된 데이터를 반환한다.

3.void SetData(BTreeNode * bt, BTData data); -노드에 데이터를 저장한다.data로 전달된 값을 저장한다.

4.BTreeNode * GetLeftSubTree(BTreeNode * bt); -왼쪽 서브 트리의 주소 값을 반환한다.

5.BTreeNode * GetRightSubTree(BTreeNode * bt); -오른쪽 서브 트리의 주소 값을 반환한다.

6.void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub); -왼쪽 서브 트리를 연결한다.

7.void MakeRightSubTree(BTreeNode * main, BTreeNode * sub); -오른쪽 서브 트리를 연결한다.

이진 트리의 ADT 구현

1.BTreeNode * MakeBTreeNode(void);

BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

2.BTData GetData(BTreeNode * bt);

BTData GetData(BTreeNode * bt)
{
    return bt->data;
}

3.void SetData(BTreeNode * bt, BTData data);

void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}

4.BTreeNode * GetLeftSubTree(BTreeNode * bt);

BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}

5.BTreeNode * GetRightSubTree(BTreeNode * bt);

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}

6.void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);

    main->left = sub;
}

7.void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);

    main->right = sub;
}

6,7번 함수 코드를 정리해보자면 "왼쪽 오른쪽에 서브 트리가 존재한다면,해당 트리를 삭제하고 새로운 서브 트리를 연결해라 " 라고 해석할수 있을거다 위의 코드 방식은 한가지 중요한 문제점을 가진다 만일 삭제하는 서브 트리가 1개의 노드로 구성되어있다면 문제가 발생하지 않지만 2개 이상이라면 메모리 누수가 발생하게 된다

이러한 문제를 해결 하기위해서는 우리가 트리의 모든 노드를 순회할 필요할 필요가 있다 순회에 대해서는 다음 장에서 정리하도록 하자

오늘은 드디어 비선형 구조인 트리에 대해 공부를 시작헀다 비선형 구조 부터가 진짜 자료구조의 벽에 시작이라는데 잘극복하기를 나 자신에게 바라며 트리에 대해 공부한 내용을 천천히 정리해 나가보자

오늘 정리해볼 내용

• 1.트리의 기본적인 구조
• 2.트리 관련 용어
• 3.이진 트리,서브 트리의 개념

1.트리의 기본적인 구조

트리는 계층적 관계를 표현하는 자료구조이다

계층적 관계라는 말은 처음 공부할 당시에는 생소한 단어였지만 예시를 그림으로 확인하니 어떤 느낌인지 바로 알수있었다 그림에 예시 말고도 족보,조직도,선택 알고리즘 등등 우리가 접할수 있는 다양한 사례가 존재한다 트리는 말그대로 나무가 가지를 늘려가는 형태와 유사하다

2.트리 관련 용어

트리와 관련된 용어들을 정리해 보자 위의 그림을 기준으로 정리한다

• 노드(node) 트리의 구성요소에 해당하는 A,B,C,D,E,F,와 같은 요소

• 간선(edge) 노드와 노드를 연결하는 연결선

• 루트 노드(root node) 트리 구조에서 최상위에 존재하는 A와 같은 노드

• 단말 노드(terminal node) 아래로 또 다른 노드가 연결되어 있지 않는 E,F,C,D와 같은 노드

• 내부 노드(internal node) 단말 노드를 제외한 모든 노드로 A,B와 같은 노드

노드간의 관계

• 부모,자식 관계 그림에서 A와 B는 부모관계 이다 A에서 B가 파생된 관계

• 형제 관계 같은 부모 A 에서 파생된 관계들 끼리는 형제 관계라고 한다 (B,C,D는 A에서 파생됨으로 형제 관계이다)

• 후손 관계 A와E는 후손관계 이다

관계는 상대적으로 결정된다 A,B가 부모관계에서 B가 자식이지만 B,E에서는 B가 부모가 된다

3.이진 트리,서브 트리의 개념

• 서브트리의 이해 큰 트리에 속하는 작은 트리들을 가리켜 서브 트리 라고 명칭한다 D,E가 자식 노드를 생성한다면 B입장에서는 D,E에 파생된 트로 또한 서브 트리가 된다

• 이진 트리

  이진 트리의 조건 1.루트 노드를 중심으로 두 개의 서브트리로 나눠진다 2.나뉘어진 두 서브 트리도 모두 이진 트리여야 한다

트리의 어떤 부분을 짤라놓고 봐도 이진 트리를 만족해야한다 4번 그림역시 이진트리의 조건을 만족한다

이런 트리는 당연히 이진 트리가 맞다 이진 트리의 조건을 만족시키지 않는것 처럼 보이지만 사실 이것은 일종의 이진트리의 약속인데 노드를 더 연결해서 2개의 이진트리를 만족시킬수있다면 이진 트리이다 즉 위의 그림에서 B,D,F,G,C,G에 노드를 더 추가한다면 이진트리 조건이 만족된다 그러면 추가해서 만족할수만 있다면 그것또한 이진트로이다 여기서 추가해서 공집합을 연결시키면 이해가 훨씬 수월하다

그림으로 보니 이진트리가 맞음을 확인할수있다

3-2.포화 이진 트리와 완전 이진 트리

• 포화 이진 트리 모든 레벨이 꽉 찬 이진트리 이다

• 완전 이진 트리 모든 레벨에서 꽉 찬상태는 아니지만 차곡차곡 빈 틈없이 싸여있는 상태 이다 여기서 차곡차곡 쌓여있다는 것인 왼쪽에서 오른쪽의 순서대로 쌓여있는 상태를 말한다 그림을 보면 이해가 쉽다

위의 그림과 똑같아 보이지만 오른쪽에서 부터 쌓여있음이 보인다 이런경우에는 완전 이진 트리로 정의 되지 않는다

마치며

요번에는 트리를 본격적으로 공부하기 위해 필요한 간략한 개념을 정리해 보았다 다음번 떄는 트리의 구현을 공부하고 정리해 보겠다

오늘은 원형 큐에 대해 공부한 내용을 정리해 볼것이다 원형 큐는 저번글에서 큐에 더이상 데이터를 추가할 공간이 부족한 상황에서 앞서 사용하지 않는 메모리 공간을 활용하는 방법이다 그림은 일반적인 형태의 큐이다 하지만 우리가 이것을 원형의 순환되는 구조로서 생각해 본다면 다음과 그림과 같이 확인할수 있을거다 그렇다면 어떻게 원형 큐가 연산되는지 정리해보자

원형 큐의 연산

그림에서 데이터가 하나 추가되니 R이 오른쪽으로 한칸 이동했다 (이해를 돕기위해 오른쪽 이동으로 일관 통일 했다)

그렇다면 반대로 데이터를 삭제하면 어떻게 될까?

F가 오른쪽 한칸 이동하고 "A"가 삭제 된것을 확인할수 있다 원형큐의 기본적인 동작을 알아보았다 하지만 이러한 원형 큐도 한가지 문제점이 있다 비어있는 큐와 꽉찬큐를 컴퓨터가 구분하기어렵다

그림처럼 원형 큐에 데이터를 게속 추가하거나 계속 삭제했다면 다음 그림처럼 포인터 변수들이 존재할텐데 컴퓨터로서는 이둘의 포인터 위치관계가 같기 때문 (F,R이 1칸 차이나는 상황) 구분하기가 어렵다 그렇다면 이러한 문제점을 개선하기 위해서는 어떻게 해야할까?

개선된 원형 큐

개선된 원형 큐는 딱히 거창한게 없다 단순히 1번째 배열에는 아무런 값을 넣지 않는것이다 이로 인해 F는 오직 삭제의 역활만을 담당 할수 있게 되어서 구분이 용이해 짐을 알수있다 단순연결 리스트를 공부할때 더미노드를 만드는것과 굉장히 유사한 원리라고생각한다

오늘 정리해볼 내용은 큐 이다 우리는 앞서 스택에 대해 정리해 보았다 스택이 후입선출 자료구조라면 큐는 선입선출 (FIFO)형 자료구조 이다 흔히 우리가 일상애서 보는 "줄서기"와 유사하다고 볼수있다

우리가 놀이기구 줄서기를 할떄 당연히 1번 으로 줄을 선사람은 1번으로 놀이기구를 탈것이다 이것이 큐의 기본적인 구조이다 그러면 이재 큐의 ADT를 정의해보자

큐의 ADT

큐 자료구조의 ADT룰 살펴보자

void QueueInit(Queue * pq) -큐의 초기화를 진행 -큐 생성후 제일 먼저 호출되어야함

int QIsEmpty(Queue * pq) -큐가 빈 경우 1 아니면 0을 반환한다

void Enqueue(Queue * pq, Data data) -큐에 데이터를 저장한다 -매개변수 data로 저장된 값을 저장

int Dequeue(Queue * pq) -저장순서가 가장 앞선 데이터를 삭제한다 (처음으로 줄선 사람을 입장시킨다) -삭제된 데이터는 반환한다 -본 함수의 호출을 위해 데이터가 1개 이상임을 보장한다

int QPeek(Queue * pq) -저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다 (처음으로 줄선 사람의 값만 확인) -본 함수의 호출을 위해 데이터가 1개 이상임을 보장한다

ADT구현에 앞서 큐의 2가지 형태에 대해 알고가자

큐는 크게 2가지 형태로 나뉘게 된다 1.배열 큐 2.연결 리스트 큐

그러면 각각의 큐가 어떻게 형성되는지에 대해 알아보자

배열 기반 큐

그림을 통해 천천히 정리해 나가보자 먼저 배열을 선언했다 배열을 줄서는 라인이라고 생각해보자 F,R은 줄에서 각각 처음과 마지막을 나타내는 역활을 한다 먼저 줄에 데이터 1개가 들어왔다고 생각해보자 지금 줄을 서고 있는 데이터는 A혼자이니 F,R모두 A를 가리킬 것이다 이상황 에서 줄에 데이터 1개가 더왔다고 생각해보자 F는 여전히 첫번쨰인 A를 가리키고 있다 하지만 R은 줄에 맨마지막인 B를 가리키고 있다 여기서 A가 반환되면 어떻게 될까? 그림처럼 F가 뒤로 1칸이동되고 배열의 처음칸이 비어버렸다 우리는 데이터가 추가 되거나 삭제될떄 F,R에 이동에 대해 알아보았다 그러면 이제 1가지 상황을 놓고 이야기 해볼건데 먼저 1가지 사실에 대해 이야기 하고 가자 우리는 포인터나 배열을 공부할떄 비어있는 값은 어떤 재앙을 불러올지 모르니 0이나 NULL값으로 초기화 시킨다고 공부했다 하지만 여기서는 빈 배열 이나 포인터를 그냥 비어있는 상태로 나둘것이다 이것은 실무에서도 코드를 구성할떄 사용하기에 비어있는 포인터나 배열에 예민하게 반응할 필요가 없음을 기억하자 그러면 그림을 통해 계속 정리해 가보자 이처럼 배열을 만들고 계속해서 데이터를 추가하다 보면 언제가 그림처럼 더이상 데이터를 담을 공간이 부족해 지는 순간이 올것이다 그렇다면 우리는 어떻게 이문제를 해결할수 있을까? 답은 우리가 앞서 비워놨던 배열들을 재사용 하는거다. 그렇다면 어떻게 우리는 앞에 빈배열들을 활용할수 있는지는 다음장에서 정리해 보겠다