02. 기본 자료구조

Notice

Recent Posts

Recent Comments

Link

« 2025/01 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

촉촉한초코칩

02. 기본 자료구조 본문

Algorithm

02. 기본 자료구조

햄친구베이컨 2022. 8. 9. 23:05

02-1 배열

자료구조 (data structure) : 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계

* 데이터 단위는 데이터를 구성하는 한 덩어리라고 생각하면 된다. 자료구조는 쉽게 말해 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법을 말한다.

배열 (array)

같은 자료형의 변수로 이루어진 요소 (element)가 모여 직선 모양으로 줄지어 있는 자료구조
배열 선언 방법

자료형 배열이름[요소개수];
ex) int a[5];

요소 개수는 상수만 사용할 수 있다. (변수 사용 불가)

* 상수식은 상수만을 포함하는 식으로, 실행 시점이 아닌 컴파일 시점에 계산된다.

요소와 인덱스

배열의 모든 요소는 직선 모양으로 줄지어 있다.
배열의 개별 요소에 접근하기 위해 사용하는 것이 연산자 [ ] 안에 넣는 정수형 인덱스이다.
배열 요소의 인덱스는 0부터 (요소개수-1)까지 있다.
배열의 요소에 접근하는 식

배열이름[인덱스];
ex) a[5];

각각의 요소는 배열로 선언한 것이 아닌 단일로 선언한 변수와 같기 때문에 각 요소에 값을 대입하거나 제거할 수 있다.
일반적으로 자료형이 Type이고 요소 개수가 n인 배열의 자료형은 Type[n]으로 나타낸다.
* 배열 a의 각 요소의 자료형은 int형이고, 배열 a의 자료형은 int[5]형이다. 다시 말해 a[0]은 int형, a는 int[5]형이다.
- ex)int a[5]라고 선언하면 배열 a는 a[0], a[1], a[2], a[3], a[4]로 총 5개의 int형 저장 공간을 갖는다.

배열의 요소값을 초기화하며 배열 선언하기

배열의 각 요소에 넣을 값을 미리 알고 있다면 선언할 때 초기화할 수 있다.

int a[5] = {1,2,3,4,5};

배열 개수 말고 배열 안에 넣을 데이터만으로 선언할 수도 있다.

ex) int a[] = {1,2,3,4,5,6};

배열의 요소 개수 구하기

sizeof(a) / sizeof(a[0])

sizeof(a) : 전체 배열이 할당된 메모리 크기 구하기
sizeof(a[0]) : 첫번째 요소가 할당된 메모리 크기 구하기
해당 식은 요소의 자료형이나 크기에 영향을 받지 않고 배열의 요소 개수를 구할 수 있다.

배열을 선언할 때 요소 개수는 상수만 사용하기 때문에 변수를 사용하면 오류가 발생한다.

int n;
scanf("%d", &n);
int a[n]; //컴파일 오류

하지만 변수를 사용해서 배열을 선언한 것처럼 할 수도 있다. 필요할 때 메모리를 확보하고 불필요해지면 메모리를 해제하여 필요한 요소 개수의 배열을 언제든지 자유롭게 만들 수 있다.

메모리 할당 기간과 동적 객체 생성

메모리를 확보하기 위해 제공되는 함수 : callloc, malloc

calloc 함수
헤더	#include <stdlib.h>
형식	void * calloc(size_t nmemb, size_t size);
해설	크기가 size인 자료가 nmemb개만큼 들어갈 메모리를 할당한다. 할당한 메모리 영역은 모든 비트가 0으로 초기화된다.
반환값	메모리 할당에 성공하면 할당한 영역의 첫 번째 포인터를 반환하고 실패하면 NULL 포인터를 반환한다.

malloc 함수
헤더	#include <stdlib.h>
형식	void *malloc(size_t size);
해설	크기가 size인 메모리를 할당한다. 할당한 메모리의 값은 정의되지 않는다.
반환값	메모리 할당에 성공하면 할당한 영역의 첫 번째 포인터를 반환하고 실패하면 NULL 포인터를 반환한다.

calloc, malloc 함수는 힙이라는 특별한 빈 공간에 기억 장소를 확보한다. 이때 확보한 메모리가 불필요하면 그 공간을 해제해야 한다. → free 함수 사용

free 함수
헤더	#include <stdlib.h>
형식	void free(void *ptr);
해설	ptr이 가리키는 메모리를 해제하여 이후에 다시 할당할 수 있도록 한다. ptr이 NULL 포인터인 경우 아무것도 하지 않는다. 이때 ptr로 전달된 실인수가 calloc 함수, malloc 함수, realloc 함수에 의해 반환된 포인터가 아니거나 영역이 free 함수, realloc 함수를 호출하여 이미 해제된 영역이면 아무것도 하지 않는다.
반환값	없다.

free 함수를 사용하면 프로그램을 실행하는 도중에도 원하는 시점에 변수를 생성하거나 제거할 수 있다.

* NULL은 stdlo.h 파일에 매크로로 정의되어 있고 값이 없음을 의미한다.

#define NULL((void *)0)

선언 : 컴파일러에게 대상에 대한 정보를 알려준다. 다만 실제 내용을 할당하지 않으므로 메모리를 사용하지 않는다.
정의 : 컴파일러에게 대상의 실제 내용을 생성하게 한다. 실제 내용을 생성하고 할당하므로 메모리를 사용한다.

