즐기는것 그리고 생각하는것

C언어 할때 배열은 했지만 중요하니까 한번더!

배열은 연속된 메모리 공간을 차지하는 같은 데이터형들의 집합

정적인 데이터이기때문에 컴파일러는 이 정해진 크기만큼 공간만을 확보한다

배열의 선언방법은

데이터형 배열명[배열의 크기];

예를들어보자

int array[10];

integer형으로 array라는 배열을 10의 크기로 정의 하였다

이것은 두가지 의미인데 첫번째는 array라는 배열명은 10개의 정수가 저장된 공간의 선두번지를

둘째로는 sizeof(array)와 같이 하면 배열의 크기 즉 int형이 몇개나 저장될 수 있는가에 10이라는 값을 나타낼 뿐이다.

그 이외의 배열에 대한 조작은 모두 포인터의 조작으로 대치된다.

중요한점은 배열의 제일 첫 요소는 array[1]이 아니라 array[0]이며 마지막 요소는 array[10]이 아니라 array[9]이다 위에서의 10은 정말로 배열의 크기일 뿐이다.

컴파일러는 위의 정의에 의해서 int형 데이터가 10개로 저장될 공간을 정적 데이터 영역에 확보해두고 실제로 확보되는 배열의 크기는 int형 크기에 2에 10을 곱한 값, 즉 20바이트가 된다.

중요한것은 배열은 포인터에 대한 처리로 대치되기 때문에 array는 배열에 확보된 메모리 공간의 선두번지를 의미한다 그래서 array[4]는 *(array+4)와 완전히 동일하다 배열의 이름 즉 메모리 공간의 선두번지는 포인터와 동일하게 취급해도 되지만 배열의 이름은 포인터가 아니라는 것이다.포인터는 주소를 가리키는 변수이고 배열이름은 그자체를 가리키는 상수이다. 그래서 배열의 이름에 따로 공간을 할당하지는 않는다. 그래서 array를 포인터로 취급해서 그 값을 변경하려 하면 에러가 발생한다.

1차원 배열(one dimensional array)

배열에서 차수는 배열 요소를 지정하는데 몇개의 첨자가 배열의 크기를 지정하는것이 있는가에 의해서 지정되는데 1차원배열은 하나만 있으면 된다.

배열은 실행 후에 그값을 결정할 수있지만 정의하면서 초기값을 부여할 수 있다.

예를들어

int array[10] = {1,2,3,4,5,6,7,8,9,0}; 

;을 빼먹지 말자

이와같은 배열은 다음과 같이 메모리에 배치된다.

                    array가 가르키는곳

1차원 배열은 위와 같아서 포인터의 연산이 제대로 먹히는 것이다.

다차원 배열(Multi dimensional array)

다차원 배열은 배열을 선언할때 원하는 차원만큼 첨자?를 지정하면 된다 보통 2차원을 많이 쓰고 3차원은 어쩌다가 가끔? 그이상은 잘 쓰지 않는다고 한다. 하지만 다차원 배열이라고 해도 그 근본은 2차원 배열과 같기 때문에 2차원 배열만 설명하겠다

2차원 배열 arra2를 선언하고 초기화를 해보자

int arra2[3][3] = 

{{1,2,3},

 {4,5,6},

 {7,8,9}};

2차원 배열의 초기화에는 여러가지 방법이 있지만 위의 방법이 가장 좋다.

배열요소를 지정할때 위의 수를 행렬이라고 생각하면 된다(고등학교때 수학을 열심히 해야하는 이유!)

         0열  1열  2열

0행     1,     2,    3  

1행     4,     5,    6 

2행     7,     8,    9  

그래서 int array2[2][1]은 2행의 1열이니 8이다

          int array2[0][1]은? 2다

array2는 2차원 배열이지만 메모리의 구조가 선형적 구조라서 메모리저장될때는 1차원 배열처럼 저장된다.

               array2가 가리키는곳(array2는 정수 3개의 배열을 가리키는 포인터라고 생각 하면 된다)

                                        array2+1                                      array2+2

