Pw4ngC0

자료구조 : 데이터의 표현 및 저장 방법

자료구조의 분류

선형 구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식

비선형 구조 : 데이터를 나란히 저장하지 않는 구조

자료구조와 알고리즘

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

-> 자료구조가 결정되면 그에 따른 효율적인 알고리즘을 결정할 수 있다.

     알고리즘은 자료구조에 의존적이다.

알고리즘 성능 분석 방법

잘 동작하고 좋은 성능을 보장받기를 원한다면 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다.

자료구조와 알고리즘을 평가하는 두가지 요소는 '속도'와 '메모리 사용량' 이다.

속도에 해당하는 수행시간 분석결과를 '시간 복잡도(time complexity)' 라고 하고, 메모리 사용량에 대한 분석 결과를 '공간 복잡도(space complexity)'라고 한다.

알고리즘 수행 속도 평가 방식

1.연산의 횟수

2.데이터의 수 n에 대한 연산횟수 T(n) 구성.

함수 T(n)을 구성하면 데이터 수의 변화에 따른 연산 횟수 변화를 한눈에 파악할 수 있어, 둘 이상의 알고리즘을 비교하기 용이해진다.

데이터 수에 따라 연산횟수도 달라지기 때문에 상황에 맞는 알고리즘을 찾아야 한다.

탐색 알고리즘에서는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

비교 연산의 수행횟수가 줄어들면 < 연산과 ++ 연산의 수행횟수도 줄어들고, 비교연산의 수행횟수가 늘어나면 < 연산과 ++ 연산의 수행횟수도 늘어나기 때문에 다른 연산들은 == 연산에 의존적이다.

위 탐색 알고리즘은 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면된다.

=> 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 한다.

모든 알고리즘에는 가장 행복한 경우와 가장 우울한 경우가 각각 존재하며, 이를 '최선의 경우(best case)'와 '최악의 경우(worst case)'라 한다. 그러나 알고리즘을 평가하는데 있어서 '최선의 경우'는 관심 대상이 아니다. 알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우' 이다.

게임 저장할 함수들 사용을 편하게 하기 위해서 다른 파일에 존재하는 저장할 변수들을 extern을 이용하여 불러왔다. 파일을 저장할떄 1을 먼저넣음으로써 내용이 저장되어있음을 알리고 파일을 삭제하는 것 대신 저장한내용들을 없애는것을 표기하기 위해 저장할때 숫자 0을 먼저 넣어주었다..

game.h에서 열거형 enum을 사용하여 각 가위 바위 보를 1 ,2 ,3에 대응 시켰다.

WhoIsWinner를 처음에는 모든 경우에 case들을 분류했었는데 훨씬 간편하게 고친것 같다.

64비트와 32비트 구분

CPU는 I/O버스를 통해 외부로 데이터를 전송하거나, CPU 내부로 수신한다.

데이터를 송수시한 할때 한번에 전송 및 수신할 수 있는 데이터의 크기에 따라 32비트 시스템과 64비트 시스템이 나뉘게 된다. 즉, CPU가 버스를 통해 한번에 송신 및 수신 할 수 있는 크기가 32비트면 32비트 컴퓨터이고, 64비트면 64비트 컴퓨터가 된다.

또다른 기준은 데이터 처리 능력(CPU)이다. CPU는 외부에서 들어오는 데이터를 처리해야 하는데, 32비트 컴퓨터는 한번에 32비트 데이터를, 64비트 컴퓨터는 한번에 64비트 데이터를 처리할 수 있다.

프로그래머 입장에서의 64비트 컴퓨터

표현할 수 있는 주소값의 크기가 클수록 좋다. 메모리 공간만 충분하다면 주소값의 범위가 넓을수록 더 많은 공간을 사용할 수 있기 때문이다. 32비트 컴퓨터에서는 32비트 포인터를, 64비트 컴퓨터에서는 64비트 포인터를 사용하는 것이 가장 좋다.

4비트를 주소값을 표현하기 위해 사용한다는 것은 0000부터 1111까지의 16개의 주소를 표현할 수 있다는 것이다. 즉 많은 비트 수를 활용하여 주소를 표현할 수록, 표현할 수 있는 주소의 범위는 더 넓어진다. 표현할 수 있는 주소의 범위가 넓어지면, 그만큼 활용할 수 있는 메모리 크기도 커진다.

프로그램 구현 관점에서의 WIN32 vs WIN64

64비트 컴퓨터에서의 자료형 표현

운영체제            모델            char             short          int             long             포인터

windows           LLP64           1바이트        2바이트      4바이트      4바이트         8바이트

UNIX               LP64             1바이트        2바이트      4바이트     8바이트          8바이트

Windows에서는 LLP64데이터표현 모델을 따르는데 int와 long 모두 4바이트 표현하고 포인터만 8바이트로 표현하는 방식이다. 이는 32비트 시스템과의 호환성을 중시한 모델이다.