* C언어의 메모리 구조

프로그램을 실행하면 운영체제는 프로그램이 사용할 메모리 영역을 할당한다. 할당하는 메모리 영역은 데이터(Data), 스택(Stack), 힙(Heap) 영역으로 나뉜다.

할당 시기 : 프로그램이 실행될 때마다 할당
할당 장소 : 메인 메모리(RAM)
할당 용도 : 프로그램 실행에 필요한 메모리 영역(지역변수, 전역 변수 선언을 위해) 할당

데이터 (Data) 영역	전역 변수와 정적 (static) 변수가 할당되는 영역
데이터 (Data) 영역	프로그램을 시작하면 할당하고, 프로그램을 종료하면 메모리에서 해제한다.
스택 (Stack) 영역	함수 호출 시 생성되는 지역 변수와 매개변수가 저장되는 영역
스택 (Stack) 영역	함수 호출이 완료되면 사라진다.
힙 (Heap) 영역	필요에 따라 동적으로 메모리를 할당한다.

* 힙 영역은 할당해야 할 메모리 영역의 크기를 프로그램이 실행되는 동안 (run time) 결정해야 하는 경우에 사용한다.

힙 영역은 관리가 가능한 데이터 외에 다른 형태의 데이터를 관리하기 위한 빈 공간이다.

즉, 동적 할당을 통해 생성된 동적 변수를 관리하기 위한 영역이다.

힙 영역은 위의 다른 영역(데이터, 스택 등)을 모두 할당하고 남은 공간이다. 남은 공간은 시스템의 메모리 영역의 여유 공간에 따라 달라진다. Java에서 'new'를 사용했던 것 처럼 C언어에서는 malloc, calloc 함수 등을 사용해서 동적으로 생성하는 변수를 저장하기 위해 할당하는 영역을 말한다.

데이터 영역과 스택 영역은 컴파일러가 미리 공간을 예측하고 할당할 수 있지만, 동적 변수는 어느 시점에 얼마만큼의 공간을 할당할지 정확하게 예측할 수 없으므로 프로그램 실행 중에 결정한다.

#include <stdio.h>
#include <stdlib.h>

int main() {    

    int *x;
    x = calloc(1,sizeof(int));
    if(x==NULL) {
        printf("메모리 할당에 실패했습니다.");
    } else {
        *x=57;
        printf("*x=%d\n", *x);
        free(x);
    }


    return 0;
}

보통 포인터 p가 가리키는 메모리 주소의 값은 *를 사용한 식 *p를 사용하여 접근할 수 있다.

포인터 x가 확보한 메모리 영역을 가리키고 있으므로 확보한 메모리 영역은 *x로 접근할 수 있다.

배열의 동적 생성

ex) 자료형인 int형 배열을 동적으로 생성하는 프로그램. malloc 함수와 calloc 함수의 호출을 비교해본다.

단일한 int형 객체 생성	calloc(1, sizeof(int))
자료형이 int형ㅇ이고, 요소 개수가 na인 배열 생성	calloc(na, sizeof(int))

calloc 함수가 확보하는 것은 특정한 자료형의 객체가 아니라 단순히 메모리 영역이다.
calloc 함수는 확보한 메모리의 첫 번째 주소를 반환하고 그 값은 포인터 a에 대입된다. 이때 포인터와 배열은 서로 바꾸어 쓸 수 있다.
따라서 확보한 메모리의 요소는 식 a[0], a[1], a[2] 등으로 접근할 수 있다. 이렇게 사용하면 포인터 a를 마치 배열인 것처럼 사용할 수 있다.

해당 프로그램은 배열의 요소 개수를 실행 시점엘 결정한다. 배열을 생성한 후 for문으로 반복하여 요소 a[i]의 값을 읽고 그 값을 출력한다.

#include <stdio.h>
#include <stdlib.h>

int main() {    

    int *a;
    int na = 5;
    a = calloc(na, sizeof(int));
    
    if(a==NULL) {
        printf("메모리 확보 실패");
    } else {
        for(int i=0; i<5; i++)
            scanf("%d", &a[i]);
        
        for(int i=0; i<5; i++)
            printf("%d\n", a[i]);
    }
    free(a);

    return 0;
}

* 단일 객체 생성과 다른 점은 확보한 영역이 5개로 배열의 개수와 크기가 동일하다는 것이다.

a는 배열에 사용하기 위해 확보한 메모리의 첫 번째 주소를 가리키는 포인터이다. a의 의미가 배열은 아니지만 앞으로 '배열 a를 생성한다', '배열 a를 해제한다'라는 의미로 사용될 수 있다.

* void 포인터

void는 배열이나 구조체 객체 등 모든 자료형의 메모리 확보 또는 해제에 사용한다.
특정한 자료형의 포인터를 주고받을 때 자료형이 서로 맞지 않으면 문제가 발생하므로 void 포인터로 반환하거나 받는 데 사용한다.
void 포인터는 모든 형의 객체를 가리킬 수 있다. void 포인터의 값을 모든 자료형의 포인터에 대입할 수 있고 또는 모든 자료형의 포인터 값을 void 포인터에 대입할 수 있다.

* 포인터와 배열

포인터 : 객체(변수) 또는 함수를 가리키는 것
포인터 선언 예시

