클래스 정의와 관련된 예제 문제입니다.

3_활동지_클래스정의_without_답.pptx

Nested if 조건문에 대해서 설명합니다.

if-else if 조건문에 대해서 설명합니다.

if-else 조건문에 대해서 설명합니다.

Casting의 개념과 연산자 우선순위에 대해서 설명합니다.

Assignment 연산자와 conditional assignment 연산자에 대해서 설명합니다.

Bit shift 연산자에 대해서 설명합니다.

Singly Linked List (SLL)의 구현, delete함수에 대해서 설명합니다.

Singly Linked List(SLL)구현 destroy와 insert함수에 대해서 설명합니다.

Singly Linked List구현, Add 함수에 대해서 설명합니다.

SLL 노드 정의에 대해서 설명합니다.

선형리스트의 구현

ㅇ 선형리스트는 배열을 이용하면 쉽게 구현이 가능하지만,

  - 배열이 가지는 한계 때문에 부적절

ㅇ 배열의 단점

  - 미리 정해진 크기를 넘어갈 경우 변경이 쉽지 않다.

  - 공간 낭비가 발생할 수 있다.

  - 중간에 새로운 요소를 넣기가 어렵다.

ㅇ 배열의 단점은 Singly linked list (SLL)로 보완

  - 데이터의 크기를 미리 알 수 없어도 사용가능

  - 공간 낭비가 없다.

  - 중간에 새로운 요소 삽입이 쉽다.  

ㅇ SLL의 구조

  - 개별 노드들을 줄로 이은 형태

  - 필요할 때마다 새로운 노드를 추가

  - 중간의 노드를 삭제하려면, 노드 제거후 줄 잇기만 다시 하면 ok

ㅇ SLL 노드의 구현

  - self-referencing structure를 이용

  - 예를 들어, 정수를 저장하는 SLL를 만들 경우,

  - 노드의 C언어 정의는

ㅇ 비디오 

  - Singly Linked List의 구현 전반에 대해서 설명합니다.

선형리스트 (Linked List)에 대해서 설명합니다.

Pointer (포인터)

C언어 프로그래밍 공부를 힘들게 하는 원인 중의 하나다.

개념은 간단하다.

포인터는 주소를 다룬다.

주소란 무엇인가? 

예를 들어보자.

int a;

a = 4;

Integer(정수)형 변수 a를 만들고, 거기에다가 값 4를 저장한다.

이는 변수a를 위해 메모리에 저장공간을 만들고, 

공간 'a'에 값 4를 저장한 것이다.

메모리의 저장공간은 모두 고유의 숫자주소를 가지고 있다.

사람들이 고유의 숫자 주민번호를 가지고 있듯이.

프로그래밍할 때 저장공간을 쉽게 기억하기 위해 'a'라는 이름을 쓰지만

사실은 'a'도 숫자 주소를 가지고 있다.

'a'의 주소를 알고 싶다고?

printf ("%d", &a);

&a는 a와 매칭된 메모리 저장공간의 주소를 의미한다.

어느 변수든지 기호 &를 앞에 붙이면 해당 저장공간의 주소가 된다.

주소를 다루기 위해 포인터라는 것을 만들었다.

포인터는 주소를 저장할 수 있도록 한다.

int *b;

포인터를 만드는 방법은 변수이름 앞에 기호 *를 붙이면 된다.

이제 변수 b에 저장되는 값은 주소로 인식된다.

100을 저장한다. 주소 100번지가 된다.

1000을 저장한다. 주소 1000번지가 된다.

b = &a;

b에 변수 a에 매칭된 저장공간의 주소를 저장하는 것이다.

왜? 굳이 포인터라는 걸 만들었나?

포인터를 통해 복잡한 일을 쉽게 하기 위해서다.

어떤 복잡한 일인가?

'주소 000번지에 가서, 그 번지에 저장되어 있는 값을 읽거나 쓰는 일이다.'

b = 100; 

변수 b는 주소 100번지를 저장한다.

printf ("%d", *b);

변수 b가 저장한 값 100을 주소로 인식하고, 그 100번지에 저장되어 있는 값을 읽어오는 것이다.

포인터 변수 앞에 기호 *를 쓰면, 그 번지에 저장된 값을 읽거나 쓸 수 있다.

단, 헷갈리지 말자.

int *b; 이건 변수 b가 포인터라는 것을 정의하는 것이다. 

포인터 변수를 만들 때도 기호 *를 사용한다.

*b = 10;

변수 b가 저장한 값 100을 주소로 인식하고, 그 100번지에 값 10을 쓰는 것이다.

기호 *을 붙여 값을 쓰는 용도로 사용한 것이다.

배운 것을 정리해보자.

1. a = 10;

2. b = &a;

3. *b = 20;

4. printf ("%d", a);

라인 1. 변수 a에 값 10을 저장한다.

라인 2. 변수 a에 매칭된 저장공간의 주소를 b에 저장한다.

라인 3. b에 저장된 주소는 a것이므로, a에다가 20을 저장한다.

라인 4. 위에서 a에 저장된 값이 20으로 바뀌었으므로 10이 아닌, 20을 출력한다.

포인터는 어디에 필요한가?

컴퓨터를 생각해보자.

키보드, 디스크, 비디오카드, USB메모리, CPU 등 여러 가지 장치들이 있다.

