알고리즘 자료구조 - 2

2장
 - 배열과 구조체에 대해 설명
 - 언급되는 알고리즘은 다음과 같다
    배열 데이터의 최댓값 구하기, 배열 데이터 역순 정렬, 기수 변환(진수 변환), 소수의 나열

1)
자료구조
 - 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
 - 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법

2)
상수식(constant expression) : 상수만을 포함하는 식, 실행시점(run time)이 아닌 컴파일 시점에 계산된다.

3)
배열 선언시 요소(index) 개수는 상수로만 정의할 수 있다.
따라서 배열의 크기는 동적으로 할당할 수 없다.
이를 위해 포인터와 동적할당 함수를 사용해서 동적객체를 생성하는 것으로 대체한다.
** 동적할당함수: malloc, calloc, realloc, free

4)
선언(declaration)은 컴파일러에게 참조할 식별자와 이름을 알려준다. 즉 메모리에 실제공간을 할당하지 않는다
 - ex) extern int a;, int func();, struct b;, typedef int a;, #define func(a, b) a+b;
     -> extern int a;는 외부의 전역변수를 사용하겠다라는 의미이기 때문에 메모리공간이 할당되지 않는다.

정의(definition)는 컴파일러가 대상을 생성한다. 즉 메모리에 실제공간을 할당한다.
 - ex) int a; 함수내용정의, 구조체 내용정의
     -> int a;의 경우 초기값 선언을 하지 않더라도 메모리에 실제공간을 할당한다. 지역변수나 전역변수나 마찬가지이다.
        (지역변수는 함수 시작시, 전역변수를 프로그램 시작시 생성된다)

** 메모리 구조
데이터(data) 영역
 - 전역변수와 정적(static) 변수가 할당되는 영역
 - 프로그램 시작시 할당, 프로그램 종료시 해제

힙(heap)
 - 동적 메모리이며, 동적객체가 할당되는 영역
 - 프로그램이 실행 중일 때 힙영역의 크기가 결정된다.

스택(stack) 영역
 - 지역변수와 매개변수가 저장되는 영역
 - 함수 호출시 생성, 함수 완료시 해제
 - 컴파일할 때 컴파일러에 의해 크기가 결정된다.

 -> 데이터와 스택영역은 컴파일러가 미리 공간을 계산하여 할당이 가능하지만, 동적변수는 어느시점에 얼마만큼의 공간을 할장할지 계산할수가 없어 프로그램 실행 중(run time)에 결정된다.

5)
포인터: 객체(변수) 또는 함수를 가리키는 변수
void 포인터 : 자료형이 정해지지 않은 포인터

공백포인터: null pointer, 아무것도 가리키지 않는 포인터
NULL: 공백포인터 상수(null pointer constant), 값 0을 값는 모든 정수, 상수 또는 상수식을 의미

** NULL은 stddef.h에 정의되어있으나, 일반적으로 NULL이 사용되는 함수를 사용하기 위해 정의하는 헤더파일(ex: stdio.h, stdlib.h, locale.h)에서 자동으로 stddef.h을 선언하여 stddef.h를 따로 선언하지 않아도 된다.

6)
함수에서 배열을 매개변수로 넘겨받을 때 주소를 넘겨받는다. 즉, 포인터로 넘겨 받는다. 이를 가독성을 위해 int *a가 아닌 int a[]와 같이 선언하여 사용할 수 있다.

7)
난수 생성 방법
 - rand 함수, srand함수, time함수가 선언되어 있는 time.h, stdlib.h 선언
 - 난수의 seed 초기화를 위한 srand 함수 호출(보통 srand(time(NULL))로 선언), time(NULL)은 현재시간(time_t형)을 반환
 - rand함수를 호출하여 난수 생성


** 의사난수
의사난수: 난수처럼 보이지만 일정한 규칙에 따라 생성되는 수

rand 함수가 생성하는 난수는 실제로는 의사난수이다.
따라서 seed를 주기적으로 time 함수를 사용하여 초기화하지 않는 이상 난수가 생성되지 않는다고 볼 수 있다.


8)
** 기수와 서수
기수: 수를 나타내는 데 기초가 되는 수, ex: 1,2,3
 ex) 10진수: 10을 기수로 하는 수
서수: 사물의 순서를 나타내는 수, ex: 첫번째, 두번째, 세번째

** 진수 표기
0b숫자 : 2진수(일부 시스템에서 사용)
0숫자 : 8진수
0x숫자 : 16진수

9)
** 전위형 증가연산자와 후위형 증가연산자
전위형 증가연산자: ++x;
후위형 증가연산자: x++;

10)
소수: 1과 자신을 제외한 어떤 정수로도 나누어지지 않는 수
소수를 구하는 알고리즘
기본
 - 2부터 주어진 수 x까지 순차적으로 증가하며 x가 나누어 떨어지는지 확인
개선1
 - 소수를 저장하는 배열 선언
 - 주어진 수 x를 배열에 저장된 데이터(소수)로 나누어 나누어지지 않으면 배열에 저장
개선2
 - 소수가 아닌 수는 a*b의 꼴로 구성되며, a와 b의 최대 수는 주어진 수 x의 제곱근이다(그 이상의 값을 가질 경우 a와 b의 크기가 역전될 뿐이다)
 - 따라서 주어진 수x가 1에서부터 제곱근 이하의 수로 나누어 떨어지는지 확인
 - 이때, 제곱근을 구하기 보다는 제곱(i*i)이 주어진 수 x보다 작은지를 확인하고, 해당 조건에 만족할 경우, i가 x로 나누어 떨어지는 지 확인(나누어 떨어지면 소수가 아님)
 - 단, 주어진 수x가 짝수일 경우는 제외한다.
   ** 짝수는 2의 배수이기 때문에(무조건 2로 나누어지기 때문에) 홀수만 확인한다

11)
한해의 지난 날 수를 계산하는 프로그램: 오늘이 올해로부터 며칠 지났는가
다차원 배열(multidimensional array)
다차원 배열의 초기화
 - 아래는 다 같은 초기화 방법
    : int aa[2][3] = {{1,2,3},{4,5,6}};
    : int aa[][3] = {{1,2,3},{4,5,6}};
    : int aa[2][3] = {1,2,3,4,5,6};
 - 아래는 다 같은 초기화 방법
    : int aa[2][3] = {{1,2},{4}};
    : int aa[2][3] = {{1,2,0},{4,0,0}};



12)
구조체: 임의의 자료형을 가지는 요소를 조합하여 만든 자료구조
구조체 선언:
 struct aa{
   int a;
   short b;
   char c;
 };

구조체 정의:
 struct aa z;

구조체 포인터:
 struct aa *y = &z;

구성요소
 - aa : 구조체 태그
 - a, b, c : 구조체 맴버
 - z : struct aa형 객체(구조체 객체)
 - y : 구초제 포인터

구조체 맴버 접근
 z.a
 y->a

구조체 재정의
 typedef struct aa A;
 ** 구조체 정의: A z; , 구조체 포인터: A *y = &z;