자료구조란?


프로그램이란 , 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는것이다. 이때, 데이터의 표현은 데이터의 저장을 포함하는개념이며 , 데이터의 저장을 담당하는 것이 자료구조이다.


선형구조의 자료구조는 리스트 , 스택 , 큐 가있고 , 비선형구조의 자료구조는 트리 , 그래프가 있다.


알고리즘이란?


알고리즘은 자료구조등으로 표현 및 저장된 데이터를 대상으로하는 문제의 해결방법이다. 

알고리즘은 자료구조에 의존적이다. ( 자료구조에 따라서 효율적인 알고리즘은 달라진다 ) 


알고리즘의 성능 분석방법


알고리즘을 평가하는 두가지 요소는 속도와 메모리 사용량에 관한것이다. 속도에 해당하는 알고리즘의 수행시간 분석결과를 시간복잡도라고 하고 , 메모리 사용량에 대한 분석결과를 가리켜 공간복잡도라고 한다.

메모리를 적게쓰고 속도또한 빨라야 최적의 알고리즘이지만 , 보통 일반적으로 알고리즘을 평가할때는 메모리의 사용량보다 실행속도에 초점을둔다.


알고리즘의 수행속도를 평가할때는 연산의 횟수를센 후 , 처리해야할 데이터 수  n 에 대한 연산횟수의 함수 T(n)을 구성하면된다. ( 연산횟수를 통해 알고리즘의 빠르기를 결정한다 )

이때 중요한것은 n 에 대한 T(n)의 증가정도에 있다. ( n 이 클때가 중요 ) 보통 안정적인 성능을 보장하는 알고리즘은 구현의 난이도가 높은편이다.

따라서 종합적으로 사고하고 판단하는 능력이 중요하다.


순차 탐색의 알고리즘과 시간복잡도 분석의 핵심요소


#include<stdio.h>


int LSearch ( int ar[] . int len , int target )

{

int i;

for ( i=0;i<len;i++)

{

if(ar[i] == target)

return i;

}

return -1;

}




T(n)을 구하는방법


T(n)을 구할때는 , 핵심이 되는 연산을 찾아서 ( 핵심이 되는 연산이란 , 그 연산이 이루어졌을때 다른 연산들또한 연산횟수가 늘어나는것을 말한다 , 위 함수의 경우 == 연산이다 )  핵심 연산의 횟수를 대상으로 시간 복잡도를 분석하면된다,

알고리즘의 성능을 판단하는데 있어서 중요한것은 최악의 경우(n개의 데이터에서 n 번의 수행횟수를 가질경우 )이다.


순차 탐색 알고리즘의 시간복잡도 : 최악의경우


최악의 경우 , 데이터의 수가 n 개일때 , 최악의 경우에 해당하는 연산횟수는 n 이다.

따라서 T(n) = n 이다.


순차 탐색 알고리즘의 시간복잡도  : 평균적인 경우


가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고가정.

가정 2. 배열의 첫 요소부터 마지막 요소까지 탐색대상이 존재할 확률은 동일하다.


탐색대상이 존재하지 않을경우의 연산횟수  n 


탐색대상이 존재하는 경우의 연산횟수 n/2 ( 탐색대상이 존재할확률이 동일하므로)


배열에 존재하거나 존재하지않을경우의 확률이 50%이므로 , (n+n/2)/2 = 3/4*n 이다.


이진탐색 알고리즘의 소개


이진탐색은 순차탐색보다 훨씬 좋은 성능을 보인다 . 하지만 이를 적용하기위해서는 배열이 정렬되어있어야한다.



C++의 형변환 연산자


C++은 무조건적인 형변환을 해주는 C스타일의 형변환보다 안전하게 형변환하기 위해 4개의 형 변환 연산자를 제공한다,


dynamic_cast

static_cast

const_cast

reinterpret_cast


위 형 변환 연산자를 사용하면 프로그래머는 자신이 의도한 바를 명확히 표시할 수 있다.


dynamic_cast : 상속관계에서의 안전한 형변환