배열은 포인터로 설명이 가능하지만 2차원 배열인 경우 약간 복잡하다. 1차원 배열에서는 배열명이 배열공간의 선두를 가리키는 주소라고 했다. 그래서 array는 int형을 가리키는 주소로 생각하면 되었다.

하지만 array2는 3개의 int형의 공간을 가리키는 조소이다 마찬가지로 array2+1은 array2다음의 3개의 int형의 공간을 가리킨다.

C의 문법은 재귀적이라는 것을 생각하면 2차원 배열이 이런 복잡한 구조를 갖는다는 것이 이해가 갈것이다

1차원 배열을 함수의 인자로 넘기는 방법

1차원 배열을 함수의 인자로 넘기는 방법은 간단하다. 포인터로 표현하는 방법과 배열로 표현하는 방법이 있지만 이 둘은 같다.

다음은 배열을 진자로 받아서 배열요소들의 평균을 구하는 프로그램이다.

int average(int a[],int n)

{

    int sum =0;

    int i;

    for (i=0;i<n;i++) {

        sum+=a[i];

    }

    return (sum/n);

}

C에서 배열의 크기는 메모리 공간을 할당할 때만 필요하지 실행시에는 배열의 크기에 대해서 컴파일러가 신경쓰지 않는다 그래서 함수가 배열을 인지로 받을 때 그 배열이 몇개의 요소를 가지는지는 전혀 알 방법이 없다. 이런이유로 average()함수는 n이라는 배열의 크기를 인자로 따로 받는다. 그리고 인자로 받는 배열a에도 []로 배열표시만 했지 크기를 명시하지 않았다(해도 컴파일러가 무시한다)

물론 배열자체에 끝을 나타냄이 있으면 배열의 크기를 넘길 필요가 없다. 가장 전형적인 예가 C에서 문자열을 다루는 방식이다. C에서 문자열은 char형의 배열로 구현하는데 특별히 문자열의 크기에 신경을 쓰지 않음을 알고 있을 것이다. 배열을 읽어가다가 0이 읽어지면 배열의 끝임을 알게 되는 것이다. 이렇게 배열의 한계는 두가지가 있지만 선택은 본인 몫이다.

배열은 포인터와 동일한 표현이라고 했으므로 위의 average함수도 포인터의 표현으로 나타낼수 있을 것이다. 다음과 같이 함수의 헤더를 바꾸어도 상관없다.

int average(int *a,int n)

다음 코드는 1차원 배열을 함수의 인자로 넘기는 방법을 보여준다.

#include <stdio.h>

#define MAX 10

int average(int a[],int n)

{

    int sum =0;

    int i;

    for (i=0;i<n;i++) {

        sum+=a[i];

    }

    return (sum/n);

}

int main(int argc, const char * argv[]) {

    int array[MAX];

    int i;

    printf("\nInput %d integer -> ",MAX);

    for (i=0; i<MAX; i++) {

        scanf("%d",array+i);

    }

    printf("\nAverage of %d integer is %d",MAX,average(array, MAX));

    return 0;

}

2차원 배열을 함수의 인자로 넘기는 방법

2차원 배열을 함수 인자로 넘기는것은 주의해야 한다. C는 프로그램이 실행한 뒤에는 배열의 크기를 모른다고 하였기 때문에 1차원 배열에서는 함수의 인자로 배열을 넘길때 배열의 크기를 명시하지 않고 따로 배열의 크기르 정수로 넘겨주었다.

하지만 2차원 배열은 뭔가 그 원칙에 어긋나는 것 같다

2차원 배열을 사용하는 가장 빈번한 예는 행렬(Matrix)이다. 다음 input_matrix() 함수는 2x2 행렬을 키보드로 입력받는 함수이다

void input_matrix(int m[][2],int n)