64비트와 32비트 공존의 문제점

ex)    LLP64기반

#include                

int main(void)

{

          int arr[10] = {0, };

          int arrVal = (int)arr;                           <-데이터 손실 발생

          printf("pointer : %d \n",arrVal);

          return 0;

} 

위 코드는 32비트 시스템에서는 전혀 문제가 되지 않는다. int형과 포인터 모두 4바이트로 표현되기 때문이다. 그러나 64비트 시스템에서는 문제가 된다. int형 포인터 arr은 8바이트인데 이것을 int형 변환을 시도하기 때문이다. 64비트 시스템에서는 포인터를 int, long등 4바이트 정수형으로 변환해서는 안된다.

64비트 windows 시스템에서는 LLP64가 기본 모델이므로 int는 4바이트, 주소값인 포인터는 8바이트로 표현된다. 때문에 위 예제는 형 변환 과정에서 데이터 손실이 발생할 수 있다. 64비트 windows시스템은 16테라(1024 X 16G바이트)바이트의 메모리 공간을 활용할 수 있도록 디자인 되었다. 따라서 배열 arr이 4G 이하의 메모리 영역에 할당되어 4바이트로 주소값 표현이 가능하다면 데이터 손실은 발생하지 않는다.

Ploymorphic  자료형

WIN64 기반으로 넘어가면서 Ploymophic 자료형을 정의한다.

Ploymorphic 단어는 "다양한 모습이 있는" 또는 "다형적"이라는 뜻으로 해석된다. 자료형이 다형적이라는 것은 상황과 환경에 따라서 그 자료형이 의미하는 바가 유동적이라는 뜻이다.

Ploymorphic 자료형 정의

#if define (__WIN64)

      typedef  __int64     LONG_PTR;

      typedef  unsigned  __int64    ULONG_PTR;

      typedef  __int64   INT_PTR;

      typedef  unsigned __int64  UINT_PTR;

#else

     typedef   long    LONG_PTR;

     typedef   unsinged __int64  UINT_PTR;

     typedef   int       INT_PTR;

     typedef   unsigned int    UINT_PTR;

#endif

   -----매크로 _WIN64는 64비트 기반으로 프로젝트 구성 시 자동으로 삽입되는 매크로이다. 마찬가지로 32비트 기반으          로 프로그램 구성 시 매크로 _WIN32가 자동으로 삽입된다. 이 매크로는 조건부 컴파일 및 실행의 기준이 된다.

위 변수들에 PTR이라는 이름이 붙은 이유는 포인터 자료형이 아니라 포인터값 기반의 산술연산을 위해 정의된 자료형이기 때문에 PTR이라는 이름이 붙는다.

Ploymorphic자료형은 시스템 함수의 32비트, 64비트간 호환성을 높이기 위한 방법으로 사용된 것이다.

오류의 확인

GetLastError 함수와 에러코드

Windows 시스템 함수를 호출하는 과정에서 오류가 발생하면, GetLastError 함수 호출을 통해 오류의 원인을 확인할 수 있다. 오류가 발생했을 때, 이어서 바로 GetLastError 함수를 호출하면 오류원인에 해당하는 에러코드를 얻을 수 있다.

GetLastError함수

DWORD GetLastError(void);

GetLastError 함수를 통한 오류확인은 오류가 발생한 직후에 바로 해야한다. Windows 시스템 함수가 호출될 때마다 GetLastError 함수가 반환하는 에러코드는 갱신된다.

위와같이 w옵션을 주어 fopen함수 사용시 파일명에 해당하는 파일이 없다면 새로 생성하여 안에 데이터를 입력한다.

소스파일에서 설명했듯이 리눅스에서 한글은 2~3바이트로 불규칙 적이다. 실행화면을 보면 2개의 문자를 요청했으며 하나는 정상적으로 출력이 완료되었지만 다른 하나는 비정상적인 출력이 되는것을 알 수 있다.이것은 출력하려는 데이터의 크기가 정확하지 않아서 발생하는 문제이다.

fopen함수에서 wb옵션을 준것은 바이너리 모드로 열어서 쓰겠다는 의미이다. 바이너리 모드란 숫자 4를 넣을때 아스키코드값이 들어가는 것이아니라 이진데이터 4가 들어가는 것을 의미합니다. 저장된 파일을 열어보면 알수 없는 형태로 저장되는것을 확인할 수 있습니다.

rb는 바이너리모드로 열어서 읽는 다는 옵션이다.

바이너리 모드로 열어서 저장한데이터는 바이너리모드로 열어서 읽으면 저장한 그대로 출력이 가능하다.

위 소스코드로 입력한 결과이다. wt는 텍스트 모드로 열어서 쓴다는 의미이다. 데이터를 아스키코드값으로 저장한다.

날짜는 바이너리모드로 입력하고 다른 데이터들은 텍스트 모드로 입력하는 파일이다.