dynamic_cast<T>(expr)


<>사이에 변환하고자하는 자료형의 이름을 두되 , 객체의 포인터 또는 참조형이 와야하며 () 사이에는 변환의 대상이 와야한다. 적절한 변환일경우 형변환된 데이터를 반환하지만 요구한 형 변환이 적절하지 않은 경우에는 컴파일 에러가 발생한다.


dynamic_cast 변환은 상속관계에 놓여있는 두 클래스 사이에서 유도클래스의 포인터 및 참조형 데이터를 기초형 포인터 및 참조형 데이터로 형변환 하는경우 변환을 허가한다. 즉 , dynamic_cast 연산자를 사용했다는것은 상속관계에 있는 유도클래스의 포인터 및 참조형 데이터를 기초 클래스의 포인터 및 참조형 데이터로 형 변환하겠다는 뜻이다.


class Truck : Car 일경우


Truck * ptruck = new Truck() ;

Car * pcar = dynamic_cast<Car*>(ptruck);


static 변환 : A타입에서 B 타입으로


static_cast<T>(expr)


static_cast를 사용하면 유도클래스의 포인터 및 차몾형 데이터를 기초클래스의 포인터 및 참조형 데이터로 뿐만아니라 , 기초 클래스의 포인터 및 참조형 데이터도 유도클래스의 포인터 및 참조형 데이터로 아무런 조건없이 형변환해준다. ( dynamic_cast 보다 넓은 범위로 형변환 , 연산속도 빠름 )


Car * pcar1 = new Truck();

Truck *ptruck1 = static_cast<Truck*>(pcar1); // 올바른 사용

Car * pcar2 = new Car();

Truck * ptruck1 = static_cast<Truck*>(pcar2);// 잘못된사용 but 컴파일 가능 -> 책임은 프로그래머가 져야함


static_cast 연산자는 dynamic_cast 보다 많은 형 변환을 허용하기때문에 , 이에따른 책임은 프로그래머가 져야하고 , 따라서 dynamic_cast 연산자를 사용할 수 있는 경우에는 이를 사용하여 안전성을 높여야한다.


static_cast 연산자는 기본 자료형 데이터간의 형변환에도 사용된다.

즉 , static_cast 연산자는 기본자료형간의 형변환과 클래스의 상속관계에서의 형 변환만 허용한다.


double result = static_cast<double>(20)/3;


const_cast : const의 성향을 삭제한다


const_cast<T>(expr)


const_cast형 변환연산은 함수의 인자전달시 const 선언으로인한 형의 불일치가 발생하여 인자의 전달이 불가능할때 , 유용하게 사용된다.


void ShowString(char * str)

{

cout<<str <<endl;

}

int main (void)

{

const char * name = "홍길동";

ShowString(const_cast<char*>(name));

return 0;

}


reinterpret_cast : 상관없는 자료형으로의 형 변환


reiinterpret_cast 연산자는 전혀 상관없는 자료형으로의 형 변환에 사용된다. 즉 , 포인터를 대상으로하는 , 그리고 포인터와 관련이 있는 모든 유형의 형 변환을 허용한다.


int num =0x010203;

char * ptr = reinterpret_cast<char*>(&num);


dynamic_cast 두번째 이야기 : polymorphic 클래스 기반의 형 변환


dynamic_cast도 기초 클래스의 포인터 및 참조형 데이터를 유도 클래스의 포인터 및 참조형 데이터로의 형 변환을 허용하는경우가 있는데 , 이때는 기초클래스가 Polymorphic 클래스인 경우이다 . Polymorophic 클래스란 하나이상의 가상함수를 지니는 클래스를 뜻한다( 추상클래스 ) ( virtual 포함 )


Sosimple클래스가 추상클래스라고할때


SoSimple * simPtr = new SoComplex;

SoComplex * comPtr = dynamic_cast<SoComplex* >(simPtr);


이때 , dynamic_cast와 static_cast와의 차이는 dynamic_cast의 경우


SoSimple * simPtr = new SoSimple

