| sitelink1 | |
|---|---|
| sitelink2 | |
| sitelink3 | |
| sitelink4 | |
| sitelink5 | |
| extra_vars6 |
http://blog.naver.com/simtwolove?Redirect=Log&logNo=30022013436
자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part1 동적배열
--------------------------------------
먼저 동적배열이란 무엇일까?
움직이는 배열. 움직이도록 설계된 배열이다.
배열은 C언어가 제공하는 가장 기본적인 자료 구조이며 워낙 단순하기 때문에 누구나 쉽게 익숙해질 수 있다.
맞다. 배열은 이미 이 단계에 오기전에 충분히 사용법을 익혔고, 비교적 매우쉬운 수준이기 때문에
구현이 쉽다는 장점이 있다.
또 장점으론, 배열이란 구조가 워낙 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없어 공간 효율이 좋다.
무슨소린가 하면, 정수형 변수 100개를 저장할 수 있는 int a[100] 배열은 정확하게 정수 100개분만큼의 메모리만을 할당하며 요구한다.
이는 메모리 효율에 매우 우수하다.
또 장점이 있는데, 배열 크기가 아무리 커지더라도 검색 속도가 일정하다 라는 것이다.
배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자 *요소크기를 더하는 간단한 동작이므로 임의의 한 요소를 참조하는 시간이 상수이다.
즉, int ar[10]에서 ar[9]를 참조하는 시간과 int ar[1000]에서 ar[999]를 참조하는 시간이 똑같다는 얘기이다.
이처럼 배열은 메모리 요구량이나 속도면에서 모두 만족할만한 성능을 보이는데 요약하자면 작고 빠른 자료구조이다.
게다가 쓰기도 쉬워 다양한 용도에 아주 요긴하게 사용된다.
그럼 단점은 무엇인가?
배열의 요소가 연속된 메모리 공간에 배치되어 있으므로, 배열 중간의 요소를 삭제하거나, 중간에 새로운 요소를 삽입할 수 없다는 점이다.
하지만 이것은 일종의 고정관념이고, 얼마든지 중간에 요소를 삭제/삽입을 충분히 구현 할 수 있다.
그러나 새로운 요소가 삽입된다 하더라도 배열의 크기가 자동으로 늘어나는 것은 아니므로 미리 선언한 크기 이상의 요소를 추가할 수는 없다.
이를 해결하기 위해 배열의 크기를 무작정 늘리려는 초급 프로그래머가 있겠지만, C언어는 중급 언어라는 특성상 배열의 범위를 전혀 점검하지 않기 때문에 배열을 넉넉한 크기로 선언하는 것만으로는 충분하지 않다.
근본적인 문제는 배열이 작은 것이 아니라 필요한 크기를 미리 예측할 수 없다는 데 있으므로 신축성 있는 관리가 필요하다.
크기가 가변적인 정보는 이론적으로 무한대까지 늘어날 수 있어야 하며 이런 정보들을 관리하기 위해서는 배열도 정보의 양에 따라 실행중에 확장 가능해야 한다.
물론 컴퓨터의 메모리가 유한하기 때문에 실질적인 무한 배열은 불가능하지만 메모리가 허락하는 한까지(=실질적인 무한대)는 정보를 저장할 수 있어야 안전하다.
즉, 우리가 원하는 것.
실행중에 필요한만큼 크기를 늘렸다 줄였다 할 수 있는 배열을 동적 배열이라고 한다.
C언어 차원에서 동적 배열에 대한 지원은 전혀 없으므로 이런 배열은 직접 만들어 쓰는 수밖에 없다.
아래의 예를 보자.
//시작---------------------------이 줄은 소스에 포함되지 않습니다.
//끝---------------------------이 줄은 소스에 포함되지 않습니다.
실행결과-------------------------
최초 배열은 크기 10으로 초기화되었고 루프를 돌며 8개의 값을 저장했다.
이 상태에서 10, 11, 12를 차례로 삽입했는데 10, 11까지는 남은 두 요소에 저장하면 되지만 12가 삽입될 때는 초기 할당된 10개로 부족하므로 이 때 재할당되어 배열은 크기 16으로 늘어난다.
더 많은 요소를 삽입하면 배열은 자동으로 필요량을 판단하여 늘어날 것이다.
1.배열의 실체 -
이 예제에서 배열의 실체는 ar 포인터이다.
저장하고자 하는 타입의 포인터를 선언하고 이 포인터를 동적으로 할당하여 배열의 크기를 가변적인 크기를 다룰 수 있게 하였다.
2.배열 관리 변수 -
동적 배열은 컴파일할 때 그 크기가 미리 정해지지 않으며 실행중에 언제든지 크기를 변경할 수 있어야 한다.
할당 크기 저장 변수 - size
배열에 실제 저장된 요소 개수 저장 변수 - num
배열 관리 함수들은 배열에 요소를 삽입할 때 이 두 변수값을 비교해 보고 재할당할 시점을 파악할 것이다.
3.배열 초기화 -
배열의 실체인 ar이 포인터 변수이므로 ar에 메모리가 할당되기 전까지 배열은 실제로 존재하지 않는다.
main에서 InitArray(10,5) 로 호출했으므로 배열의 초기 할당치는 10이 되고 여유분은 5로 설정된다.
ar포인터가 메모리의 선두를 가리키게 되고, main에서 1~8까지의 정수를 추가했으므로
ar배열은 다음과 같다
----------------------------------
ar
↓ size = 10, num = 8
[1][2][3][4][5][6][7][8][?][?]
----------------------------------
총 10개의 요소를 기억할 수 있으며 8개를 저장했으므로 아직 두 개의 여유가 남아 있는 상황이다.
물론 이 남은 칸에는 쓰레기값이 들어 있을 것이다.
4.재할당 -
1~8까지 정수를 추가한 후 10, 11, 12를 요소 3의 위치에 순서대로 삽입하는데 10, 11까지 삽입되면 ar은 꽉 찬 상태가 된다.
이 상태에서 12를 더 삽입하려면 기억 공간이 부족하므로 배열의 크기를 늘려 재할당해야 한다.
배열의 크기가 늘어나는 경우는 Insert 함수에서 요소를 추가할 때 뿐이므로 이 함수의 선두에서만 배열 크기를 점검하면 된다.
┌ 여기에 12를 삽입하려고 한다. (need = 11, size = 10 이때 재할당 한다)
[1][2][3][11][10][4][5][6][7][8]
┌ 여기에 12를 삽입
[1][2][3][11][10][4][5][6][7][8][?][?][?][?][?][?]
└이만큼더늘린다┘
[1][2][3][12][11][10][4][5][6][7][8][?][?][?][?][?]
현재 크기가 부족하다는 판단이 내려졌으므로 새로운 크기를 계산하되 일단 need 이상 되어야 하고 여기에 약간의 여유분 growby를 더했다.
size는 16이 되며 이 크기대로 realloc 함수를 호출하여 ar 배열을 재할당한다.
만약 need가 size보다 더 작다면, 즉 아직 여유분이 남아 있다면 재할당없이 기존의 방법대로 삽입한다.
5. 여유분-
배열을 재할당할 때는 어느 정도의 여유분을 주는 것이 효율상 유리하다.
삽입은 보통 연속적으로 일어나므로 need만큼 필요해졌을 때 need만큼만 재할당하면 일단은 삽입 가능하지만 잠시 후 다시 재할당해야 할 확률이 상당히 높다.
realloc 함수는 편리하기는 하지만 번지가 바뀔 경우 굉장히 느리며 특히 배열의 크기가 클수록 속도상의 불이익이 심하기 때문에 가급적이면 호출 회수를 줄여야 한다.
그래서 이왕 재할당을 할 때 여유분을 주어 다음 번 부족한 상황을 최대한 늦추는 것이 좋다.
동적 배열은 이런 목적으로 growby라는 변수를 정의하고 재할당할 때 need에 이 값을 더한 크기로 배열을 늘린다.
여유분은 어디까지나 여유를 두기 위한 값이므로 이 값이 0이더라도 동적 배열은 제대로 동작하겠지만 성능이 떨어진다.
그렇다고 해서 여유분을 지나치게 크게 주면 남는 메모리가 많아져 공간 효율이 떨어진다.
필요에 따라 적당한 양을 주는 것이 좋으며 그래서 InitArray 함수를 호출할 때 개발자가 결정할 수 있도록 해 두었다.
예제에서는 재할당이 빨리 일어나도록 하기 위해 초기값, 여유분을 10, 5로 주었지만 실제 프로젝트에서는 배열의 삽입, 삭제 빈도에 따라 초기값과 여유분을 적당한 크기로 선택해야 한다.
100, 50 정도면 대체로 쓸만한 성능을 보일 것이며 자료의 양이 많고 삽입도 빈번하다면 1000, 500 정도로 충분한 값을 주어 성능의 향상을 꾀할 수 있다.
즉 InitArray의 인수들은 배열의 성능 파라미터인 것이다.
///////////////////////////////////////
WinAPI 의 강의를
초급 프로그래머가 더욱 이해하기 쉽게
편집, 추가, 삭제하여 작성한 글 입니다.
written by 호근
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part1 동적배열
--------------------------------------
먼저 동적배열이란 무엇일까?
움직이는 배열. 움직이도록 설계된 배열이다.
배열은 C언어가 제공하는 가장 기본적인 자료 구조이며 워낙 단순하기 때문에 누구나 쉽게 익숙해질 수 있다.
맞다. 배열은 이미 이 단계에 오기전에 충분히 사용법을 익혔고, 비교적 매우쉬운 수준이기 때문에
구현이 쉽다는 장점이 있다.
또 장점으론, 배열이란 구조가 워낙 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없어 공간 효율이 좋다.
무슨소린가 하면, 정수형 변수 100개를 저장할 수 있는 int a[100] 배열은 정확하게 정수 100개분만큼의 메모리만을 할당하며 요구한다.
이는 메모리 효율에 매우 우수하다.
또 장점이 있는데, 배열 크기가 아무리 커지더라도 검색 속도가 일정하다 라는 것이다.
배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자 *요소크기를 더하는 간단한 동작이므로 임의의 한 요소를 참조하는 시간이 상수이다.
즉, int ar[10]에서 ar[9]를 참조하는 시간과 int ar[1000]에서 ar[999]를 참조하는 시간이 똑같다는 얘기이다.
이처럼 배열은 메모리 요구량이나 속도면에서 모두 만족할만한 성능을 보이는데 요약하자면 작고 빠른 자료구조이다.
게다가 쓰기도 쉬워 다양한 용도에 아주 요긴하게 사용된다.
그럼 단점은 무엇인가?
배열의 요소가 연속된 메모리 공간에 배치되어 있으므로, 배열 중간의 요소를 삭제하거나, 중간에 새로운 요소를 삽입할 수 없다는 점이다.
하지만 이것은 일종의 고정관념이고, 얼마든지 중간에 요소를 삭제/삽입을 충분히 구현 할 수 있다.
그러나 새로운 요소가 삽입된다 하더라도 배열의 크기가 자동으로 늘어나는 것은 아니므로 미리 선언한 크기 이상의 요소를 추가할 수는 없다.
이를 해결하기 위해 배열의 크기를 무작정 늘리려는 초급 프로그래머가 있겠지만, C언어는 중급 언어라는 특성상 배열의 범위를 전혀 점검하지 않기 때문에 배열을 넉넉한 크기로 선언하는 것만으로는 충분하지 않다.
근본적인 문제는 배열이 작은 것이 아니라 필요한 크기를 미리 예측할 수 없다는 데 있으므로 신축성 있는 관리가 필요하다.
크기가 가변적인 정보는 이론적으로 무한대까지 늘어날 수 있어야 하며 이런 정보들을 관리하기 위해서는 배열도 정보의 양에 따라 실행중에 확장 가능해야 한다.
물론 컴퓨터의 메모리가 유한하기 때문에 실질적인 무한 배열은 불가능하지만 메모리가 허락하는 한까지(=실질적인 무한대)는 정보를 저장할 수 있어야 안전하다.
즉, 우리가 원하는 것.
실행중에 필요한만큼 크기를 늘렸다 줄였다 할 수 있는 배열을 동적 배열이라고 한다.
C언어 차원에서 동적 배열에 대한 지원은 전혀 없으므로 이런 배열은 직접 만들어 쓰는 수밖에 없다.
아래의 예를 보자.
//시작---------------------------이 줄은 소스에 포함되지 않습니다.
·미리보기 | 소스복사·
- #include <stdio.h>
- #include <stdlib.h>
- #define ELETYPE int
- ELETYPE *ar;
- unsigned size;
- unsigned num;
- unsigned growby;
- void InitArray(unsigned asize, unsigned agrowby)
- {
- size=asize;
- growby=agrowby;
- num=0;
- ar=(ELETYPE *)malloc(size*sizeof(ELETYPE));
- }
- void Insert(int idx, ELETYPE value)
- {
- unsigned need;
- need=num+1;
- if (need > size)
- {
- size=need+growby;
- ar=(ELETYPE *)realloc(ar,size*sizeof(ELETYPE));
- }
- memmove(ar+idx+1,ar+idx,(num-idx)*sizeof(ELETYPE));
- ar[idx]=value;
- num++;
- }
- void Delete(int idx)
- {
- memmove(ar+idx,ar+idx+1,(num-idx-1)*sizeof(ELETYPE));
- num--;
- }
- void Append(ELETYPE value)
- {
- Insert(num,value);
- }
- void UnInitArray()
- {
- free(ar);
- }
- void DumpArray(char *sMark)
- {
- unsigned i;
- printf("%16s => 크기=%02d,개수=%02d : ",sMark,size,num);
- for (i=0;i<num;i++)
- {
- printf("%2d ",ar[i]);
- }
- printf("n");
- }
- void main()
- {
- int i;
- InitArray(10,5);DumpArray("최초");
- for (i=1;i<=8;i++) Append(i);DumpArray("8개 추가");
- Insert(3,10);DumpArray("10 삽입");
- Insert(3,11);DumpArray("11 삽입");
- Insert(3,12);DumpArray("12 삽입");
- Delete(7);DumpArray("[7]인자 데이타 삭제");
- UnInitArray();
- }
//끝---------------------------이 줄은 소스에 포함되지 않습니다.
실행결과-------------------------
최초 => 크기=10,개수=00 :
8개 추가 => 크기=10,개수=08 : 1 2 3 4 5 6 7 8
10 삽입 => 크기=10,개수=09 : 1 2 3 10 4 5 6 7 8
11 삽입 => 크기=10,개수=10 : 1 2 3 11 10 4 5 6 7 8
12 삽입 => 크기=16,개수=11 : 1 2 3 12 11 10 4 5 6 7 8
[7]인자 데이타 삭제=> 크기=16,개수=10 : 1 2 3 12 11 10 4 6 7 8
실행결과-------------------------
최초 배열은 크기 10으로 초기화되었고 루프를 돌며 8개의 값을 저장했다.
이 상태에서 10, 11, 12를 차례로 삽입했는데 10, 11까지는 남은 두 요소에 저장하면 되지만 12가 삽입될 때는 초기 할당된 10개로 부족하므로 이 때 재할당되어 배열은 크기 16으로 늘어난다.
더 많은 요소를 삽입하면 배열은 자동으로 필요량을 판단하여 늘어날 것이다.
1.배열의 실체 -
이 예제에서 배열의 실체는 ar 포인터이다.
저장하고자 하는 타입의 포인터를 선언하고 이 포인터를 동적으로 할당하여 배열의 크기를 가변적인 크기를 다룰 수 있게 하였다.
2.배열 관리 변수 -
동적 배열은 컴파일할 때 그 크기가 미리 정해지지 않으며 실행중에 언제든지 크기를 변경할 수 있어야 한다.
할당 크기 저장 변수 - size
배열에 실제 저장된 요소 개수 저장 변수 - num
배열 관리 함수들은 배열에 요소를 삽입할 때 이 두 변수값을 비교해 보고 재할당할 시점을 파악할 것이다.
3.배열 초기화 -
배열의 실체인 ar이 포인터 변수이므로 ar에 메모리가 할당되기 전까지 배열은 실제로 존재하지 않는다.
main에서 InitArray(10,5) 로 호출했으므로 배열의 초기 할당치는 10이 되고 여유분은 5로 설정된다.
ar포인터가 메모리의 선두를 가리키게 되고, main에서 1~8까지의 정수를 추가했으므로
ar배열은 다음과 같다
----------------------------------
ar
↓ size = 10, num = 8
[1][2][3][4][5][6][7][8][?][?]
----------------------------------
총 10개의 요소를 기억할 수 있으며 8개를 저장했으므로 아직 두 개의 여유가 남아 있는 상황이다.
물론 이 남은 칸에는 쓰레기값이 들어 있을 것이다.
4.재할당 -
1~8까지 정수를 추가한 후 10, 11, 12를 요소 3의 위치에 순서대로 삽입하는데 10, 11까지 삽입되면 ar은 꽉 찬 상태가 된다.
이 상태에서 12를 더 삽입하려면 기억 공간이 부족하므로 배열의 크기를 늘려 재할당해야 한다.
배열의 크기가 늘어나는 경우는 Insert 함수에서 요소를 추가할 때 뿐이므로 이 함수의 선두에서만 배열 크기를 점검하면 된다.
┌ 여기에 12를 삽입하려고 한다. (need = 11, size = 10 이때 재할당 한다)
[1][2][3][11][10][4][5][6][7][8]
┌ 여기에 12를 삽입
[1][2][3][11][10][4][5][6][7][8][?][?][?][?][?][?]
└이만큼더늘린다┘
[1][2][3][12][11][10][4][5][6][7][8][?][?][?][?][?]
현재 크기가 부족하다는 판단이 내려졌으므로 새로운 크기를 계산하되 일단 need 이상 되어야 하고 여기에 약간의 여유분 growby를 더했다.
size는 16이 되며 이 크기대로 realloc 함수를 호출하여 ar 배열을 재할당한다.
만약 need가 size보다 더 작다면, 즉 아직 여유분이 남아 있다면 재할당없이 기존의 방법대로 삽입한다.
5. 여유분-
배열을 재할당할 때는 어느 정도의 여유분을 주는 것이 효율상 유리하다.
삽입은 보통 연속적으로 일어나므로 need만큼 필요해졌을 때 need만큼만 재할당하면 일단은 삽입 가능하지만 잠시 후 다시 재할당해야 할 확률이 상당히 높다.
realloc 함수는 편리하기는 하지만 번지가 바뀔 경우 굉장히 느리며 특히 배열의 크기가 클수록 속도상의 불이익이 심하기 때문에 가급적이면 호출 회수를 줄여야 한다.
그래서 이왕 재할당을 할 때 여유분을 주어 다음 번 부족한 상황을 최대한 늦추는 것이 좋다.
동적 배열은 이런 목적으로 growby라는 변수를 정의하고 재할당할 때 need에 이 값을 더한 크기로 배열을 늘린다.
여유분은 어디까지나 여유를 두기 위한 값이므로 이 값이 0이더라도 동적 배열은 제대로 동작하겠지만 성능이 떨어진다.
그렇다고 해서 여유분을 지나치게 크게 주면 남는 메모리가 많아져 공간 효율이 떨어진다.
필요에 따라 적당한 양을 주는 것이 좋으며 그래서 InitArray 함수를 호출할 때 개발자가 결정할 수 있도록 해 두었다.
예제에서는 재할당이 빨리 일어나도록 하기 위해 초기값, 여유분을 10, 5로 주었지만 실제 프로젝트에서는 배열의 삽입, 삭제 빈도에 따라 초기값과 여유분을 적당한 크기로 선택해야 한다.
100, 50 정도면 대체로 쓸만한 성능을 보일 것이며 자료의 양이 많고 삽입도 빈번하다면 1000, 500 정도로 충분한 값을 주어 성능의 향상을 꾀할 수 있다.
즉 InitArray의 인수들은 배열의 성능 파라미터인 것이다.
///////////////////////////////////////
WinAPI 의 강의를
초급 프로그래머가 더욱 이해하기 쉽게
편집, 추가, 삭제하여 작성한 글 입니다.
written by 호근
