2024.02.29 리뉴얼
자료구조와 배열
먼저 자료구조의 뜻은 아래와 같이 정의할 수 있다.
| 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계 혹은 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저정하는 방법 |
배열
같은 자료형의 변수로 이루어진 요소가 모여 직선 모양으로 줄지어 있는 자료구조.
배열을 선언할 때 요소개수는 상수만 사용이 가능하다. (변수 사용 시 동적할당을 이용한다.)
| 요소 | 배열의 해당 위치에 저장되있는 값 |
| 인덱스 | 요소의 위치 또는 배열의 개별 요소에 접근하기 위해 사용하는 값 |
배열에서 요소개수를 상수가 아닌 변숫값을 사용하면 에러가 나는데, 이는 위에서 언급한 조건에 해당되지 않기 때문이다. 이때, 마치 변수를 사용해서 배열을 선언한 것처럼 할 수 있다. 이를 이용하면 필요할 때 메모리를 확보하고 불필요시 메모리를 해제할 수 있다.
동적할당
메모리 확보/할당에 필요한 함수는 아래와 같다. 이때 조심할 점은 동적할당 함수는 일반적으로 사용되는 <stdio.h>가 아닌 <stdlib.h>에 정의되어 있으므로 사용 전 선언이 필요하다.
두 가지의 동적할당 함수 모두 메모리 할당에 성공 시 할당한 영역의 첫 번째 포인터를 반환하며 실패 시 NULL포인터를 반환한다.
malloc 함수
malloc 함수는 리턴값이 *void이다. 이때 사용자가 어떠한 자료형의 메모리를 동적할당 할지 알 수 없기에 선언에서 명시적 형변환이 필요하다. 아래의 예제 코드에서 arr 포인터 배열을 선언하고 malloc 함수를 사용해 동적할당하는 과정에 명시적 형변환하는 것을 볼 수 있다.
int * arr = (int *)malloc(sizeof(int) * len);
명시적 형변환에서 * 기호는 int 뒤에 작성한다!
포인터가 미리 선언되어 있는 경우 해당 포인터에 malloc 함수를 호출해 얻은 메모리 공간을 대입한다.
| malloc() 함수 | |
| 해더 |
#include <stdlib.h>
|
| 형식 | void *malloc(size_t x) |
| 해설 | 크기가 x인 메모리를 할당한다. 할당한 메모리의 값은 정의되지 않는다. 명시적 형변환이 필요하다. |
| 반환값 | 메모리 할당에 성공 시 할당한 영역의 첫 번째 포인터 반환. 실패시 NULL포인터를 반환한다. |
malloc 함수의 인자로는 배열의 사이즈를 가지며 이때 인자는 (자료형의 크기) * (배열의 크기)로 설정한다.
아래의 [더보기] 란의 예제를 참고한다.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int len = 4;
int * arr = (int *)malloc(sizeof(int) * len);
for(int i = 0; i < len; i++) *(arr + i) = i;
for(int i = 0; i < len; i++)printf("%d",arr[i]);
}calloc 함수
calloc 함수도 malloc과 마찬가지로 명시적 형변환이 필요하며, 함수의 인자로는 ( (배열의 크기), (자료형의 크기) )이다.
이때 순서를 헷갈리지 않도록 한다. 필자는 일반적으로 순서가 필요 없이 곱의 값으로 인자를 받는 malloc을 사용한다.
| calloc() 함수 | |
| 해더 |
#include <stdlib.h>
|
| 형식 | void *calloc(size_t x,size_t y) |
| 해설 | 크기가 y인 자료가 x개만큼 들어갈 메모리를 할당한다. 할당한 메모리 영역은 모든 비트가 0으로 초기화된다. |
| 반환값 | 메모리 할당에 성공 시 할당한 영역의 첫 번째 포인터 반환. 실패시 NULL포인터를 반환한다. |
아래의 [더보기] 란의 예제를 참고한다.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int len = 4;
int* arr = (int*)calloc(len,sizeof(int));
for (int i = 0; i < len; i++)printf("%d",arr[i]);
}free 함수
| free() 함수 | |
| 해더 |
#include <stdio.h>
|
| 형식 | void free(void *prt) |
| 해설 | prt가 가리키는 메모리 해제 후 다시 할당 가능하게함. 프로그램의 효율적인 공간 활용을 위해 메모리 할당 공간 사용 종료 시 해제하는 습관을 들이는 것이 중요함. |
| 반환값 | 없음 |
free 함수를 사용하면 프로그램을 실행하는 도중에도 원하는 시점에 변수를 생성하거나 제거할 수 있다.
⭐️TIP⭐️
C언어 상에서 선언은 컴파일러에게 대상에 대한 정보를 알려주고 실제 메모리를 사용하지 않는 반면, 정의는 컴파일러에게 대상의 실제 나용을 생성하고 할당하므로 메모리를 사용한다.
void 포인터
void 포인터는 calloc, malloc, free 함수는 char/int 형 객체 나아가 배열이나 구조체 객체 등 모든 자료형의 메모리 확보 또는 해제에 사용한다.
이때 특정한 자료형의 포인터를 주고받을 때 형이 서로 맞지 않으면 문제가 발생하므로 void 포인터를 반환하거나 받는 데 사용한다. 이때 void 포인터는 모든 형에 객체를 가리킬 수 있다.
동적할당을 이용한 예제
1. 배열 요소의 최댓값을 구하는 함수를 작성하라.
[ 입력 예시 ]
| 5 172 153 192 140 165 |
[ 출력 예시 ]
| 최댓값은 192입니다. |
[정답 코드]
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int maxof(const int arr[], int n){
int max = arr[0];
for(int i=0;i<n;i++){
if(max < arr[i]) max = arr[i];
}
return max;
}
int main(){
int num, *arr;
printf("사람 수: ");scanf("%d",&num);
arr = (int *)malloc(sizeof(int)*num);
printf("%d사람의 키를 입력하세요.\n",num);
for(int i=0;i<num;i++){
printf("height[%d]: ",i);scanf("%d",&arr[i]);
}
printf("최대값은 %d입니다.\n",maxof(arr,num));
free(arr);
}
/*
*/함수의 매개변수로 배열 사용하기
C언어의 함수 선언에서 매개변수의 배열 표기는 배열이 아니라 포인터를 선언하는 것과 같다. 따라서 예를 들어 매개변수 선언인 const int a[]는 const int *a로 해석된다.
이때 매개변수를 선언할 때 붙이는 const는 함수에서 그 인수가 가리키는 배열의 요솟값에 직접적으로 '쓰기'를 할 수 없는 고정 상수로 사용하도록 하는 메서드이다.
2. 난수를 사용해 배열의 요솟값 설정하기
배열의 요소에 값을 하나씩 입력하는 것이 번거로운 경우 각 요소에 난수를 대입하면 된다.
이때 난수 생성 함수는 아래의 포스팅을 이용하자.
이때 <include.time> 헤더를 작성하는 것을 잊지 않도록 한다.
난수 생성 라이브러리
라이브러리 난수를 생성하는 rand()함수가 반환하는 값은 0이상 (일반적으로) 32767 이하이다. #include rand()함수 사용 위함 #include time()함수 사용 위함 난수 생성 (컴파일 할 때마다 같음) #include #includ
udangtangtang-cording-oldcast1e.tistory.com
난수 생성에는 컴파일할 때마다 생성값이 같은 고정형과 컴파일할 때마다 난수 생성값이 다른 시드형이 있다. 이는 rand 함수가 seed를 이용해 난수를 생성하기 때문이다. seed가 N값으로 rand 함수에 심어져 있을 경우 프로그램을 실행할 때마다 N을 기준으로 랜덤 값을 생성한다. 이러한 seed를 바꿔주는 함수가 srand이다.
srand의 인자로는 time 라이브러리를 활용하여 프로그램 실행마다 다른 seed값을 주도록 한다.
time(NULL)은 현재 시간을 매개변수로 주기 때문에 프로그램 실행마다 새로운 seed를 가지고 난수를 생성한다. 따라서 프로그램 실행마다 값이 변화하는 것을 알 수 있다.
[ 입력 예시 ]
| 5 |
[ 출력 예시 ]
| height[0]: 156 height[1]: 139 height[2]: 165 height[3]: 181 height[4]: 145 최대값은 181입니다. |
[정답 코드]
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <time.h>
int maxof(const int arr[], int n){
int max = arr[0];
for(int i=0;i<n;i++){
if(max < arr[i]) max = arr[i];
}
return max;
}
int main(){
int num, *arr;
printf("사람 수: ");scanf("%d",&num);
arr = (int *)malloc(sizeof(int)*num);
// printf("%d사람의 키를 입력하세요.\n",num);
srand(time(NULL));
for(int i=0;i<num;i++){
arr[i] = 100 + rand()%99;
printf("height[%d]: %d\n",i,arr[i]);
//scanf("%d",&arr[i]);
}
printf("최대값은 %d입니다.\n",maxof(arr,num));
free(arr);
}
/*
*/3. 배열 요소를 역순으로 정렬하기
입력 예시 ]
| 5 10 73 2 -5 42 |
[ 출력 예시 ]
| 5 개의 정수를 입력하세요. 배열 요소를 역순으로 정렬했습니다. x[0]: 42 x[1]: -5 x[2]: 2 x[3]: 73 x[4]: 10 |
[정답 코드]
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define swap(type, x,y) do{type t = x; x = y; y = t;} while(0)
void arr_swap(int arr[], int num){
for(int i=0; i< num/2;i++){
swap(int,arr[i],arr[num-i-1]);
}
}
int main(){
int num, *arr;
printf("요소 개수: "); scanf("%d",&num);
arr = (int *)malloc(sizeof(int)*num);
printf("%d 개의 정수를 입력하세요.\n",num);
for(int i=0;i<num;i++){
printf("x[%d]: ",i);scanf("%d",&arr[i]);
}
arr_swap(arr,num);
printf("배열 요소를 역순으로 정렬했습니다.\n");
for(int i=0;i<num;i++){
printf("x[%d]: %d\n",i,arr[i]);
}
}
/*
*/위 코드에서 do while 문을 이용한 이유를 주목할 필요가 있다. do while문은 세미콜론이 while 함수 뒤에 붙으므로 불필요한 세미콜론을 사용함에 따른 오류가 발생할 수 있는 호출을 피할 수 있다.
4. 기수 변환 알고리즘
10진수를 n 진수로 변환하려면 정수를 n으로 나눈 나머지를 구하는 동시에 그 몫에 대해 나눗셈을 반복해야 한다.
이 과정을 몫이 0이 될 때까지 반복하고, 이 과정에서 구한 나머지를 거꾸로 늘어 놓은 숫자가 변환한 숫자이다.
이때 가장 신경 쓸 부분은 아래 코드의 dchar 배열이다. dchar 배열에서 진법 변환 할 수인 x와 기수 cd의 나머지 (x%cd)는 dcahr의 배열에서 계산된 인덱스를 인덱스로 가지는 대응되는 요소값을 가진다.
진법변환을 한다면
char dchar[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
을 꼭 사용하도록 하자![정답 코드]
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int card_cvt(unsigned int x, int n, char arr[]){
char dchar[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int digit = 0;
if(x == 0) arr[digit++] = '0';
else{
while(x){
arr[digit++] = dchar[x%n];
// printf(">>%c",arr[digit-1]);
x/=n;
}
}
return digit;
}
int main(){
int unsigned num,cd,tmp;//cd: 기수
char arr[512];
while(1){
printf("10진수를 기수 변환합니다.\n");
printf("변환하는 음이 아닌 정수: "); scanf("%d",&num);
printf("어떤 진수로 변환할까요?(2-36):") ;scanf("%d",&cd);
int digit = card_cvt(num,cd,arr);
for(int i=digit-1;i>=0;i--)printf("%c",arr[i]);
printf("\n다시 실행하기(1 - 예/0 - 아니오): "); scanf("%d",&tmp);
if(tmp == 0) break;
}
}
/*
*/5. 소수의 나열
불필요한 반복을 사용하는 소수의 나열
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main(){
unsigned count = 0,i,j;
int prime[500],cnt = 0;
prime[count ++ ] = 2;
for(i=3;i<=1000;i+=2){
for(j=3;j<i;j++){
cnt ++;
if(i%j == 0) break;
}
if(i==j)prime[count++] = i;
}
for(i=0;i<count;i++)printf("%d\n",prime[i]);
printf("count = %d",cnt);
}[ 출력 예시 ]
| /*출력 생략*/ count = 78022 |
알고리즘의 개선 1
소수의 탐색의 조건은 아래와 같다.
| 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다. |
이때 우리는 위에서 n의 소수여부를 확인하기 위해 2부터 n-1까지 소수 판단을 진행했다. 이때 소수 여부 판단 숫자인 n이 2가 아닌 짝수인 경우 소수에 해당되지 않으므로 짝수의 경우 연산을 제외하면 불필요한 반복을 줄일 수 있다.
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main(){
unsigned count = 0,i,j;
int prime[500],cnt = 0;
prime[count ++ ] = 2;
for(i=3;i<=1000;i+=2){
for(j=3;j<i;j++){
cnt ++;
if(i%j == 0) break;
}
if(i==j)prime[count++] = i;
}
for(i=0;i<count;i++)printf("%d\n",prime[i]);
printf("count = %d",cnt);
}[ 출력 예시 ]
| /*출력 생략*/ count = 77024 |
알고리즘의 개선 2
위 알고리즘 개선에는 소수의 판별을 짝수가 아닌 수로 했지만 이번에는 소수는 소수로 나누어 떨어지지 않음을 이용한다.
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main(){
unsigned count = 0,i,j;
int prime[500],cnt = 0;
prime[count ++ ] = 2;
for(i=3;i<=1000;i+=2){
for(j=0;j<count;j++){
cnt ++;
if( i % prime[j] == 0) break;
}
if(j == (count)) prime[count++] = i;
}
for(i=0;i<count;i++)printf("%d\n",prime[i]);
printf("count = %d",cnt);
}[ 출력 예시 ]
| /*출력 생략*/ count = 15121 |
이때 아래 코드와 같이 cnt의 자료형을 바꾸면 반복 횟수는 14622로 줄어든다. (필자도 이유를 모르겠다.)
unsigned long cnt = 0;[ 출력 예시 ]
| /*출력 생략*/ count = 14622 |
알고리즘의 개선 3
곱셈에서 순서는 상관이 없다. 따라서 정사각형 형태의 배열 즉 예를 들어 100, 10000과 같은 형태에서 각각 (10*10) (100*100)를 기준으로 (x * y)는 (y * x)과 동일하므로 정사각형의 한 변의 길이까지만 소수로 나눗셈을 시도하고, 그 과정에서 한 번도 나누어 떨어지지 않으면 소수라고 판단해도 좋다.
이는 제곱근과 소수의 관계로 설명할 수 있다.
n의 약수는 무조건 1 ~ √n의 범위에 존재한다.
✔️ 소수인지를 확인할 숫자 n의 제곱근 √n을 기준으로 약수끼리의 곱은 대칭으로 이루어진다.
✔️ 그렇기 때문에 √n 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다.
예를 들어 n = 18이라면, 18의 약수는 1, 2, 3, 6, 9, 18이다
이때 n의 제곱근인 √18은 약 4.242이며, 이를 기준으로 약수의 순서를 보면 아래와 같다
(1 x 18) (2 x 9) (3 x 6) √18 = 4.242 (6 x 3) (9 x 2) (18 x 1)
제곱근을 기준으로 좌우의 연산이 대칭되는 형상을 가진다 (예) (3 x 6) √18 (6 x 3) 그렇기 때문에 제곱근과 같거나 작은 숫자로 나누어지면, 그 이후는 대칭이므로 확인할 필요가 없다.
즉, 제곱근 값 이하의 수만 확인하면 되며 √18은 약 4.242 이므로, 4까지 확인했을 때 나누어 떨어지지 않으면 소수가 아니다.
정리하면. 소수의 판별 조건에는 하나가 추가된다.
| 소수를 저장한 배열 prime[i]의 제곱이 n 이하인가? |
정답 코드는 아래의 [더보기] 란을 확인한다.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main(){
unsigned count = 0,i,j;
int prime[500];
unsigned long cnt = 0;
prime[count ++ ] = 2;
prime[count ++ ] = 3;
for(i=5;i<=1000;i+=2){
for(j=1;j<count;j++){
if(prime[j]* prime[j] < i){
cnt ++;
if( i % prime[j] == 0) break;
}
}
if(j == (count)) prime[count++] = i;
}
for(i=0;i<count;i++)printf("%d\n",prime[i]);
printf("count = %lu",cnt);
}[ 출력 예시 ]
| /*출력 생략*/ count = 2060 |
'Datastructure > [3] 데이터구조' 카테고리의 다른 글
| [3] 데이터구조 ③ 구조체 (1) | 2024.03.02 |
|---|---|
| [3] 데이터구조 ① 배열 (0) | 2022.01.04 |