{

    int i,j;

    printf("\n input %d by %d Matrix in row order ->",n,n);

    for (i=0;i<n; i++) {

        for (j=0; j<n; j++) {

            scanf("%d",&m[i][j]);

        }

    }

}

배열의 크기를 모른다고 했는데 위의 input_matrix 함수는 인자에 int m[][2]라고 쓰여있어 2라는 크기가 들어갔음을 알수있다.

m을 포인터라고 보았을때 int m[][2]의 표현은 m이 두개의 int형의 공간을 가리키는 포인터이다. 즉 int m[][2]의 표현은 배열의 크기를 나타낸것이 아니라 m이 어떤 형의 데이터르 가리키는 포인터 인지 나타내는 것이다. 즉 m이 두개의 int혀이 공간을 가리킨다는 것은 알려졌지만 두개의 int형의 공간이 몇개나 있는지는 모른다. 결국 배열의 크기는 모른다는 것이다.

input_matrix 함수는 포인터 표현으로 나타낼수 있다 아래처럼 바꾸어도 지장이 없다

void input_matrix(int *(m[2]),int n) 

포인터로 표현하니 의미가 더 명확하게 보인다. 2개의 int형 공간을 가리키는 포인터 m의 정체가 이제 확연하게 드러난다.

2차원 배열을 1차원 배열인것 처럼 사용할수도 있지만 그럴 필요까진 없을것 같다 굳이 하자면 할수 있지만...굳이 써보자면

void input_matrix(int *m,int n)

{

    int i,j;

    printf("\n input %d by %d Matrix in row order ->",n,n);

    for (i=0;i<n; i++) {

        for (j=0; j<n; j++) {

            scanf("%d",m+i*n*j);

        }

    }

}

함수 호출은 다음과 같다.

void main()

{

int mat[2][2];

input_matrix(&mat[0][0],2);

...

}

조금은 기형적입니다. 왠만하면 보이는 대로 2차원 배열을 다룹시다!

연습으로 2x2의 정방행렬을 두개 입력받아서 곱을 출력하는 프로그램을 작성해 보자.

두행렬 A,B의 곱 C에 대입하는 알고리즘을 풀어 써보자

1.for(i는 0부터 N-1까지 1씩 증가) --> i는 C의 행

2.for(j는 0부터 N-1까지 1씩 증가) --> j는 C의 열

3.C[i][j]를 0으로 초기화 -->누적을 위해서 초기화

4.for(k는 0부터 N-1까지 1씩 증가)

5.C[i][j]에 A[i][k]*B[k][j]를 더함

이 알고리즘을 코드로 구현해 보면

#include <stdio.h>

#define MAX 2

void input_matrix(int m[][MAX],int n) //배열을 키보드로 입력받음

{

    int i,j;

    printf("\n input %d by %d Matrix in row order ->",n,n);

    for (i=0;i<n; i++) {

        for (j=0; j<n; j++) {

            scanf("%d",&m[i][j]);

        }

    }

}

void print_matrix(int m[][MAX],int n)

{

    int i,j;

    printf("\n");

    for (i=0; i<n; i++) {

        for (j=0; j<n; j++) {

            printf("%-6d",m[i][j]);

        }

        printf("\n");

    }

}

void multiply_matrix(int m1[][MAX],int m2[][MAX],int m3[][MAX],int n)

{

    int i,j,k;

    for (i=0; i<n; i++) {

        for (j=0; j<n; j++) {

            m3[i][j] = 0;

            for (k=0; k<n; k++) {

                m3[i][j] += m1[i][j] * m2[k][j];

            }

        }

    }

}

int main(void)

{

    int mat1[MAX][MAX];

    int mat2[MAX][MAX];

    int mat3[MAX][MAX];

    input_matrix(mat1, MAX);

    input_matrix(mat2, MAX);

    multiply_matrix(mat1, mat2, mat3, MAX);

    printf("\n Answer : ");

    print_matrix(mat3, MAX);

}