int *p;    //p : int형 객체를 가리키는 포인터
double *q; //q : double형 객체를 가리키는 포인터

포인터의 자료형은 포인터가 가리키는 곳의 객체의 자료형을 따라간다.
int 형 객체를 가리키는 포인터는 int *형이고, double 형 객체를 가리키는 포인터는 double *형이다.
n이 int형 객체라고 할 때, 포인터 p가 객체 n을 가리키기 위해서는 n의 주소를 p에 대입해야 한다.

p = &n; //n의 주소를 p에 대입한다. (p가 n을 가리키도록 한다.)

n에 사용한 단항 연산자 &는 주소 연산자라고 하며 피연산자(n)의 주소를 가져온다.
포인터 p가 가리키는 객체의 값은 간접 연산자라고 하는 단항 연산자인 *를 사용해서 접근할 수 있다.
p가 n을 가리키면 p가 가리키는 곳에 있는 n의 값을 접근하는 식은 *p가 된다.
그러므로 다음을 실행하면 n에 999가 대입된다.

*p = 999; //p가 가리키는 곳에 999를 대입한다.

다시 말해, *p는 n과 같다고 할 수 있다. 만약 p가 다른 객체 x를 가리킨다면, *p는 x와 같다고 할 수 있다.

포인터와 배열

배열 a와 포인터 p가 선언될 때 p의 초기화는 배열 이름인 a로 할 수 있다. 그런데 배열 이름은 그 배열의 첫 번째 요소에 대한 포인터로 해석할 수 있다.
즉, a에 들어있는 값은 a[0]의 주소인 &a[0]와 같다. 배열 a의 자료형이 Type이면 요소 개수와 상관없이 a의 자료형은 Type* 형이된다.
따라서 포인터 p에 주어진 초기화 값이 a이므로 p에 넣는 것은 &a[0]의 값과 같아진다. 그 결과로 피언트 p는 배열 a의 첫 번째 원소 a[0]를 가리키도록 초기화된다.

배열의 요소를 가리키는 포인터 규칙 -> 포인터 p가 배열의 요소 e를 가리킬 때
p + i	요소 e의 i개만큼 뒤쪽의 요소를 가리키는 포인터
p - i	요소 e의 i개만큼 앞쪽의 요소를 가리키는 포인터

배열의 요소를 가리키는 포인터 p+i에 간접 연산자 *를 적용한다면? ->
p + i는 p가 가리키는 요소의 i개만큼 뒤쪽에 있는 요소를 가리키는 포인터이므로 p에 간접 연산자를 적용한 식 *(p+i)는 a[i]에 접근하는 식이 된다.
그러므로 p가 a[0]을 가리키면 식 *(p+i)는 a[i]와 같다.
* 아래 규칙을 반드시 기억해둘것!

배열의 요소를 가리키는 포인터 규칙 -> 포인터 p가 배열의 요소 e를 가리킬 때
p + i	요소 e의 i개만큼 뒤쪽의 요소를 가리키는 포인터	*(p + i)는 p[i]로 표시
p - i	요소 e의 i개만큼 앞쪽의 요소를 가리키는 포인터	*(p - i)는 p[-i]로 표시

ex) p+2와 *(p+2)는 a[2]를 가리키는 것과 동일.

*(p+2)를 p[2]로 표기할 수 있으므로 p[2]는 a[2]와 같다.

여기서 배열 이름 a는 첫 번째 요소 a[0]에 대한 포인터이다. 그 포인터에 2를 더한 a+2는 세 번째 요소 a[2]에 대한 포인터이다.

포인터 a+2가 요소 a[2]를 가리키므로 포인터 a+2에 *를 적용한 *(a+2)는 a[2]와 같다.

즉, *(a+2), p[2], *(p+2) 모두 배열 요소인 a[2]에 접근하는 식이 된다.

아래 4개의 식은 모두 배열의 각 요소에 접근하는 식이다. ( 첫 번째부터 i개 뒤쪽의 요소)
a[i]	*(a + i)	p[i]	*(p + i)
아래 4개의 식은 배열의 각 요소를 가리키는 포인터이다. (첫 번째부터 i개 뒤쪽의 요소를 가리키는 포인터)
&a[i]	a + i	&p[i]	p + i
첫 번째 요소를 가리키는 포인터 * 포인터가 배열의 첫 번째 요소를 가리킬 경우 그 포인터는 마치 배열처럼 동작할 수 있다.		a + 0	a
		p + 0	p
		*(a+0)	*a
		*(p+0)	*p

공백 포인터(null pointer)와 NULL

공백 포인터 : 정수값 0은 모든 포인터형으로 형변환이 가능하며 그 결과는 NULL 포인터이다.
공백 포인터를 나타내는 것 : 공백 포인터 상수(null pointer constant), 매크로 NULL
NULL의 정의 : 값 0을 갖는 모든 정수, 상수 또는 상수식을 void*로 형변환한 식
매크로 NULL은 <stddef.h> 헤더에 정의되어 있다. 그 외에 <locale.h>, <stdio.h>, <stdlib.h>, <time.h> 헤더를 포함해도 선언한 것과 마찬가지로 동작한다.

//NULL 정의 예시
#define NULL 0          //NULL을 정의한 예시
#define NULL(void *)0   //NULL을 정의한 예시 (C++에서는 불가능)

배열 요소의 최대값 구하기 알고리즘