프로그램으로 이 장치 들에게 명령을 내리고 싶다면, 어떻게 할 수 있을까?

각 장치들은 고유의 주소를 가지고 있다.

이 주소들을 이용하여 명령을 내릴 수 있다.

예를 들어, 비디오카드가 100번지에 있다면, 100번지에 값을 읽거나, 써서 비디오카드에게 명령한다.

이를 가능하게 하는 것이 포인터다.

따라서 포인터를 아는 것은 시스템을 내 휘하에 두고 이러저러 명령을 내릴 수 있는 힘을 얻는 것이나 마찬가지다. 

int *a

포인터 변수를 선언한 것이다.

하나하나 뜯어서 살펴보자.

a는 포인터 변수의 이름이다.

*: a 앞에 붙은 기호 *은 변수 a가 포인터임을 나타낸다. 기호 *이 없으면 포인터가 아니다.

int: 이것의 의미를 잘 이해해야 한다. 포인터 변수 a를 이용하면 어떤 주소 위치에 값을 쓸 수도 있고, 읽어올 수도 있다. 이 때 그 값의 형(type)을 나타낸다. 즉 변수 a를 이용하면 읽거나 쓰는 값은 int이고, 따라서 4바이트 단위로 읽거나 쓸 수 있게 된다. (32비트 운영체제일 경우에 말이다. 64비트 운영체제이고 int가 64비트이면 8 바이트 단위로 동작한다.)

int **a

포인터 변수이긴 하다.

여기에는 기호 *이 두 개가 붙었다.

이중 포인터라는 것이다.

이것의 의미도 하나하나 뜯어보자.

a: 포인터 변수의 이름이다.

* (오른쪽에서 첫 번째): 변수 a가 포인터임을 나타낸다.

int * (오른쪽에서 두 번째 *): 변수 a를 이용하여 읽고 쓸 수 있는 값의 데이터 형이 int *, 즉 정수 포인터

예제프로그램

변수 a를 만들고, 거기에다가 10을 넣었다.

포인터 변수 b를 선언했다.

포인터 변수 c를 선언했다.

b를 이용해서는 int값을 읽고 쓸 수 있으므로, b에는 변수 a의 주소를 넣는다.

c를 이용해서는 int *값을 읽고 쓰기 때문에, c에는 int 포인터 변수 b의 주소를 넣는다.

출력결과는 모두 10, 10, 10

첫 번째 10: 변수 a의 값을 출력한 것

두 번째 10: 포인터 변수 b를 이용하여, a의 주소를 이용해서 int값을 읽어서 출력했다.

세 번째 10: 이중 포인터 변수 c를 이용했다. **c == *(*c)로 이해하면 쉽다. *c는 b에 저장된 a의 주소를 읽는다. *(*c)는 a의 주소를 이용하여 a에 저장된 값을 읽는다.

malloc

메모리를 할당받는 데 사용하는 함수이다.

원하는 크기의 메모리 공간을 할당받을 수 있다.

이 함수의 인자는 할당받기를 원하는 크기이다.

크기는 바이트 단위이다.

malloc(100) : 100 바이트 크기의 공간할당을 요청하는 것이다.

이 함수의 반환값은 주소이다.

할당된 공간의 시작주소이다.

반환값이 주소이므로 이 주소는 포인터 변수에 저장해야 한다.

malloc casting

malloc함수의 원형은 아래와 같이 생겼다.

반환형이 독특하게 생겼다.

void *

생긴 것을 봐서는 포인터이다. 

왜냐면 *이 붙었으니까.

이것으로부터 유추해보면, 포인터 즉 주소값을 반환한다는 뜻이다.

좀 더 추리해보면, 할당받은 공간과 관련된 주소일 것이다.

정확하게 말하자면, 할당받은 공간의 시작주소가 반환값이 된다.

그러면 void는 무슨 뜻인가?

void의 사전적인 의미는 '비어있는' '없는' '무효' 이다.

데이터 형이 없다는 뜻으로 생각하면 된다.

왜 void, 데이터형을 없는 것으로 해 놨을까?

그건 공간을 마음대로 활용할 수 있도록 해 주기 위해서이다.

공간에 int 값을 쓰거나 읽을 용도로 할당받는 경우도 있고,

char 값 용도로 쓸때도 있다.

그러니 데이터형을 일단 없다고 하고, 

실제로 할당받는 순간에 그 형을 정해서 쓰기 위해서 void로 해 놓은 것이다.

공간을 할당받는 순간에 데이터형을 결정하다. casting

int *k;

k = (int *)malloc(100);

char *m;

m = (char *)malloc(100);

둘 다 100 바이트 공간을 할당받는다.

하지만 위의 것은 int형 값들을 읽고 쓰는 공간으로 만들기 위해 (int *)로 캐스팅한다.

아래는 char형 값을 위한 것이다.

할당받은 공간에 값을 저장해보자.

*k = 1;

값 1을 쓰는 것이다.

int형 1을 쓰는 것이다.

int형은 4바이트이므로,

할당받은 공간 100바이트 중 4바이트에다가 1을 쓰는 것이다.

*m = 1;

역시 값 1을 쓰는 것이다.

하지만 이번에는 char형 1을 쓰는 것이다.

char형은 1바이트이므로,