바이너리 모드로 된 데이터는 바이너리모드로 읽고 텍스트모드로 저장된 데이터는 텍스트 모드로 읽으면된다.

바이너리모드 관련함수는 fread와 fwrite이고 텍스트모드는 fgets, fputs 등등이다.

날짜와 지역 오전오후만 입력해서 해당 데이터를 출력하는 것이다. 검색하는 데이터만 읽어야한다고 생각을 해서 문제해결에 어려움이 있었다. 그냥 데이터를 다읽어서 입력한 데이터와 비교하여 같은 부분만 출력하는 형태로 문제를 풀었다.

파일을 바이너리모드로 열고 텍스트 문자를 입력하고 바이너리모드로 열어서 데이터를 읽는 것이다. 문자열을 읽어서 출력하는 부분에서 fgets를 사용하면 편했겠지만 문제에서 요구하는것은 fread를 사용하는 것이다. fread를 사용할때는 개행문자('\n')까지만 읽는것이 아니라서 해당 문자열일때 break를 걸어주는 방식으로 문제를 풀었다.

파일을 복사하는 프로그램이다. 파일이름을 가져올때는 fgets를 사용해서는 안된다. 개행문자('\n')까지 파일명으로 인식하기 때문이다.

파일데이터를 복사할 때는 바이너리모드로 여는것이 좋을 듯 하다. 텍스트 모드로 파일을 열면 '\n'가 '\r\n'으로 변경되기 때문이다.

fgetc는 한글자씩 읽기 때문에 해당 프로그램의 성능은 좋지 않다.

fread와 fwrite를 통해 데이터를 복사하는 프로그램이다. feof함수는 파일의 끝을 알려주는 함수가아니라, 더이상 읽을 데이터가 없는데도 읽을려고 할때 feof는 0이아닌값을 반환한다. 즉 파일을 읽는 함수인 fread이후에 배치되어야한다.

include 즉 헤더파일을 선언한 위치에 그대로 들어가는 것을 알 수있다.

각 파일들에 같은 구조체로 각각 선언되어있다. 이러한 이유는 C파일을 object파일로 컴파일 할때 컴파일러는 각 파일단위로 각각 컴파일을 진행하기 때문이다. 한 파일에 선언된 구조체를 다른파일에서 사용할 수 없다.  각 파일들을 오브젝트 파일로 컴파일하고 이러한 오브젝트 파일들은 링커에 의해 연결된다.

각 오브젝트 파일을 하나로 묶어서 실행파일을 생성하는 것은 링커가 진행하는데 이때 링커는 main함수를 찾아 실행파일을 만들 방법을 찾는다. main함수 없이는 실행 파일을 만들 수 없다. main함수가 프로그램의 시작위치를 알려준다.

main함수를 찾고나서 각각 전역변수의 접근과 함수의 호출 관계를 파악한다. 이러한 과정을 통해 링커는 여러 오브젝트 파일을 묶어 실행파일을 생성해 낸다.

링커가 하는 일은 하나이상의 오브젝트 파일을 묶어서 하나의 실행파일을 만드는 일을 한다.

각 헤더파일에 ifndef 을 사용한것은 중복 정의를 피하기 위해 정의한 것이다. ifndef은 if not define 의 약자로 point.h의 경우 __POINT_H__가 정의되어있지 않으면 __POINT_H__를 정의하고 해당 구조체를 정의하는 것이다. 이후에 개발자의 실수로 point.h를 두번 선언하게 되더라도 중복을 피할 수 있도록 정의한 것이다.

pointOperation.h에도 point.h가 선언되어있다. main.c에는 pointOperation.h와 point.h가 각각 선언되어있어 결과적으로 point.h가 두번 선언되어있는데 ifndef을 통해 중복을 막을 수 있다. 그리고 point.h의 구조체의 선언같은 경우 중복되면 컴파일 에러가 발생할 수 있어 ifndef의 중요성을 인식할 수 있다. 개발시 실수를 방지하기 위해 해더파일에 ifndef을 꼭 추가해주는 것이 좋을 듯 하다.

하나의 헤더파일에 여러 함수들을 선언하고 4개의 함수들을 2개의 파일에 걸쳐 정의하였다.

main함수에서는 myString.h만 include해주면 컴파일 에러가 발생하지않으니 간편하것 같다.

구조체의 필요성을 알게해주는 문제

제목순으로 구조체 정렬

제목순, 출판사순, 가격순 선택 정렬 및 출력하는 문제

문자열을 복사할때는 strcpy를 사용하면 되지만 문자열의 주소를 옮길때는 그냥 대입하면 된다. 

temp는 문자열이 들어가있는것이아니라 char형 포인터 변수이기떄문에 strcpy를 이용하면 문제가 발생한다. 

문자열 주소가아닌 문자열 내용을 옮기고 싶다면 반복문을 통해 인자값들을 하나씩 옮기는 식으로 해야할것 같다.