배열의 요소 개수와 관계없이 첫 번째 요소의 값을 max에 대입한다.
요소 개수가 n이라면, for문은 n-1번 동작한다.
if문을 실행해서 요소의 인덱스 값을 하나씩 증가시키고 max와 값을 비교한다.
만약 요소의 인덱스 값이 max보다 크다면 max에 그 요소를 넣는다.

배열의 요소를 하나씩 차례로 살펴보는 과정을 알고리즘 용어로 주사(스캐닝, traverse)라고 한다.

결과적으로 배열의 모든 요소에 대해 주사를 완료한 시점의 배열의 최대 요소값이 max에 대입된다.

#include <stdio.h>
#include <stdlib.h>

int maxof(const int a[], int n) {
    int max = a[0];
    for(int i=0; i<n; i++) 
        if (a[i] > max) max = a[i];
    return max;
}

int main(void) {
    int *height; //배열의 첫 번째 요소 포인터
    int number;  //인원=배열 height의 요소 개수
    printf("사람 수 : ");
    scanf("%d", &number);

    height = calloc(number, sizeof(int)); //요소 개수 number개인 배열 생성
    printf("%d 사람의 키를 입력하세요\n", number);
    for(int i=0; i<number; i++) {
        printf("height[%d] : ", i);
        scanf("%d", &height[i]);
    }
    printf("최대값은 %d입니다.\n", maxof(height, number));
    free(height); //배열 height 해제
}

* 함수의 매개변수로 배열 사용하기 - maxof 함수의 매개변수 a의 선언 const int a[]에 대해 더 알아보기

C언어의 함수 선언에서 매개변수의 배열 표기(a[])는 배열이 아니라 포인터를 선언한 것과 같다.

그러므로 매개변수 선언인 const int a[]는 const int *a로 해석된다.

이때 매개변수를 선언할 때 붙이는 const는 함수에서 그 인수가 가리키는 배열의 요소값에 직접적으로 쓰기를 할 수 없게 만든다. → maxof 함수 안에서 a[i]의 값은 읽기만 가능하고 쓰기는 불가능하게 된다.

int main(void) {
	int *height;
	maxof(height, number);
}

int maxof (const int a[], int n) { }

const int *a = height; //동일 

//main 함수의 height와 maxof 함수의 a는 같은 배열의 첫 번째 요소를 가리키게 된다.

maxof 함수를 호출하면 전달된 포인터 height(&height[0])에서 매개변수 a가 초기화되기 때문에 포인터 a는 height[0]의 주소를 가리키게 된다.

이때 전달받은 인수 (height)는 포인터이지 배열이 아니므로 배열의 요소 개수는 새로운 인수로 전달받아야 한다. -> n

(호출하는 함수는 배열으 요소 개수를 알 수 없다.)

난수를 사용해 배열의 요소값 설정하기

배열의 요소에 값을 하나씩 입력하는 것이 귀찮을 때는 각 요소에 난수를 대입하면 된다.

/* 배열 요소의 최댓값을 구합니다(값을 난수로 생성). */
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

/*--- 요솟수가 n인 배열 a의 요소의 최댓값을 구합니다. ---*/
int maxof(const int a[], int n) {
	int max = a[0]; 		/* 최댓값 */
	for (int i = 1; i < n; i++)
		if (a[i]> max) max = a[i];
	return max;
}

int main(void) {
	int *height; 		/* 배열의 첫 번째 요소의 포인터 */
	int number; 		/* 사람 수 = 배열 height의 요솟수 */
	printf("사람 수 : ");
	scanf("%d", &number);

	height = calloc(number, sizeof(int));		/* 요솟수가 number인 배열을 생성 */

	srand(time(NULL));                          /* 시간으로 난수의 seed(씨앗)을 초기화 */
	for (int i = 0; i < number; i++) {
		height[i] = 100 + rand() % 90;			/* 100 ~ 189의 난수를 생성 · 대입 */
		printf("height[%d] = %d\n", i, height[i]);
	}

	printf("최댓값은 %d입니다.\n", maxof(height, number));
	
	free(height); 			/* 배열 height를 해제 */

	return 0;
}

난수 생성 단계 요약

rand 함수, srand 함수, time 함수의 선언이 들어 있는 헤더 포함
난수의 seed를 초기화하기 위해 srand 함수 호출
난수를 생성하기 위해 rand 함수 호출

* 2번을 한 번 실행하고 난수가 필요할 때마다 3번을 실행시킨다.
* 생성한 난수를 90으로 나눈 나머지 (0~89)에 100을 더하므로 height[i]에 대입되는 키의 값은 100~189이다.
* 난수를 생성하는 rand 함수가 반환하는 값은 0 이상 RAND_MAX 이하의 값이다. 이때 <stdlib.h> 헤더에 정의된 RAND_MAX 값은 컴퓨터 환경에 따라 다르다.

#incldue <stdio.h>
#include <stdlib.h>

//생략

x = rand();   //0 이상 RAND_MAX 이하의 난수 생성
y = rand();   //0 이상 RAND_MAX 이하의 난수 생성

