구현 소스

실행 화면

예제소스

원하는 만큼의 데이터를 입력받고 출력

#include stdio.h
#include stdlib.h
#include conio.h

void main() {
	int i, input;
	int *arr;
	printf("몇개의 숫자 데이터를 입력하실건가요? : ");
	scanf("%d", &input);
	arr = (int *)malloc(sizeof(int)*input);	//입력받은 n만큼 동적할당

	printf("차례대로 입력하세요.\n");
	for (i = 0; i < input; i++)
	{
		scanf("%d", &arr[i]);
	}

	printf("입력된 데이터는 ");
	for (i = 0; i < input; i++)
        {
		printf("%d ", arr[i]);
	}
	printf("입니다\n");
	getch();
}

실행화면

동적할당이란?

 우선 c언어에서는 메모리 할당 방식의 종류가 2가지로 나뉘는데 한가지는 정적인 방식과 동적인 방식으로 나뉜다.

ㆍ정적인 방식 : 프로그램 실행 전 변수의 저장공간을 먼저 할당 후 프로그램 종료시 해제.

Ex) int a[10] = 0;

ㆍ동적인 방식 : 프로그램 실행 중 필요한만큼의 메모리를 할당 후 원할때 해제.

  동적할당은 상당이 많은 상황에서 꼭 필요합니다. 예를 들어 영어이름을 저장하는 char배열을 만든다고 가정할때 char 배열의 크기를 얼마나 크게 잡아야 할까? 대충 15글자로 정했다고 하면 아래와 같이 배열을 만들것이다.

char name[15];

□ □ □ □ □ □ □ □ □ □ □ □ □ □ □

그렇다면 만약에 name에다가Hong Gil dong 이라는 이름을 넣으면 name

 이라는 배열에 총 13글자가 들어간다. 

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ □

하지만 이 배열의 크기는 15인데 13만들어가면 2라는 크기의 메모리가 낭비된다.

그리고 만약에 Hong Myeong seong 이라는 이름을 넣으면 이 배열에

17글자가 들어간다. 즉 15라는 배열의 크기를 초과했다.

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

이처럼 오버플로우 위험 또한 생긴다.

그래서 이럴때 사용하는 것이 동적할당이다.

▶동적할당의 사용방법

 malloc 함수로 동적할당함. (C 언어의 표준 라이브러리로 stdlib.h에 정의)

▶malloc함수

예를 들어 malloc(4)를 하면 4byte 만큼의 메모리를 할당받는다.

사용의 예를 들어보자면 다음과 같다.

Ex) int *i = (int*) malloc (sizeof(int));

위와 같이 i라는 포인터 변수를 선언하고 i값에다가 메모리를 할당하는 것이다.

sizeof(int)는 4와 같으니 malloc함수에 4byte의 메모리를 할당 받고 int 형으로 바꾸어 주는 것이다.

만약에 malloc(sizeof(int))는 그대로 하고 앞에 int*을 int형이 아니라 short형으로 바꾼다면 i라는 변수는 short형의크기의 배열 2개가 선언됩니다.

예를들어 input을 받아 input 만큼 배열의 크기를 할당받고 싶다면

int *arr = (int*) malloc(sizeof(int)*input);

이런식으로 하면 된다.

▶free함수

할당된 메모리를 해제하는 함수이다.

메모리를 할당 받고 메모리가 해제되지 않으면 할당받은 메모리는 사용이 끝났음에도 불구하고 컴퓨터가 종료되기 전까직 해당 메모리를 차지하게 된다.

따라서 메모리를 할당만 하고 해제를 안하면 언젠가는 메모리가 부족해지는 현상이 발생하게된다. 때문에 동적할당 후 더 사용할 이상 필요가 없다면 꼭 free함수로 메모리를 해제 시켜주어야 한다.

다음 같이 메모리를 할당을 해주었으면 

int *arr = (int*) malloc(sizeof(int)*input);

마지막에는 꼭 다음과 같이 메모리를 꼭 해제 시켜 주어야 한다.

 free(arr_2); 

동적할당의 장점과 단점