이렇게 나타낼수 있다.

다차원 배열을 함수의 인자로 넘기는 방법

이 방법은 2차원 배열을 함수의 인자로 넘기는 방법의 연장선상에 있다. 즉 다차원 배열을 함수의 인자로 넘길 떄에는 2차원 배열과 마찬가지로 가장 큰 블록을 가리키는 최자측 첨자를 비워두고 나머지 첨자는 그 크기를 명시하는 것이다

예를들어 3*4*2 크기를 가지는 int형의 tri 배열을 예로 들어 보겠다.

int tri[3][4][2];

int func(int t[][4][2])

{    ...    

}

위와 같다.

그 이상도 마찬가지다

프로그램을 작성할때에도 구조적인 작성이 필요하다

예를들어 전체적으로 지도를 그리듯이 윤곽을 잡고 기능을 분류,모듈로 작성한다음 다시 각 모듈을 세분화 하여 함수들을 작성하는 방법을 (Top -down Programming)이라고 하며 구조화 하는 프로그래밍의 중요한 기법이다

자료에 눈을 돌려 보아도 그냥 개념없이 흐트러져 있거나 외부조작에 대해 너무 개방적이면 이는 구조적이라고 할수 없다.

서로 연관있는 자료끼리 연견되어있으며 자료에 접근하는 방법을 제한하는 등의 짜여진 자료구조는 프로그램을 작성하는 데 아주 중요하다.

자료구조와 알고리즘은 아주 밀접하다. 자료구조가 복잡하면 알고리즘은 간단해지고 그 역이 성립한다 자료구조와 알고리즘의 복잡함을 타협하는 지혜가 필요하다.

그래서 배열,리스트,스택,큐,트리 로 하나씩 알아보겠다

앞에서 입력자료의수 N에 대해서 그 실행시간 함수 T(N)은 일정한 유형이 있음을 알아보았는데요 실제로는 이유형에 상수가 곱해지고 더해집니다.

실행시간에 대해서 오해하기 쉬운점은 나쁜유형의 알고리즘이라도 효율석있게 만들면 좋지 않을까? 인데 물론 잘만 프로그래밍한다면 바꿀수는 있지만 알고리즘 자체를 변경하는것은 불가능 합니다. 효율적인 프로그래밍은 유형에 곱하거나 더해지는것을 작게 하는것분 획기적인 시간단축을 위해서는 알고리즘 자체를 개선해야 합니다.

하나의 알고리즘을 여러사람이 프로그래밍 한다면 실행 결과의 함수는 모두 다를 뿐더러 이 알고리즘은 추상적인 방법인데 비해 프로그래밍은 정말 많은 변수가 있기때문에 서로다른 실행시간을 가져옵니다. 그래서 경험적으로 알고리즘 성능을 판단하는것은 옳지 못하기 때문에 이런 알고리즘 성능을 객관적으로 표현하는 기준이 바로 O표기법 입니다.

O 표기법의 정의는

만약 실행 시간 함수T(N)이 N0보다 큰 N에 대하셔 항상 C0F(N)보다 작거나 같은 C0와 N0가 존재한다면 T(N)은 O(F(N))이라고 합니다.

즉 N>=N0인 모든 N에 대하여 T(N)<=C0F(N)이 만족하면 T(N)=O(F(N))입니다.

실제 실행함수 T(N)이 같는 상수는 프로그래머의 능력에 따라 달라질수 있는 것이기 때문에 순수한 알고리즘 성능표시를 위해 상수요소를 없어야 하는데 이 상수 요소를 없앤 입력 자료수 N에 따른 실행시간만 나타낸것이 바로 O 표기법입니다 

이 O표기법은 정의상 알고리즘 실생시간의 상한을 나타냅니다. 실행시간의 상한은 최악의 경우 에 해당한다는것도 알아둡시다. 즉 O표기법은 최악의 경우에 대한 입력 자료수 N에 대한 실행시간 함수 관계입니다.