1바이트에다가 1을 쓰는 것이다.

free

컴퓨터의 메모리공간은 유한한다.

malloc으로 할당받은 공간을 다 썼으면 반환해야 한다.

이 때 사용하는 함수가 free이다.

이 함수는 인자로 반환하고자 하는 공간의 시작주소를 받는다.

malloc했을 때 할당받은 공간의 시작주소를 얻을 수 있으니,

이것을 잘 간직해 두었다고,

free할 때 쓰면된다.

free(k);

free(m);

k와 m은 각각 할당받은 공간의 시작주소를 가지고 있으니,

이렇게 하면 되는 것이다.

free를 안하면 어떻게 될까?

메모리 공간이 모자르니 다른 프로그램이 손해를 떠안아야 한다.

프로그램이 아예 실행이 안 될 수도 있고,

실행되는 도중에 '더 이상 메모리를 얻을 수 없습니다.'하고,

중간에 종료되기도 한다.

그러니 malloc으로 할당받은 공간 중에 필요없게 된 것들은

그 때 그 때 free해서 반환하는 것이 에티켓이다.

프로그램 종료는 자동 free된다.

프로그램이 끝나면,

수행되면서 할당받았던 공간들이 자동 반환된다.

그러니, 종료되고 나서, '아차, free 안했네' 걱정할 필요없다. 

구조체 (Struct)

C언어에서 구조체를 이용하면,

데이터형이 다른 여러 데이터를 묶어서

새로운 데이터형을 만들 수 있다.

예를들어, 

int와 char 데이터를 하나씩 묶어서

새로운 데이터 타입을 만드는 것은

아래와 같이 할 수 있다.

이렇게 하면, 

새로운 데이터형 struct A가

생겨나게 된다.

이를 사용하는 방법은 다음과 같다.

sturct A가 데이터형이므로,

x는 struct A형의 변수가 된다.

그리고,

x 안에는 int를 저장하는 a가 있고,

또 char를 저장하는 c가 있는 것이다.

따라서,

각각을 x.a와 x.c로 부르고,

그곳에 값을 넣거나, 읽는 것은 일반 변수와 

똑같이 하면 된다.

구조체변수 대입( Assignment)

여기까지는 일반적인

구조체 정의와 사용법에 대한 얘기이니

별로 새롭지는 않다.

그런데, 아래 프로그램은 조금 생소할 수도 있다.

line 11:

구조체 변수 m과 n을 만들었다.

line 12-13.

m에 데이터를 채워넣는다. n에는 아무 것도 안 들어간 상태이다

line 14:

m을 그대로 n에 대입하면, 구조체 속의 a는 a로, 

c는 c로 자동 대입된다.

line 15:

대입된 결과를 n을 출력해 봄으로써 알 수 있다.

구조체변수 비교 (Comparison): 이건 불가능

대입(assignment)는 당연하게 느껴지겠지만,

비교도 당연히 되리라고 생각해서는 안된다.

아래 프로그램을 보자.

구조체 변수 m과 n이 서로 같은지 

line 16에서 비교하려고 하고 있다.

그런데, 컴파일 과정에서 "이러시면 안됩니다."하고 오류 메시지가 발생한다.

구조체변수끼리의 비교를 하려면,

멤버변수 별로 해야 한다.

아래 프로그램처럼 말이다.

line 16을 보면

구조체 변수 n과 m이 서로 같은지를 비교하기 위해

멤버 a는 a끼리,

멤버 c는 c끼리 비교하고 있다.

자기참조 구조체 (Self Referential Struct)

이것이 무엇인고,

말도 안되는 거 하나를 보자.

무엇이 이상한가 하면,

struct A를 정의하고 있는데,

그 안에 자기자신을 포함하고 있다.

아직 자기자신이 다 생기지도 않았는데, 

자기자신이 그 안에 들어있으면,

어쩌라는 말이냐,, 이건 마치 무한 recursion과 같은 일이다.

결론부터 말하면, 이런 구조체는 생길 수가 없다.

그런데,,,

,,,

,,, 기대하시라,,

이런 건 가능하다.

무엇이 달라졌는가?

자기자신을 포함하는 대신에,

자기자신처럼 생긴 것에 대한 주소를 저장하고 있다.

즉,

변수 a는 포인터다.

struct A 타입의 데이터가 저장된 곳의 주소를 저장하는 포인터 변수이다.

갑자기 철학적 질문이 된다.

나는 나를 품지 못하되,

나처럼 생긴 애가 어디있는지 가리키는 손가락은 가질 수 있구나.

이런 것을 소위

자기참조 구조체 (Self referential struct)라고 한다.

이것은 앞으로 데이터구조에서

아주 많이 사용되니 개념을 잘 이해하고 넘어가야 한다.

혹시 이해에 도움이 될까 싶어,

발로 그린 그림이지만, 올려본다.

포인터 변수 a가 다른 struct A형의 데이터의 주소를 가리키는 것을 보여준다.

구조체에 대해서 설명합니다.

배열 (Array)에 대한 복습

데이터구조에서 

배열을 많이 사용하기 때문에

이쯤에서 한 번쯤

복습해 보는 것이 좋겠다.

배열은,

같은 데이터형 (data type)을 갖는 

여러 개의 변수들을 손 쉽게 만들 수 있는 방법이다.