SoComplex * comPtr = dynamic_cast<SoComplex *>(simPtr);


comPtr이 simPtr 을 가리킬 수 없을경우 , 형변환의 결과로 NULL을 반환한다는 것이다 . ( comPtr에 NULL값이 저장된다 ) 이때, if문을 이용해 형변환 성공 유무를 판단할 수 있다.


bad_cast 예외


bad_cast 예외는 dynamic_cast 연산자를 이용한 형변환 과정에서 발생할 수 있는 예외이다.


try

{

SoSimple simObj;

SoSimple& ref = simObj;

SoComplex& comRef = dynamic_cast<SoComplex&>(ref);

}

catch(bad_cast expt)

{

cout<<expt.what()<<endl;

}


참조자 대상으로는 NULL을 반환할 수 없기때문에 , 이러한 상황에서는 bad_cast 예외가 발생하며 , 이를 catch 문으로 잡아서 예외처리를 해야한다.

try catch 그리고 throw


if 문을 사용하여 예외문을 구성할 수 있지만 , 코드의 가독성을 위하여 C++ 은 try catch 메커니즘을 제공한다. 


try

{

// 예외처리 발생지역

}


try 블록은 예외발생에 대한 검사의 범위를 지정할때 사용한다. 즉 , try 블록 내에서 예외가 발생하면 C++ 예외처리 메커니즘에 의해 처리된다. try 블록 내에서 예외가 발생하면 catch 블록이 실행되고나서, 예외가 발생한 지점 이후를 실행하는것이 아니라, catch 블록의 이후가 실행된다.



catch( 처리할 예외객체의 자료형 )

{

//예외처리 코드의 삽입

}


catch 블록은 try 블록에서 발생한 예외의 처리를 담당하는 코드가 담기는 영역이다. catch 블록은 try 블록의 바로 뒤에 이어서 등장한다. ( 중간에 다른 문장이 올 수 없다. )


throw expn;


키워드 throw는 예외가 발생했음을 알리는 문장의 구성에 이용된다. throw에 의해 던져진 예외데이터는 예외데이터를 감싸는 try 블록에 의해서 감지가되어 이어서 등장하는 catch 블록에 의해 처리된다. 이때, throw 절에 의해 던져진 예외데이터의 자료형과 catch 블록의 매개변수 자료형은 일치해야한다.


예외의 전달


함수 내의 throw 절에의해 예외가 발생했을때 , 예외를 처리하기위한 try catch 문이 함수 내에 존재하지않아서 예외처리가 되지않았다면 , 예외처리에 대한 책임은 그 함수를 호출한 영역으로 넘어가게된다. ( 그 함수가 호출된 절을 감싸는 try 문에의해 감지된다 )

또한 , 함수 내에서 함수를 호출한 영역으로 예외데이터를 전달하면 , 해당 함수는 더이상 실행되지않고 종료된다 . 


스택 풀기


예외처리가 되지 않아서 함수를 호출한 영역으로 예외 데이터가 전달되는 현상을 가리켜 스택풀기라고한다. 예외가 처리될때까지 호출된 함수의 역순으로 예외데이터가 전달되며 함수의 종료가 이루어지므로 함수의 스택이 소멸된다고 하여 스택풀기라고 한다.

main 함수까지 예외처리가 전달되었는데 , main 함수에서도 예외를 처리하지못하면 terminate 함수 ( 프로그램을 종료시키는 함수 )가 호출되면서 프로그램이 종료된다.

throw가 던진 자료형과 catch 가 받는 자료형이 다르다면 이때도 같은 자료형을 받는 catch 가 나올때까지 예외가 전달된다.


하나의 try 블록과 다수의 catch 블록


자료형을 달리하여 try 블록 내에서 발생하는 둘 이상의 예외를 처리할 수 있다.


전달되는 예외의 명시


예외가 있는 함수를 정의할때는 해당 함수의 throw 호출문장을 감싸는 적절한 try catch 블록을 구성하기 쉽게하기위해 함수 내에서 발생한 예외의 종류를 명시해 주는것이 좋다.