* 해당 프로그램은 몇 번을 실행해도 x와 y값이 같다.
* 프로그램에서 첫 번째 생성되는 난수, 두 번째 생성되는 난수, 세 번째 생성되는 난수가 정해져 있다.
- 왜냐하면 rand 함수는 seed를 사용해서 난수를 생성하기 때문이다. seed가 상숫값 1로 rand 함수에 심어져 있다고 가정할 경우, rand 함수는 프로그램을 실행할 때마다 상수값 1을 기준으로 매번 같은 순서의 난수를 생성하게 된다.
* 이때 seed 값을 변경하는 것이 srand 함수이다.

srand(50);  //seed의 값을 50으로 설정

* 만약 50을 매개변수로 전달해서 srand 함수를 호출하면 seed의 값을 변경할 수 있다. 하지만 이렇게 상수(seed)를 전달하는 srand 함수를 호출한다고 해도 이후에 rand 함수가 생성하는 난수의 순서는 seed의 값을 기준으로 생성되므로 같은 문제가 발생한다.
* 그러므로 srand 함수에 전달되는 매개변수는 임의의 (random) 난수여야 한다. 난수를 생성하기 위해 난수가 필요하다.
일반적으로 사용하는 방법으로는 srand 함수에 현재 시간의 값을 준다.

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

srand(time(NULL));

* time 함수가 반환하는 값은 time_t형의 값인 현재 시간이다.
프로그램을 실행할 때마다 시간이 달라지고, 그 현재 시간의 값을 seed로 srand 함수에 전달하면 생성되는 난수도 무작위로 생성된다. 현재 시간은 매 순간 바뀌므로 이전에 발생한 의사 난수를 다시 생성하지 않는다.
* 사실 rand 함수가 생성하는 난수는 의사 난수이다. 그 이유는 한 번 난수를 생성하면 다음에 생성할 난수를 예측할 수 있기 때문이다. 의사난수가 아닌 진짜 난수는 다음에 생성할 난수를 예측할 수 없다.
* 만약 srand 함수에 전달한 seed의 값과 컴퓨터 환경이 같다면 그 결과값은 항상 같다. 결국 컴퓨터에 의해 생성된 모든 난수는 미리 컴퓨터가 계산해 둔 의사 난수이다. 컴퓨터는 게산된 결과만 가지고 난수를 생성하는데, 이 계산된 결과는 입력값에 의해 결정되므로 이 값으로 임의의 난수를 생성할 수는 없다.
* 따라서 프로그램에서 매번 같은 방법으로 난수를 가져오면 처음 실행할 때 이외에는 난수라고 할 수 없다. 그래서 보통 seed라 불리는 수를 srand 함수에 매개변수로 매버 다르게 전달해 항상 다른 의사 난수를 생성해야 한다.
* 의사 난수 : 난수처럼 보이지만 일정한 규칙에 따라 생성되는 수

배열 요소를 역순으로 정렬하기

배열 요소가 7개 있다면, [0]과 맨 뒤의 요소 [6]의 값을 교환한다. 그리고 하나씩 안쪽의 요소값을 교환한다.
교환 횟수 : 요소개수/2 (나머지는 버림)
요소개수가 n인 배열을 처리하는 과정을 변수 i의 값을 0, 1...로 증가하는 방법을 통해 나타내기

1. 왼쪽 요소의 인덱스 (i)	n이 7이라면 0 -> 1 -> 2
2. 오른쪽 요소의 인덱스 (n-i-1)	n이 7이라면 6->5->4

요소 개수가 n인 배열 요소를 역순으로 정렬하는 알고리즘

for(i=0; i<n/2; i++)
	//a[i]와 a[n - i - 1]의 값을 교환한다.

역순으로 바꾸지만 내부적으로는 두개의 값을 교환하는 것이기 때문에 변수 하나를 더 만들어서 3개의 값을 교환하면 된다.

for(int i=0; i<n/2; i++) {
	int t = a[i];
	a[i] = a[n-i-1];
	a[n-i-1] = t;
}

이때 반복해서 수행해야 하는 두 값을 교환하는 과정을 함수 형식 매크로로 구현하면 프로그램이 짧아지고 읽기 쉬워진다.

/* 배열 요소를 역순으로 정렬합니다. */
#include <stdio.h>
#include <stdlib.h>

/*--- type형의 x와 y 값을 교환 ---*/
#define swap(type, x, y) do { type t = x; x = y; y = t;} while (0)

/*--- 요소 개수가 n인 배열 a의 요소를 역순으로 정렬 ---*/
void ary_reverse(int a[], int n) {
	for (int i = 0; i < n / 2; i++)
	    swap(int, a[i], a[n - i - 1]);
}

int main(void) {
	int *x; 		/* 배열 첫 번째 요소의 포인터 */
	int nx; 		/* 배열 x의 요소 개수 */

	printf("요소 개수 : ");
	scanf("%d", &nx);
	x = calloc(nx, sizeof(int)); 	/* 요소 개수가 nx인 int형 배열 x를 생성 */

	printf("%d개의 정수를 입력하세요.\n", nx);
	for (int i = 0; i < nx; i++) {
		printf("x[%d] : ", i);
		scanf("%d", &x[i]);
	}

	ary_reverse(x, nx); 		/* 배열 x의 요소를 역순으로 정렬 */
	printf("배열의 요소를 역순으로 정렬했습니다.\n");
	for (int i = 0; i < nx; i++)
		printf("x[%d] = %d\n", i, x[i]);
	
	free(x); 			/* 배열 x를 해제 */

	return 0;
}