배열을 선언할 때는

맨 앞에 데이터형을 쓰고,; 위에서는 int

그 다음에 그 배열의 이름을 붙이고; 위에서는 a

마지막에 몇 개를 만들 것인가를 [ ] 안에 지정한다.; 위에서는 6개

이 때 생기는 6개 배열변수들의

이름은 아래와 같다.

이렇게 번호를 이름삼아 부르는 데, 이 번호를 index 라고 한다.

index는 0부터 시작

이걸 절대 잊지 말아야 한다.

사람들이 물건을 셀 때는

첫 번째, 두 번째, ... 이렇게 1을 기준으로 하지만,

C언어에서는

0  번째, 1 번째,... 이렇게 0이 기준이 된다.

index는 n-1에서 끝

이것도 절대 잊지 말아야 한다.

배열 크기가 n일 때,

마지막 index는 당연히 n-1이 된다.

왜냐면, 0부터 시작했으니.

배열 (Array) 해부

배열은 메모리 상의 연속된 공간에 위치하게 된다.

쉽게 얘기하면,

크기 n인 배열을 선언하면,

n개의 배열변수들이

메모리 상의 연속된 위치에 생기게 된다는 것이다.

서로 서로 떨어질 수가 없다.

일심동체인 것이다.

아래 프로그램을 보자.

크기 6인 int 배열을 만들고,

각 배열변수들의 주소를 출력해보면

'4' 바이트 간격으로 모두 연속된 것을 볼 수 있다.

예를 들어,

a[0]는 16진수 주소 279138에 있고, 4 바이트를 차지한다. 왜냐면 int니까.

그러면

a[1]은 16진수 주소 27913c부터 시작한다. 이런 식이다.

이번에는 char배열을 예로 프로그램을 보자

크기 6인 char배열을 만들었고,

각 배열변수의 주소를 이번에는 10진수로 출력해 보았다. 

1바이트 단위로 증가하는 것을 볼 수 있다.

왜냐면, char가 1바이트이니까.

정리하자면,

배열을 선언하면, 각 배열변수들은 연속된 메모리 공간에 위치한다.

바꿔 말하면,

배열은 메모리에 그 만한 연속공간이 있을 때만 만들 수 있다. 

다차원 배열 (Multi-dimensional Array)

2차원 배열을 생각해보면

다차원 배열이 뭔지 금방 알 수 있다.

2차원 배열은 지도를 떠올리면 금방 이해된다.

또는 지뢰찾기 같은거,,,

2차원 배열은 행과 열 개수만큼의 공간이 만들어진다.

예를 들어, 2x2 배열이면 모두 4개의 배열변수가 만들어진다.

이 때도 index는 0부터 시작이다.

그리고 각 배열변수의 이름은 

두 개 index의 조합으로 나타내어 진다.

3차원 배열

이거는 큐브를 생각하면 된다.

그리고,

3차원 배열은 x, y, z축으로 이루어진 공간을

생각하면 되는데,

예를 들어, 2x2x2 배열이면 모두 8 개의 배열변수가

만들어지고,

배열변수는 3개 index의 조합으로 이름이 지어진다.

다차원배열의 비밀

2차원 배열이면 메모리 상에 2차원으로 생길 줄 알았지?

3차원 배열이면 메모리 상에 3차원이 만들어 지고,,

그러면 4차원은 어떻게 하려고,,

다차원 배열은 

다 뻥이다.

몇 차원이고 간에

메모리상에는 1차원 배열처럼 생긴다.

증명이 필요하다구? 

아래 프로그램을 보자.

3차원 배열 a[2][2][2]를 만들었다.

만약, 이게 진짜로 3차원이면,

주소가 연속이면 안되고, 위층, 아래층 이렇게 나와야 한다.

그런데,

결과를 보면 모두 1바이트 단위로 인접해 있음을 알 수 있다.

다차원 배열, 다 소용없는기라.

그기 다 사기인기라.

결국 1차원 짜릴, 그리 뻥치고 다닌기라.

배열에 대해서 설명합니다.

Fibonacci 수열 계산하기.

Fibonacci 수열은 무엇인가?

대충 이름은 들어봐서 알 것이다.

숫자들을 늘어 놓은 것이니 수열일테고,

다만, 숫자들 사이에 특수한 관계가 있는 것인데,

어떤 숫자든 자기 앞의 두 개 숫자의 합과 같아야 한다.

이런 조건을 만족시키는 수열이 Fibonacci 수열이다.

잠깐,

Fibonacci 수열의 첫 번째와 두 번째 숫자는 모두 1이라는 것을

기억합시다.

Recursive함수를 이용하여 Fibonacci 수열 계산하기

Fibonacci 수열을 계산하는 것은,

recursion함수를 이용해서

구현하는 것이 

직관적이라서 쉽다.

line 4-14:

Fibonacci 숫자를 구하는 재귀함수이다.

이 때 인수 n의 의미는 "n 번째" 숫자이다.

그래서 

fibo(1)은 첫 번째 Fibonacci 숫자를 의미해서

'1'을 반환해야 한다.

fibo(2)는 두 번째 Fibonacci 숫자이니

'1'을 반환해야 한다.

fibo(3)은 세 번째 Fibonacci 숫자이니,

상식적으로 생각할 때, 