예시로

T(N) = 3*N*N+1

T(N)은 4*N*N보다는 N이 1보다 큰 경우에 항상 작으므로 상수 4를 떼버리고 O(N^2)이 라고 말할 수 있습니다. 또한 4*N*N*N도 O(N^3)라고 말할수 있고 더 큰수도 가능하지만 이렇게 큰함수만 잡는것은 알고리즘 성능을 표헌하는데 큰 의미가 없습니다.

일반적으로 T(N)이 N의 다항식으로 나타날 떄는 최고차항만 의미가 있습니다. 그래서 T(N)이 최고차가 m이라면 O(N^m)이라고 말할수 있습니다.

하지만 O표기법을 과신하는것도 문제 가 있습니다

첫번째로 O표기법은 실행시간의 상한을 제공하기 때문에 실제로는 실행시간이 작을수도 있습니다

두번쨰로 알고리즘이 실행시간이 상한을 하는것은 실제 운용상 거의 나타나지 않습니다.

세번째로는 미정의 상수 C0는 충분히 작아야 합니다.

네번째로는 미정의 상수 N0역시 충분히 작아야 한다는 점 입니다

예를 들어 가장 빠른 정렬 알고리즘이라고 알려져 있는 퀵정렬의 경우 그 실행시간은 O(N^2)입니다 O표기법은 최악의 경우 실행시간의 상한을 나타내기 때문에 실제의 일반적인 경우 실행시간은 훨씬 적습니다. 퀵 정렬은 일반적으로 NlogN의 실행시간을 가져 매우 빠른 속도를 가집니다.

결론은 O표기법은 최악의 경우라도 넘지않는 실행시간의 함수이기 떄문에 일반자료에 대한 실행시간 보다는 훨씬 큰 값을 가진다. 일반적인 경우에는 매우 뛰어난 속도를 가지지만 최악의 경우에만 극도로 성능의 좋지 않는 알고리즘의 경우 O표기법은 과장되게 성능이 나쁜것으로 판단합니다.

--후일 추가 내용 다른 표기법과 시간적 공간적 소요량

읽어보기 전에...:컴퓨터는 엄청 큰 계산기 랍니다. 그말은 수학을 조금은 알아야 한다는것이지요 하하하

읽어보시기 전에 로그,제곱,등은 알아두고 읽어보시는것이 이해가 더 잘될것 같습니다

1.

입력 자료수에 관계없이 일정한 시간을 갖는 알고리즘이다. 프로그램에서 대부분의 명령으로 한번이나 몇번만 실행된다. 전체적 프로그램이 이런경우라면 실행시간은 상수(1처럼)가 된다. 알고리즘을 설계하거나 테스트시 도전해볼만 하다.

log N.

입력자료 N에 따라라 실행시간이 Log N을 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 커다란 문제를 해결할때 조금씩 잘게 쪼갤때 나타나는 알고리즘이다.로그 가 그렇듯이 base에 따라 결과가 달라지지만 그렇게 크게 다르지는 않다. 예를들어 N이 1000일때 밑이 10이라면 결과는 3이 나오지만 밑이 2라면 약 10이다 이차이는 매우 미미하다. 이 유형의 알고리즘은 매우 바람직한 실행시간을 가지는데 성능의 좋은 알고리즘은 대부분 Log N의 수행시간을 가진다.

N log N.

커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 알고리즘이다 N이 두배가 많아지면 실행시간은 두배보다 조금 더 많이 늘어난다.

N^2.

이 유형은 이중 루프 내에서 입력자료를 처리하는 경우에 나타난다. N값이 큰값이 되면 실행시간은 감당하지 못할정도 커진다 그러므로 많은 양의 입력자료에 대해서는 사용이 부적절 하다. N이 두배로 늘어나면 실행시간은 4배로 늘어난다.

N^3.