swap() : type형 변수 x와 y 값 교환하는 함수 형식 매크로
any_reverse() : 함수 형식 매크로 swap()을 n/2회 호출하여 배열 요소를 역순으로 정렬한다.

* 함수 형식 매크로는 프로그램을 컴파일 하는 과정에서 치환된다.

for(int i=0; i<n/2; i++) 	
	do { int t = a[i]; a[i] = a[n-i-1]; a[n-i-1] = t; } while(0);

do문의 반복을 계속할지의 여부를 판단하는 제어식이 0이기 때문에 do { } 코드는 1회만 실행된다. 루프의 코드가 2회 이상 반복되지 않으므로 치환되는 코드는 결국 아래 프로그램과 같다.

for(int i=0; i<n/2; i++) 
	{ int t = a[i]; a[i] = a[n-i-1]; a[n-i-1] = t; }

do문을 사용하는 이유

1) 잘못된 정의

- 아래처럼 정의하면 컴파일 오류가 발생한다.

if(a > b)
	swap(int,a,b);
else
	swap(int,a,c);

- if문을 만족한다고 하면 { } 블록이 실행되고 바로 뒤에 else문이 나와야 하는데 swap()으로 인해 세미콜론 ; 이 나온다. 이렇게 되면 else에 대응하는 if가 세미콜론에 의해 끊어진다.

#define swap(type,x,y) {type t = x; x = y; y = t; }
if(a>b)
	{ type t = a; a = b; b = t; } ;
                    //첫번째 세미콜론 까지만 if문으로 해석하고 나머지 명령문은 대응하는 if문이 끊어지게 된다. 
else
	{ type t = a; a = c; c = t; } ;

2) 올바른 정의

- 함수 형식 매크로 swap의 올바른 정의와 프로그램의 일부(치환한 모습)

#define swap(type,x,y) do { type t = x; x = y; y = t; } while(0)

if(a>b)
	do { type t = a; a = b; b = t; } while(0);
else
	do { type t = a; a = c; c = t; } while(0);

- do문의 구분 표기법이 do문 while(식);이기 때문에 전체를 if문으로 인식해 올바른 프로그램이 된다.

기수 변환

정수 값을 임의의 기수로 변환하는 알고리즘

- 10진수 정수를 n 진수 정수로 변환하려면 정수를 n으로 나눈 나머지를 동시에 그 몫에 대해 나눗셈을 반복해야 한다. 몫이 0이 될 때까지 반복하고 구한 나머지를 거꾸로 늘어 놓은 숫자가 기수로 변환한 숫자가 된다.

ex) 59 -> 2진수로 변환

59 / 2 = 29...1

29 / 2 = 14...1

14 / 2 = 7...0

7 / 2 = 3...1

3 / 2 = 1...1

1 / 2 = 0...1 (끝)

(아래자리) 110111 (윗자리)

16진수

0~F는 10진수 0~15에 해당한다. 이 숫자를 모두 사용하면 자릿수가 한 자리 올라가 10이 된다.
2자리 숫자는 10부터 시작하여 FF까지이다. 이 2자리의 숫자를 모두 사용하면 그 다음 수는 100이 된다.
16진수의 각 자리는 아랫자리부터 16^0, 16^1, 16^2..으로 16의 거듭제곱 값을 갖는다.
ex) 12A0 (0x12A0) = 1 * 16^3 + 2 * 16^2 + 10 * 16^1 + 0 * 16^0

10진수

0~9의 숫자를 모두 사용하면 자릿수가 한 자리 올라가 10이 된다.
2자리의 숫자는 10에서 시작하여 99까지이다. 99의 다음 수는 다시 한 자릿수 올라가 100이 된다.
10진수의 각 자리는 아랫자리부터 10^0, 10^1, 10^2..으로 10의 거듭제곱 값을 갖는다.
ex) 1234 = 1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0
* 10^0은 1이다. 2^0, 8^0 모두 0 제곱의 값은 1이다.

8진수

0~7 숫자를 모두 사용하면 자릿수가 한 자리 올라가 10이 되고 그 다음 수는 11이 된다.
2자리 숫자는 10부터 시작하여 77까지이다. 이 2자리의 수를 모두 사용하면 그 다음 수는 100이 된다.
8진수의 각 자리는 아랫자리부터 8^0, 8^1, 8^2..으로 8의 거듭제곱 값을 갖는다.
ex) 5306 = 5 * 8^3 + 3 * 8^2 + 0 * 8^1 + 6 * 8^0

* 정수 상수는 정수 계열의 값을 나타내는 10진수, 8진수, 16진수이다. 정수 상수는 변경할 수 없는 정수 값을 나타낼 때 사용한다. 정수 상수가 0x또는 0X로 시작하는 경우 16진수이고, 숫자 0으로 시작하는 경우에는 8진수이다. 두 경우에 해당하지 않으면 10진수로 간주한다.

기수변환하는 프로그램

/*정수를 2~36진수로 변환*/
#include <stdio.h>