앞에앞에 숫자와 앞에 숫자를 더한 것이니

fibo(3) = fibo(2) + fibo(1)이 된다.

line 6-9:

첫 번째와 두 번째 Fibonacci 숫자인 경우를 처리하는 것으로,

1을 반환한다.

그래서,

이 부분은 재귀함수의 

탈출조건에 해당한다.

line 10-13:

fibo(n) = fibo(n-1) + fibo(n-2)를 구현한 것이다.

이 부분은,

자기 자신을 또 호출하고 있으니,

지속조건에 해당한다.

수행결과는 아래와 같이,

12번째 Fibonacci 숫자는 144임을 보여주고 있다.

Non-recursive방식으로 Fibonacci 수열 계산하기

Recursion함수를 사용하지 않고,

구현하는 non-recursive방법도

생각해 보자.

그리 어렵지는 않지만,

recursion함수 방법보다

더 손이 간다.

main함수는 전혀 변화가 없지만,

함수 fibo ( )가 바뀌었다.

자기자신을 호출하지 않는 형태로..

line 6-9:

첫 번째와 두 번째 Fibonacci 숫자를 처리하는 경우이고,

recursion경우와 똑같다.

line 10-23:

n번째 Fibonacci 숫자를 구하는데,

반복문을 사용한 것이다.

변수를 살펴보면,

beforebefore는 앞에앞에 숫자를 말하고,

before는 앞에 숫자를 의미하고,

me는 현재 숫자를 의미한다.

변수 i는 "몇 번째" 숫자를 구하고 있는지를 표시한다.

line 16-22:

Fibonacci 숫자를 계산하는 무식한 방법이다.

현재 숫자는 앞에앞에 숫자와 앞에 숫자를 더해서 구하고,

다음 번에 반복할 때는,

앞에앞에숫자는 앞에 숫자가 되고,

앞에숫자에는 현재 숫자가 되는 것이고,

이 과정을

원하는 n번째 숫자를 구할 때까지

반복하는 것이다.

하노이탑 (Tower of Hanoi)원반 옮기기

하노이탑 문제란 무엇인가? 

접시 옮기기다. 깨지 말고,,

위 그림에 보면 막대 A에 접시 5개가 있다.

규칙이 있다.

큰 접시위에 작은 접시.

하노이탑 문제는

접시 n개를 막대 C로 옮기는거다.

단, 제약조건은

이게 가능해?!

당근, carrot,

가능하지.

3개를 어떻게 옮기는지 보여줄테다...

이걸 프로그램으로 구현할 수 있다고?!

carrot, too.

어떻게 구현하는지 보여줄테다....

그것도 recursion을 이용해서,,,

이게 실행이 된다고?!

carrot, three.

아래 출력결과를 봐봐.

이걸 따라서 한접시, 한접시 옮겨봐.

코드가 이해가 안되...ㅠㅠ

걱정하지말아요, 그대,

이걸 글로 쓰기는 너무 긴 이야기지만,

아래 동영상을

보면 쉽게 이해가 갈겁니다.

시인 릴케와 Recursion

Recursion을 제대로 이해한다는 것은 어렵다.

불가능하지는 않지만,,,

일단 이해하려고 무지 노력을 해보고,

안되면,

시인 '릴케'의 말을 위안삼자.

아래 동영상에서는

Recursion을 이용한 Fibonacci 수열계산이

어떻게 이루어지는지 "매우 상세히" 설명하고 있으니,

보시면 큰 도움이 됩니다.

그리고, 

하노이탑 알고리즘에 대해서 이해가 쉽게 될 수 있도록 설명하고 있습니다.

Recursion을 이용한 거듭제곱의 계산

재귀함수를 이용해서

거듭제곱을 계산하는 프로그램을 작성해보자.

거듭제곱

이게 무엇인가?

아래와 같은 것을 말한다. 길게 설명할 필요는 없을 것 같다.

우리 말로는 2는 밑, 3은 지수라고 했던 것 같은데,

영어로는 base와 exponent이다.

우리 말로는 '2의 3승' 이라고 읽는데,

영어로는 'two to the third power' 혹은 

간단히 'two to the three'라고 읽는다.

Non-recursive로 거듭제곱 계산하기

거듭제곱을 계산하는 C언어 프로그램을 작성해보자.

for-loop 반복문을 사용하면 아주 쉽게 구현할 수 있다.

Non-recursive 함수로 구현하기

위에서는 main함수 안에서 구현했는데,

별도의 함수로 만들면 활용성이 높다.

그래서,

아래와 같이 구현해 본다.

line 6-15: 

지수승을 계산해서 반환하는 함수 calcPower함수를 정의했다.

두 개의 인수를 받는다.

base와 exponent.

지수승 계산은 단순히 반복문을 이용해서 한다.

Recursive함수로 거듭제곱 계산하기

함수 calcPower( )를 recursion함수로 만들면 된다.

아래와 같이....

line 6:

함수 calcPower의 반환형, 인수에는 변함이 없다.

line 8-11:

recursion함수의 탈출 조건에 해당하는 부분이다.

exponent가 1이 되면, 더 이상 진행하지 않고,

base를 반환하고 끝낸다.

어떤 숫자이든 1승은 자기 자신이므로.

line 12-15:

recursion함수의 지속 조건에 해당하는 부분이다.