이 유형은 앞의 유형과 비슷하게 입력자료를 삼중 루프내에서 처리하는 경우에 나타난다 N값이 커짐에 따라 실행시간은 훨씬더 커지게 된다. 앞의 유형과 마찬가지로 많은 입력자료에 대해서는 부적절하며 문제가 있는 알고리즘이다 N이 두배가 늘어나면 실행시간은 8배로 늘어난다.

2^N

입력자료가 늘어남에 따라 급격하게 실행시간이 늘어난다. 흔하지는 않지만 알고리즘을 개발할떄 보인다. 하지만 개발되고 난후로 더좋은 알고리즘으로 개선된다. N이 두배로 늘어나면 실행시간은 제곱이 된다.

실행시간이 오래걸리는것 순서대로 알고리즘을 적어 보았는데요 가장 효율적인 유형은 logN과 NlogN 인것같습니다!

알고리즘 아랍의 수학자인 알-콰리즈미(الخوارزمي)의 이름에서 유래했다고 알려졌다 

문제를 해결하기 위한 절차나 방법 

어떠한 생동을 하기 위해서 만들어진 명령이 집합

컴퓨터는 거대한 계산기이다 논리와 알고리즘이 무엇보다 중요하다

나는 프로그래밍은 자료의 생성과 변화라고 생각한다 알고리즘과 자료구조는 이런 자료를 사자용자가 효율적으로 원하는 방향으로 생성되고 변화하는 절차와 방법이라고 생각한다

2007년 아이폰이 등장하고 it분야는 점점 거대해졌다 이제는 사물에도 인터넷이 들어가는 iot에 인터넷만 있으면 다되는 웹까지 컴퓨터로 할수있는것이 무궁무진 한 만큼 언어나 방식도 너무나 많아졌다 하지만 그래도 변치 않는게 바로 알고리즘 자료구조이다 그래서 회사에서 기술면접을 볼때 언어는 그려려니해도 자료구조와 알고리즘 중심으로 본다

이제 중요한것을 알았으니 그것을 해야할때 하루하루 내가 고민하고 생각한것을 이곳에 기록하려한다(뭐 어때 내 개인 블로그인데)

참고도서는

훓어보니 시작은 

좋은 프로그램을 만드는 핵심원리 25가지로 개괄적으로 감을 잡고

C로 배우는 알고리즘 1,2권을 한후

gof 디자인 패턴까지 하고 난후

STL에 들어가면서 완성시켜야 겠다

C/C++를 주로하되 언어따위에 구속받지 않겠다!

2014/10/29 추가

알고리즘으로 정한 책 3권을 주제별로 분류하는 작업

1.집합

2.관계

3.함수

4.진법

5.소수

6.수열

7.순열과 조합

8.행렬

9.급수

10.기초통계

11.컴퓨터에서의 정수와 실수

12..난수

13.오류 검출과 정정

14.컴퓨터논리

15.배열

1권 3장 3.2배열

16.재귀호출

1권 4장 재귀 호출

17.정렬

1권 5장 정렬 알고리즘

18.탐색

1권 6장 검색

19.스택과 큐

1권 3장 7,8,9

20.연결리스트

1권 3장 4,5

21.트리

1권 3장 9,10    

22.그래프

2권 7장

23.해싱

24.인공지능 탐색

25.암호화 알고리즘

** 데니스 리치의  The C Programming Language 에서 quick sort ,stack 정도는 다르더군요 그래서 뭐 굳이 여기 순서를 지키지 않고 퀵정렬이랑 스택은 먼저 하겠습니다

**11월 11일 다시생각! 세화 출판사 님의 책 C로 배우는 알고리즘이 심화 되었기 때문에 이책으로 일단 한뒤 빠진부분은 좋은 프로그램을 만드는 핵심원리 25가지로 보충하는 것으로 하겠습니다 그뒤 gof 디자인 패턴 이런식으루... 아마 주중에는 cocos2d-x 주말은 자료구조/알고리즘 하는식으로 하겠습니다