/*정수 값 x를 n진수로 변환하여 배열 d에 아랫자리부터 저장*/
int card_convr(unsigned x, int n, char d[]) {
	char dchar[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int digits = 0; //변환 후 자릿수
	if(x == 0)  //0이라면 
		d[digits++] = dchar[0]; //변환 후에도 0
	else
		while(x) {
			d[digits++] = dchar[x%n]; //n으로 나눈 나머지 저장
			x /= n;
		}
	return digits;
}

card_convr() : 정수 x를 n진수로 변환한 값의 각 자리의 문자를 char 형 배열 d에 저장하고 그 자릿수를 반환하는 함수이다.

char형의 배열 dchar는 "0123456...Z"로 초기화되므로 각 문자는 아래 식으로 접근할 수 있다.

숫자문자	알파벳
dchar[0] 문자 0	dchar[10] 문자 A
dchar[1] 문자 1	dchar[11] 문자 B

만약, x가 59이고 n이 16이라면 x % n = 11이다. -> 문자 B

0으로 초기화한 변수 digits는 변환한 다음 수의 자릿수를 나타내기 위한 변수이다. whlie문의 루프 본문은 다음 작업을 수행한다.

먼저 x를 n으로 나눈 나머지를 인덱스로 하는, 배열 dchar 안의 문자 dchar[x % n]을 배열 d으 요소 d[digits]에 대입하고 digits 값을 증가시킨다. (다음 인덱스에 값을 저장하기 위해 digits 증가)
x를 n으로 나눈다.

이 작업을 x가 0이 될 때까지 반복한다.

ex) 59 % 16 = 3...11 B -> d[0] = dchar[11] 넣고 digits 증가. d[1]을 가리킨다.

3 % 16 = 0...3 -> d[1] = dchar[3]을 넣고 digits 증가. d[2]를 가리킨다.

나머지를 구하는 순서대로 배열 d에 저장하지만 변환한 후의 d 값은 역순으로 배치된다.

즉, B3이 아니라 3B가 59를 16진수로 변환한 값이 된다.

/*정수를 2~36진수로 변환*/
#include <stdio.h>

/*정수 값 x를 n진수로 변환하여 배열 d에 아랫자리부터 저장*/
int card_convr(unsigned x, int n, char d[]) {
	char dchar[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int digits = 0; //변환 후 자릿수
	if(x == 0)  //0이라면 
		d[digits++] = dchar[0]; //변환 후에도 0
	else
		while(x) {
			d[digits++] = dchar[x%n]; //n으로 나눈 나머지 저장
			x /= n;
		}
	return digits;
}

int main(void) {
	unsigned no; //변환하는 정수
	int cd; //기수
	int dno; //변환 후 자릿수
	char cno[512]; //변환한 값의 각 자리의 숫자를 저장하는 문자 배열
	int retry; //한 번 더
	printf("10진수를 기수 변환합니다.\n");
	do {
		printf("변환하는 음이 아닌 정수 : ");
		scanf("%du", &no);
		do {
			printf("어떤 진수로 변환할까요?(2-36) : ");
			scanf("%d", &cd);
		} while (cd < 2 || cd > 36);
		dno = card_convr(no, cd, cno); //no를 cd진수로 변환
		printf("%d진수로는", cd);
		for(int i=dno-1; i>=0; i--) //윗자리부터 차례로 출력
			printf("%c", cno[i]);
		printf("입니다.\n");
		printf("한 번 더 할까요? (1:예, 0:아니오) : ");
		scanf("%d", &retry);
	} while(retry == 1);
}

card_convr 함수의 반환값을 대입 : dno -> 변환한 후의 자릿수

변환한 각 자리의 문자 : cno 배열에 저장

card_convr 함수 : 배열에 역순으로 저장되므로 결과를 출력할 때는 배열 cno를 맨 끝에서부터 역순으로 출력한다.

소수의 나열 > 정수 이하의 소수를 모두 나열하는 알고리즘

소수 : 자신과 1 이외의 정수로 나누어떨어지지 않는 정수 > 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않아야 한다.
합성수 : 나누어떨어지는 정수가 하나 이상 존재

1000 이하의 소수를 나열하는 알고리즘

n의 값을 2부터 시작하여 1000이 될 때까지 1씩 증가해 그 값이 소수인지 판별한다.
변수 i : 2부터 n-1까지 증가해 n과 나누었을 때 0으로 나누어 떨어진다면, break문을 통해 반복문에서 빠져나온다. 나누어 떨어지지 않는다면 소수라는 뜻이므로 출력한다.

→ 문제점 : n이 2 또는 3으로 나누어떨어지지 않으면 2x2인 4, 2x3인 6으로도 나누어떨어지지 않는다. 즉, 불필요한 나눗셈이 실행되고 있어 메모리를 낭비한다.

> 정수 n이 소수인지의 여부 : "2부터 n-1까지의 어떤 소수로도 떨어지지 않는다" 만족하면 된다.

알고리즘 개선 (1)

소수를 구하는 과정에서 이때까지 구한 소수를 배열 prime의 요소로 저장한다.
이때 n이 소수인지 판단할 때 쌓아 놓은 소수(prime)로 나눗셈을 한다.
3 이상의 소수는 이중 for문으로 구한다.
- 바깥 for문 : n의 값을 2씩 증가하여 홀 수 값만 생성 (4이상의 짝수는 2로 나누어 떨어져 소수가 아니기 때문)
- 안쪽 for문 : i값을 1부터 시작하여 ptr -1 회 반복
- * ptr : 소수 개수

> 이렇게 수정하면 나눗셈을 수행하는 횟수가 훨씬 감소한다.

알고리즘 개선 (2)

ex) 100의 약수를 그림으로 나타내면(넓이 : 100) 소수들은 정사각현 10x10을 중심으로 대칭 형태를 이룬다.
정사각형 한 변의 길이까지만 소수로 나눗셈을 시도하고, 그 과정에서 한 번도 나누어떨어지지 않으면 소수라고 판단한다.
> 제곱근을 한 변으로 하는 직사각형은 계산량을 줄일 수 있다.