base 값에 

을 곱해주기 위해서

자기자신을 호출한다.

단, calcPower(based, exponent-1)을 호출해서,,

Recursive함수기반의 거듭제곱 계산을 개선해보자

개선하려면 문제점이 무엇인지 알아야 한다.

문제점은,

을 예로 들어보자.

이것을 계산하기 위해서는 자기자신 호출이 1000번 일어나야 된다.

이게 문제점이다.

너무 많이 자기자신을 호출한다는 것이다.

호출되는 횟수를 줄일 수는 없을까?

이게 문제점이요, 개선포인트이다.

어떻게 할 수 있을까? 

아래 동영상을 보면, 

그 해답을 알 수 있다.

엄청나게 개선시킬 수 있는 방법이 있다,,

위에서 설명한 내용에 대해 

보다 자상하게, 또박또박 얘기해 주는 동영상입니다.

Recursion: 재귀함수, 순환함수

Recursion함수의 개념

recursion함수는 묘한 매력이 있다.

이걸 사용해서 프로그램을 짜면,

엄청나게 짧게 짜더라도, 놀라운 일을 후딱 해치우기 때문이다.

그런데,

이해하기는 쉽지 않다.

Recursion 함수를 정의하자면 

함수가 내부에서 자기 자신을 호출하는 것이다.

보통은 함수가 다른 함수를 호출하거나,

일을 끝내면 return하는 것이 도리이거늘,

recursion함수는 자기 자신을 호출한다.

헐...

그러면, 이건 도대체 뭘 의미하는가?

혹시,,

이런 경험있으세요,,

밤 늦은 시간에 지친 몸을 이끌고

엘리베이터에 탔다.

혼자였다.

옆에 붙은 거울을 보는데,

그 반대쪽에도 거울이 붙어 있다.

그러면 이런 일이 벌어진다. 거울 속에 내가 있고, 그 안에 내가 있고, 그 속에 내가 또 있다.

이게 끝이 아닌다. 그 속에 내가 있는데, 그 안에 있는 너는 뭐냐? 너지 뭐냐....

Recursion함수는 엘리베이터 거울에 비친 내모습 같은 것이다.

다만,

엘리베이터 거울은 무한대이지만,

recursion함수는 유한하게 만들 수 있다.

물론

무한한 recursion함수도 만들 수 있지만,

컴퓨터 메모리의 한계로 어느 정도 하다보면 프로그램이 종료된다.

Factorial 계산

이건 뭐지, 

n이 놀라고 있는 표정이지,,,

이걸 계산하는 프로그램을 작성해보자.

recursion없이...반복문으로 짜면

실행결과는 잘 나온다.

Recursion을 이용한 factorial 계산

반복문으로 짰던 것을

이제

굳이 recursion을 이용해서 짜보자.

그나마 factorial 예제가 recursion을 이해하기가 쉽다.

함수 int fact(int n)은 재귀함수이다.

재귀함수는 두 부분으로 이뤄어 진다.

하나는 탈출 파트,

다른 하나는 지속 파트,

지속 파트에서는 자기 자신을 호출한다.

탈출 파트에서는 자기 자신을 더이상 호출하지 않는다.

위 프로그램이 어떻게 동작하는지 자세히

알고 싶으시죠.. 

아래 동영상을 보시면 손그림을 그려가면서

자세히 설명해 주고 있습니다.

위에서 설명한 내용을 동영상으로 보고 싶으면,,,

Abstract Data Type

data type, 혹은 데이터형

C언어에서 변수들은 data type을 가진다.

가장 대표적인 것인 int, 

int는 정수값을 말한다. 

int형의 변수에는 음의 정수, 0, 양의 정수를 저장할 수 있다.

실수값을 저장할 수 있는 data type은 float, 혹은 double

또는 새로운 데이터형을 만들 수도 있다.

struct를 이용하는 것이다.

예를 들어,

와 같이 하면

struct A라는 새로운 data type을 만든 것이다.

그리고 struct A a라고 하면,

a 라는 변수를 만든 것이고,

이 변수의 data type은 struct A가 된다.

abstract data type

Abstract Data Type (줄여서 ADT)라는 것이 있다.

data type은 데이터형이니 이해하는 데 아무 문제가 없을 것인데,

abstract가 앞에 붙었다.

Abstract의 사전적 의미는 '추상적'이다.

우리말로 하면, ADT는 추상데이터형 이라고 번역하면 되겠다.

그래도 이게 뭔지 잘 이해가 되지 않을 것이다.

우선, 정의부터 얘기하자면

ADT라는 것은 '데이터를 저장할 수 있는 공간'과 '그 공간을 사용하는 방법'을 정의한 것이다.

정의를 얘기해도 뭔말인지,, 

그럼, 비유를 들어서 얘기해보자.

데이터 '물'이 있다. 먹는 물을 말하는 것이다.

물을 저장할 수 있는 공간을 신이 창조하면서 '냄비'라고 했다고 하자.

'물을 저장할 수 있는 공간' = '냄비' = '데이터를 저장할 수 있는 공간'

'냄비'는 data type이 된다.

'냄비'를 사용할 수 있는 방법을 생각해 보자.

1. 물을 넣다.

2. 물을 비우다.

3. 물을 데우다.