-장점 : 상황에 따라 원하는 크기만큼의 메모리가 할당되므로 경제적이며, 이미 할당된 메모리라도 언제든지 크기를 조절할 수 있다.

-단점 : 더 이상 사용하지 않을 때 명시적으로 메모리를 해제해 주어야 한다.

큐(Queue)란?

 큐는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과는 달리 리스트의 한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화된 리스트. 가장 먼저 리스트에 삽입된 원소가 가장 먼저 삭제되므로 선입 선출(先入先出)인 FIFO(first in first out) 리스트라고 한다.

[그림 7-28] 큐 구조

ㆍ한쪽에서는 입력만 다른 한쪽에서는 출력만 가능함.(입구와 출구가 다름)

ㆍ먼저 입력한값이 먼저 출력 → First Input First Out  → FIFO 라고불림

 구현 소스

스택(Stack)이란?

 스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조(linear data structure)로서, 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다. 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것을 pop이라 한다.

ㆍTop이라고 불리는 한쪽 끝에서만 삽입 삭제가 행해짐.(입구와 출구가 같음)

ㆍ나중에 입력한값이 가장 먼저 출력 → Last Input First Out  → LIFO 라고불림

 구현 소스

Stack보고서.hwp

▶2차원 배열이란?

 2차원 배열은 이전에 배웠던 배열의 확장이다.

이전에 배웠던 배열이 

int arr[1]; 

이라면 오늘 배울 2차원 배열은 위 배열에서 아래와 같이조금 확장한 것이다.

int arr[1][2];

이처럼 이전에 배운 배열은 1차원 배열이라고 하고 오늘 배울 배열은 2차원 배열이라고 한다.

차이점은 index가 하나 늘어난것과 저장공간이 많아졌다는것 뿐이다. 아래의 사진을 보면 이해가 쉬울것이다.

[그림 7-5] 2차원 배열의 표현

▶2차원 배열의 선언과 저장

자료형 변수명[열][행]

예)int arr1[2][2]; char arr2[4][3];

     0  1 2              0 1  2  3  4 

  0 □ □ □          0 □ □ □ □ □

  1 □ □ □          1 □ □ □ □ □

  2 □ □ □          2 □ □ □ □ □

arr1              arr2 

위와 같이 각 배열에 행(가로 한줄)과 열(세로 한줄)이 생긴다. 

▶2차원 배열의 값 대입

배열이 

int arr[1][2]; 와 같을때 아래의 그림처럼 나온다

배열이란 간단하게 말하면 변수들을 

한 데 묶어 둔것이다. 

▶그렇다면 배열이란 것을  왜 사용 할까?

그 이유는 배열이 없다면 변수를 선언할때  

int a1, a2, a3, a4, a5, a6, a7, … 

이런식으로 매우 귀찮아지죠. 하지만 배열을 사용하면

예) int a[10];

이렇게 데이터마다 변수 이름을 따로 두지 않으므로 처리가 훨씬 수월하며. 또한 활용도도 아주 높다는 장점이 있다.

▶배열의 선언은 어떻게 할까?

자료형 변수명[갯수]

예)int arr1[100]; char arr2[10]; 

▶배열은 어떻게 저장 될까?

배열의 저장을 비유하자면 연속적으로 놓여있는 빈 박스와 비슷하다.

다음과 같이 배열을 선언하면

int a[10]; 

□ □ □ □ □ □ □ □ □ □

0  1  2  3  4  5  6  7  8  9

다음과 같은 a라는 빈 박스 10개가 뙇 하고 생기는 것과 같다.

박스 아래에 있는 번호는 Index라고 하는데 이는 몇번째 박스인지 나타내는 번호와 같다. 

이는 Index가 0번째 부터 시작 해서 9까직 총 10개의 빈 박스가 있는것이다.(1부터 시작하는게 아니란건 주의해야한다.)

예를 들면 a[2] 는 a라는 박스들중 3번째 박스를 가르킨다.

이제 어떻게 저장되는지 알았다면 이제 이 박스 안에다가 값을 넣어보자. 

▶배열에다가 값을 어떻게 넣을까?

int a[10]; 