즉, 어떤 정수 n은 다음 조건을 만족하면 소수라고 판단할 수 있다 > n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는다.

2와 3은 먼저 넣어두고, 5부터 홀수만 반복한다.
flag를 0으로 넣어둔다.
안쪽 for문 : i는 1부터 prime[i]의 제곱근이 n보다 작거나 같을 때까지 반복한다.
1. 만약 n이 prime[i]와 나누어떨어진다면 소수가 아니므로 flag를 1로 바꾼다.
flag가 0이라면 소수라는 뜻이므로 prime에 n값을 넣는다.

* for문에서 제어식에 쉼표 연산자를 사용하여 2개의 식을 평가할 수 있다.

여기서 for문의 반복을 계속할지는 두번째(오른쪽) 피연산자가 성립하는지의 여부에 따라달려있다.

다차원 배열 (2차원 이상의 배열)

배열을 요소로 하는 배열 만들기
배열을 자료형 > 2차원 배열
2차원 배열을 자료형으로 > 3차원 배열

2차원 배열 만드는 과정

n개의 int형을 모아 1차원 배열 만들기
m개의 1차원 배열을 모아 2차원 배열 만들기

각각의 자료형

n : int형
int[n] : int를 자료형으로 하는 단일 요소가 n개인 배열
int[m][n] : int를 자료형으로 하는 단일 요소가 n개인 배열을 자료형으로 하는 요소 개수가 m개인 배열

→ 이때 n이 열, m이 행이 된다.

다차원 배열의 선언은 가장 마지막으로 모은 요소 개수(행)를 맨 앞쪽에 놓는다.

마지막 구성 요소 : 값 - 1

다차원 배열 초기화

초기화 개수로 요소 개수를 알 수 있는 경우 > 맨 앞쪽 요소 개수 생략 가능 (1차원 배열과 동일)
초기화에 없는 요소는 0으로 초기화된다.

행우선

행 번호 고정
같은 행 안에서 열 변호 변화

열 우선

열 번호 고정
같은 열 안에서 행 번호 변화

한 해의 지난 날 수를 계산하는 프로그램 > 년, 월, 일 3개의 값이 주어지면 해당하는 연도의 지난 날 수를 구하는 프로그램

* 2월 : 평년은 28일, 윤년은 29일
* 윤년 계산 : 4의 배수 가운데 100의 배수를 제외하고 제외한 100의 배수 가운데 400의 배수를 다시 포함시킨다.
알고리즘 p86-87

2-2 구조체

구조체

임의의 데이터를 다시 조합하여 만드는 자료구조
임의의 자료형의 요소를 조합하여 다시 만든 자료구조

구조체 선언

구조체 태그 : struct 다음의 붙는 구조체 이름
구조체 멤버 : 구조체를 구성하는 요소
구조체 내용물 : int형 (x), long형(y), double형(z)

struct xyz {   //구조체 xyz
  int x;
  long y;
  double z;
};

struct xyz a;   //struct xyz형을 갖는 객체 a 정의

struct xyz *p = &a;  //a를 가리키는 포인터

구조체 접근

구조체의 객체 안 멤버는 . 연산자를 사용해 객체이름.멤버이름으로 접근한다.
p가 struct xyz형에 대한 포인터일 때 p가 가리키는 객체의 멤버에 접근하는 형식 : 포인터이름→멤버이름(p가 가리키는 객체 안의 멤버

typedef

구조체는 태그 이름만을 구조체 자료형의 이름으로 지정할 수 없다.
구조체 자료형의 이름은 struct xyz처럼 두 단어로 구성해야 한다. > 짧게 줄여서 쓰려면 typedef를쓰면 된다.

typedef struct xyz XYZ;  //struct xyz = XYZ

간단하게 정의, 선언 가능
XYZ a; //XYZ형 (struct xyz형)의 a
XYZ *p = &a;  //a를 가리키는 XYZ 포인터형(즉, struct xyz 포인터)의 포인터 p

구조체 사용 예제

typedef struct {
	char name[20];
    int height;
    double vision;
} PhysCheck;

PhysCheck A[];
A[i].name/height/vision; //접근

//main함수
PhysCheck x[] = {
	{"이름",키,시력},
    {"이름",키,시력},
    {"이름",키,시력}
};

//배열 x의 요소 개수 구하기
sizeof(x)/sizeof(x[0])

저작자표시 비영리 변경금지

'Algorithm' 카테고리의 다른 글

[백준] 10989 (수 정렬하기3) c언어 (0)	2022.09.21
[백준] 25304 (영수증) c언어 (0)	2022.08.12
[백준] 3003 (킹, 퀸, 룩, 비숍, 나이트, 폰) C언어 (0)	2022.08.09
01. 기본 알고리즘 (0)	2022.08.05
자료구조와 함께 배우는 알고리즘 (1) (0)	2022.08.05

'Algorithm' Related Articles

촉촉한초코칩

02. 기본 자료구조 본문

02. 기본 자료구조

'Algorithm' 카테고리의 다른 글

티스토리툴바