(1, 2, 3 방법) = '냄비를 사용하는 방법' = '고 공간을 사용하는 방법' 

이렇게 '냄비'라는 저장공간을 만들면서, 그 공간을 사용하는 방법까지 정의한 것을

abstract data type이라고 한다.

비유를 다 걷어내고 말하면,

Abstract data type이란 데이터공간구조와 그 구조를 사용할 수 있는 방법을 같이 정의한 것

데이터구조란 결국 ADT를 정의하고, 그것을 프로그래밍 언어로

구현한 것에 불과하다.

예를 들어, 필요한 ADT가 다음과 같은 것이라고 하자.

숫자를 저장하는 공간인데, 

거기에 숫자를 넣을 수도 있고,

꺼낼수도 있는데, 꺼낼 때는 넣은 순서대로 꺼내어진다.

데이터공간구조는 "숫자를 저장하는 공간"이고,

사용방법은 "숫자를 넣고, 넣은 순서대로 꺼내어진다."가 된다.

위에서 설명한 ADT는 Queue(큐)라는 것이다.

이런 ADT도 있다.

숫자를 저장하는 공간인데,

거기에 숫자를 넣을 수도 있고,

꺼낼 수도 있는데, 꺼낼 때는 넣은 순서의 역순으로 꺼내어 진다.

이것은 Stack (스택)이라는 ADT이다.

데이터구조를 공부한다는 것은

이러한 ADT들을 공부하고,

필요에 따라 새로운 ADT들을 만들 수 있는 능력을 키우는 것이다.

typedef 사용하기

매크로

C언어에서 macro라는 것이 있다.

말로 설명하기는 좀 그렇지만,

#define AAA 10

이런 거다.

이것은 소스코드에 나타나는 AAA를 모두 10으로 처리하게 하는 것이다.

왜 이런 매크로를 사용하는가?

1. 가독성

2. 편리성

3. 오류방지

세 가지 정도의 이유가 있다.

예를 들어, 3.1415921564,, 파이값, 원주율을 소스코드에서 사용한다고 하자.

그것도 아주 많이.

이 숫자가 길어서, 문제가 많다.

1. 소스코드가 지저분해서 보기가 싫다. --> 가독성이 떨어진다.

2. 숫자가 긴 파이값을 입력하기가 불편하다 ---> 편리성이 떨어진다.

3. 파이값 입력하다가 오타나기가 쉽가 --> 오류가 쉽게 생긴다.

그래서,

#define PI 3.1415921564

이렇게 해놓고, 소스코드에서는 PI만 쓰면

문제점, 1, 2, 3를 한 번에 해결할 수 있다.

typedef

만약에,

int 라는 데이터형 이름이 마음에 안든다고 하자.

왜 마음에 안들지?

글쎄,, 날 버리고 매몰차게 떠난 그 사람의 이름이 "김int"라고 하자.

가뜩이나 힘들어 죽겠는데,

C언어 프로그래밍 할 때마다, int가 나오면 이건 더 죽을 맛이다.

이 때 int 대신 다른 것을 쓸 수 있도록 해주는 것이 typedef이다.

이렇게 하면, int 대신에 byebye를 해도 된다.

int a, b, c; 이렇게 코딩하던 것을 

byebye a, b, c; 이렇게 해도 된다는 것이다.

물론,,,

헤어진 연인의 이름을 피하기 위해 typedef가 생기지는 않았다.

typedef는 긴 data type이름을 사용하는 불편함을 없애기 위한 것이다.

긴 data type 이름이란 무엇인가?

구조체를 새로 만들어 보자.

이제 새로운 data type struct ABCD가 생긴 것이다.

이 type을 갖는 변수를 만들려면,

다음과 같이 해야 한다.

이렇게 했을 때 문제점은

1. 불편해

2. 틀리기 위해

3. 소스가 지저분해져

이를 해결하려면 typedef를 사용하면 된다.

1. struct를 정의하면서 이름을 바로 YYY로 하는 방법도 있고,

2. struct abc를 정의한 후에, typedef를 이용해서 이름을 YYY로 개명하는 방법도 있다.

위에서 설명한 내용을 동영상에서 "무미건조"하게 설명합니다.

Method overriding에 대해 실습합니다.

bit 연산자에 대해서 설명합니다.

관계연산자에 대해서 설명합니다.

논리연산자에 대해서 설명합니다.

연산자의 shorthand에 대해서 설명합니다.

증감연산자의 사용에 대해서 설명합니다.

연산자 (operator)에 대해서 알아봅니다.

실수 데이터형 (Data type for Real Numbers)

C언어에서는 실수를 위해 다음과 같은 두 가지 데이터형을 제공한다.

프로그램으로 확인해 보는 크기와 최대, 최소값

아래는 float와 double형의 크기와

각각에 해당하는 최소값과 최대값을 출력해주는 프로그램이다.

실수형의 최소, 최대값을 알기 위해서는

line 2에서와 같이 float.h 헤더파일을 사용해야 하고,

FLT_MIN (MAX), DBL_MIN(MAX)가 최소, 최대값에 해당한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <stdio.h>
#include <float.h>

int main(void)
{
	printf("float size is %d\n", sizeof(float));
	printf("float min %e, max %e\n\n", FLT_MIN, FLT_MAX);

	printf("double size is %d\n", sizeof(double));
	printf("double min %e, max %e\n\n", DBL_MIN, DBL_MAX);
	return 0;
}