int ThrowFunc(int num) throw( int ,  char )

{

...

}


try 

{

ThrowFunc(20);

}

catch(int expn){  .. }

catch(char expn){ ... }


위처럼 선언될경우 함수로부터 int 혹은 char 데이터의 예외가 전달되어야하며 , 다른 종류의 데이터가 전달될경우 terminate 함수가 호출되고 , 프로그램이 종료된다.


int SimpleFunc(void) throw ()

{

....

}


위의 함수에는 전달되는 예외의 자료형을 명시하는부분이 비어있다 . 이는 이 함수가 어떠한 예외도 전달하지않음을 의미하며 , 예외가 전달될경우 프로그램이 종료된다.


예외 클래스의 설계


예외 발생을 알리는데 사용되는 객체를 가리켜 예외객체라고 하며 , 이 객체의 생성을 위해 정의된 클래스를 예외클래스라고 한다.


class DepositException

{

private :

int reqDep;

public :

DepositException(int money) : reqDep(money)

{ }

void ShowExceptionReason()

{

cout<<"예외메세지 "<<reqDep<<"은 입금 불가" <<endl;

}

};

class Account

{

private :

char accNum[50];

int balance;

public :

Account ( char * acc, int money) : balance(money)

{

strcpy(accNum,acc);

}

void Deposit(int money) throw (DepositException)

{

if (money<0)

{

DepositException expn(money);

throw expn;

}

balance += money;

}

};

int main (void)

{

Account myAcc("12345-12345",4000);


try

{

myAcc.Deposit(2000);

myAcc.Deposit(-100);

}

catch ( DepositException expn)

{

expn.ShowExceptionReason();

}

return 0;

}


상속관계를 이용한 예외클래스의 단순화


class AccountException 

{

public : 

virtual void ShowExceptionReason()  = 0; // 순수 가상함수

}

class DepositException : public AccountException

{

private :

.....

public :

....

void ShowExceptionReason() // 순수 가상함수 오버로딩

{

cout<< "예외메시지 : "<<reqDep<<"는 입금할 수 없습니다 " <<endl;

}

};


예외의 전달방식에 따른 주의사항


AAA객체를 BBB객체가 상속하고, BBB객체를 CCC 객체가 상속하는경우 , AAA BBB CCC 객체들이 전부 예외를 던지면 catch 문을 구성할때는 CCC BBB AAA 객체의 예외를 전달받는 순서로 선언해야한다. 이유는 AAA 객체를 먼저 받게되면 , CCC 객체는 AAA 객체를 상속하므로 AAA 객체의 예외를 받는 catch 문에서 처리되기 때문이다.


예외처리와 관련된 또다른 특성들


new 연산자에 의해서 발생하는 예외


new 연산에 의한 메모리 공간의 할당이 실패하면 bad_alloc 이라는 예외가 발생한다. bad_alloc 은 헤더파일 new에 선언된 예외클래스로서 메모리공간 할당이 실패했음을 알리는 용도로 사용된다.


모든 예외를 처리하는 catch 블록


catch ( ... ) // ...은 전달되는 모든 예외를 전부 받아주겠다는 선언이다.

{

...

}

보통 마지막 catch 블록에 덧붙여지는 경우가 많다


예외 던지기


catch 블록에 전달된 예외는 다시 던져질 수 있다 . 이로 인해서 하나의 예외가 둘 이상의 catch 블록에 의해서 처리되게 할 수 있다.


void Divide(int num1, num2)

{

try

{

if(num2==0)

throw 0;

cout <<" 몫: " <<num1/num2<<endl;

cout<< "나머지 : "<<num1%num2<<endl;

}

catch (int expn)

{

cout << "firts catch "<<endl;

throw; // 예외 다시던지기

}

}

int main (void)

{

try

{

Divide(9,2);

Divide(4,0);

}

catch(int expn)

{

cout<<"second catch"<<endl;

}

return 0;

}



+ Recent posts