□ □ □ □ □ □ □ □ □ □

0  1  2  3  4  5  6  7  8  9

여기서 만약에 내가 3번째 박스에다가 5라는 값을 넣고 싶으면 a[3] = 5; 만 해주면 된다. 

그럼 모든 박스에 값을 다 넣어주자.

a[0] = 5;

a[1] = 5;

a[2] = 5;

a[3] = 5;

a[4] = 5;

… 

그렇다 미친짓이다. 그렇다면 이짓을 어떻게 쉽고 간단하게 할 수있을까?

바로  for문이다

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

a[i] = 5;

} 

이렇게 for문으로 i값을 증가시켜주고 a배열의 인덱스에 i값을 넣어주면 상당히 효율적으로 배열에다가 값을 넣을 수가 있다.

또한 처음에 배열을 선언할때도 다음과 같이 값을 넣을 수 있다.

예)int arr1[5]= {9, 4, 5, 7, 1};

           ⑨  ④  ⑤  ⑦  ①

 0   1   2   3   4

그러므로 이 짱짱 좋은 배열을 효과적으로 잘 사용해보자.

이진 탐색이란?

이진 탐색(binary search)이라는 말 그대로 탐색하는 방법중 하나인데 순차 탐색과는 다르게 정렬된 데이터 집합을 이분화하면서 탐색하는 것이다.

예를들면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우가 있다.

[그림 8-5]의 정렬된 데이터 집합에서 이진 탐색을 이용해 데이터 15를 탐색하는 과정을 살펴보자.

[그림 8-5] 이진 탐색을 위한 데이터 집합

① 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다.

② 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

③ 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다.

④ 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

⑤ 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 같은지 비교한다. 원하는 데이터이므로 탐색을 종료한다.

내가짜본

이진탐색 소스(c언어)

이진탐색의 장점과 단점

-장점 : 이진탐색 방법은 순차탐색처럼 하나하나 일일히 값을 확인하지 않고 효과적으로 원하는 값을 찾아낼 수 있다.

-단점 : 배열이 반듯히 정렬되어 있어야 한다는 제약이있다.

포인터란?

포인터는 포인터 변수를 줄여서 말하는 걸로 영어 단어(pointer)그대로 무엇을 가르킨다는 뜻입니다. 

포인터 변수란 일반적인 변수를 저장하는 것이 아니라 해당변수가 들어있는 주소의 값을 저장 하는 것을 말한다.예를 들어 일반변수는 a라는 이름으로 100을 저장한다고 하는 반면 포인터 변수는 a라는 변수가 메모리에 위치하는 주소를 알려주는 것이다.

포인터의 선언방법

포인터의 선언은 간단하다. 선언 할 때 변수이름 앞에 * 기호를 넣어 주는게 전부이다.

-인반 변수 : 타임 변수의 이름

-포인터 변수 : 타입 *포인터의 이름

예)일반변수 : int a; , 포인터 변수 : int *input;

포인터를 선언하기만 하면 그 안에는 아무의미도 없는 쓰레기 값이 들어가게 된다. 

그래서 포인터 변수에다가 변수의 주소를 지정 해주어야한다. 변수의 주소를 지정 하는 방법은 지정할 변수 앞에다가 & 기호를 넣어주면 된다.

포인터 변수에 값 넣기 : 포인터 변수 = &변수

예)input = &a;

백문이 불여일견 이라고 그림으로 나타내면 이러하다.

-a의 값 : 3

-a의 주소 값 : 4832

-*p의 값 : 3

-p의 값 : 4832

포인터를 쓰는이유& 활용도

포인터를 사용함으로써 복사본을 만들지 않고 주소만 알려줌으로써 용량 및 처리시간에서 이득을 볼 수 있습니다.

그래서 메모리가 한정적이거나 처리시간이 중요한 시스템에서 사용할 경우 도움이 됩니다.

-예를들어 배열을 선언할때 배열이 a[100000]와 같이 거대한 량의 자료를 저장할때 포인터를 사용 하여 필요한 만큼의 배열의 량을 받아서 메모리를 비효율적으로 안써도 되게 합니다.