실행결과

최소와 최대값이 지수형으로 표시되었다.

float의 최소값을 예로 들면, 

그리고, 최소값이 음수가 아닌 양수이다.

이것은 마이너스 부호만 붙이면 최대값이 최소값이 되기 때문이다.

따라서, 절대값으로 표현할 수 있는 가장 작은 수를 최소값으로 한 것이다. 

double형의 최소, 최대값은 float형과

비교했을 때 어마무시하게 크고, 정밀하다는 것을 알 수 있다.

아래 동영상에서는

이진수 표현, 실수 데이터형인 float와 double, 그리고 overflow에 대해서 설명합니다.

정수 자료형 (Data type for Integer)

C언어에서는 정수를 저장할 수 있는

자료형으로 다음 4가지를 제공한다.

주의할 것은 long형은 Windows 운영체제에서는 int와 동일하다.

다른 운영체제에서는 다를 수도 있으니, 경우에 따라 확인해서 사용해야 한다.

sizeof( )

데이터형이 갖는 크기를 알려면

sizeof( )연산자를 사용하면 된다.

데이터형 이름을 써도 되고, 그 데이터형의 변수 이름을 써도 된다.

데이터형의 최소값과 최대값

각 데이터형이 가질 수 있는 최소값과 최대값을 알려면, 

#include <limits.>를 헤더파일에 포함시키고 (아래코드의 line 2 참조),

미리 지정된 값 (CHAR_MIN, CHAR_MAX, 등,, 아래 코드 확인)을

출력해 보면된다.

아래 프로그램은 위의 4가지 자료형의 크기, 최소, 최대값을

출력해주는 프로그램이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>
#include <limits.h>

int main(void)
{
	printf("char size is %d\n", sizeof(char));
	printf("char min %d, max %d\n\n", CHAR_MIN, CHAR_MAX);

	printf("short size is %d\n", sizeof(short));
	printf("short min %d, max %d\n\n", SHRT_MIN, SHRT_MAX);

	printf("int size is %d\n", sizeof(int));
	printf("int min %d, max %d\n\n", INT_MIN, INT_MAX);

	printf("long size is %d\n", sizeof(long));
	printf("long min %d, max %d\n\n", LONG_MIN, LONG_MAX);
	return 0;
}

실행결과는 아래와 같다.

위의 내용을 동영상에서 설명하고 있습니다.

매크로 (Macro) #define

프로그래밍하면서

어떤 숫자는 너무 길거나 복잡해서 불편한 경우가 있다.

예를 들어,

원주율 파이(pi)같은 것이 그런 것이다.

3.141592.....

이걸 다 치고 있으려면 시간도 많이 걸리고,

오타날 확률도 있다.

그리고,

숫자가 짧긴 하지만,

다른 사람이 보기에 그 숫자가 무엇을 의미하는지가

직관적이지 않을 때가 있다.

예를 들어,

13.

무슨 뜻일까?

주민번호 자릿수 이다.

그래서, 

C언어에서는 

특정 수에 이름을 붙여서 사용할 수 있도록 하는

#define 매크로라는 것을 제공하고 있다.

아래 프로그램을 보면 쉽게 이해간다.

#define이라고 쓰고,

내가 사용하고 싶은 이름을 쓰고,

그 이름에 해당하는 숫자를 쓰면 된다.

이 때, 

#define 매크로 뒤에는 세미콜론을 붙이지 않는다.  

일단, MYNUMBER가 15로 정의되면,

이후 프로그램에서는 15대신에 MYNUMBER를 붙여서 쓰면된다.

그리고,

이런 #define 매크로는 원하는 만큰 정의해서 쓰면 된다.

데이터 타입, char

지금까지 데이터타입은 int만 사용해 왔는데,

새로운 것을 하나 더 배워보자.

하나의 문자를 저장할 수 있는 char형이다.

이 때 문자는 알파벳, 숫자, 각종 기호 등, 한 글자로 이루어진 것이면 된다.

그리고 문자는 작은 따옴표로 감싸서 표시한다.

문자형 변수 c를 선언하고,

여기에 문자 'a'를 저장하고 있다.

그리고

변수 d에는 숫자 문자 '9'를 저장하고 있다.

이 때 9는 숫자가 아님을 주의하자.

변수 e에는 기호 문자 '+'를 저장하고 있다.

문자 출력을 위한 형식지정자: %c

문자형 변수의 값을 printf를 이용해서

출력하기 위해서는

'%c'라는 형식지정자를 이용해야 한다.

특수문자: \n, \t, \a,

줄바꿈을 할 때 사용하는 '\n'을 기억할 것이다.

이것은 문자인데, 특수한 역할을 하기 때문에

앞에다가 back-slash 기호인 '\'를 붙여서 사용한다.

이런 종류의 특수문자들이 몇 개 있는데,

두 개만 더 소개하면,

\t는 탭 문자라서, 이것을 출력하면 탭 크기만큼 띄어쓰고,

\a는 alarm문자라서, 이것을 출력하면 '삑'소리가 난다.

아래 동영상을 보면 이 소리를 들어볼 수 있다. 

C언어의 데이터형인 char에 대해서 설명합니다.