Chap.5 전체와 부분 - 함수

함수(function)

• 수학에서의 ‘함수’의 정의

- y=f(x1, x2, …, xn)	// 독립변수, 함수이름, 종속변수

http://ko.wikipedia.org/wiki/%ED%95%A8%EC%88%98 (함수)

- 독립변수들과 종속변수와의 수학적 관계(relationship)

• 프로그램에서의 ‘함수’

- C language: Function-based Programming Language

http://ko.wikipedia.org/wiki/함수(프로그래밍)

- 전체를 구성하는 ‘부분’들 (not 수학적 관계): 특정한 기능(function)을 수행

main()

main

codes

library

functions

user

functions

e.g., cc test.c -o test -lm -lcurses

- y=f(x1, x2, …, xn)   // y: return value   f: function name

x1, x2, …, xn : I/O arguments(인자/parameter)

e.g., 사람{             //  program

먹는다();       // we don't know exactly what happens inside...

잔다();         // information hiding

}

자동차 program{

엑셀레이터(push_level); // we know exactly what happens inside...

브레이크(push_level);   // information hiding

핸들(rotate_level);

}

• Object-oriented Programming Language

- class: 객체(object)를 만들기 위해 사용되는 형판(template).

variables

methods

class

hierarchy

inheritance

variables

methods

variables

methods

……

- object: class로부터 생성되는 instance.

⇒ 동일 class로부터 여러 개의 객체를 생성할 수 있음.

⇒ class로부터 생성된 각 객체는 동일한 variable들과 method들을 가지나, variable의 값들은 다를 수 있음.

- class variable: object reference

⇒ object는 생성자(constructor)를 이용하여 메모리에 생성됨.

- object들을 생성하여 ‘전체’를 구성:

e.g., Java

p1=new Protoss(x1, x2, …, xn)    // make an object from the class.

p2=new Protoss(y1, y2, …, yn)

- C++, C#, Java 등

C 함수

• C 라이브러리 함수

[본문] p.102 - p.182: Chap 05-1 PPT

e.g., 3.7 난수 생성

• 사용자 정의 함수:

[부록 5] p.709 - 712 참조 ([C 콘서트] Chap. 07)

#include <stdio.h>

#define MAX 100	// 매크로 상수

[함수 원형의 선언]

int main(void){	// int main(argc, argv)

...
[함수 호출]

...

return 0;

}

[함수 정의]

- 변수의 범위: [부록 5] p.714 - 719 참조

([C 콘서트] Chap. 07)

지역(local) 변수와 전역(global) 변수	// 함수 내 or 함수 외

자동(auto) 변수	// 지역(local) 변수

정적(static) 변수	// local 변수와는 달리 프로그램 종료시까지 유지

외부(extern) 변수	// 다른 file의 변수를 사용할 때

레지스터(register) 변수	// CPU register 사용, 실행 속도 증가

ex) 정적 변수

#include <stdio.h>

int gcnt=0;	// 외부 (정적) 변수: static int gcnt=0;

void count(void);

int main(int argc, char *argv[])

{

int i;

for(i=1; i<=3; i++){

count();

gcnt+=1;	// 외부 정적 변수 사용...

}

return 0;

}

void count(void)

{

int lcnt=0;	// 지역 변수

static int stcnt=0;	// 내부 정적 변수

lcnt+=1;	// 지역 변수 사용...

stcnt+=1;	// 내부 정적 변수 사용...

gcnt+=1;	// 외부 정적 변수 사용...

printf("local count=%d, local static count=%d, global static count=%d\n", lcnt, stcnt, gcnt);

}

ex) 외부 변수

> cc 718.c 718-1.c -o 718    // 분할 컴파일

// 718.c

#include <stdio.h>

void func01(void);

int data;

int main(void){

data=9;

printf("before call=%d\n", data);

func01( );

printf("after call=%d\n", data);

return 0;

}

// 718-1.c

#include <stdio.h>

extern int data;

void func01(void){

data=10;

printf("call func01=%d\n", data);

data=20;

}

• 재귀 함수: recursive function

- 자신을 사용하여 정의되는 함수

⇒ 함수 내에서 ‘자신’을 다시 호출(call)

- 프랙탈(fractal): 자기 자신을 계속하여 반복하는 구조

http://ko.wikipedia.org/wiki/%ED%94%84%EB%9E%99%ED%83%88 (프랙탈)

http://ko.wikipedia.org/wiki/%EC%BD%94%ED%9D%90_%EB%88%88%EC%86%A1%EC%9D%B4 (코흐눈송이)

- 점화식/재귀식(recurrence relation): 재귀함수를 사용

https://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D

ex) Factorial(n): n!

F(1) = 1

F(n) = n * F(n-1)

e.g. [C 콘서트] Chap. 07 p.251 - 254 참조

ex) Add(n): ∑k=1nk

A(1) = 1

A(n) = n + A(n-1)

e.g. [부록 5] p.712 - 714 참조

ex) 하노이의 탑 (Tower of Hanoi)

http://ko.wikipedia.org/wiki/하노이의 탑

(조건) 한 번에 하나의 원판만 이동할 수 있다.

맨 위에 있는 원판만 이동할 수 있다.

크기가 작은 원판위에 큰 원판이 쌓일 수 없다.

Tn : n개의 원판을 다른 기둥으로(from → to) 옮기는데 필요한 횟수

Tn+1 = Tn + 1 + Tn

= 2Tn +1

T1 = 1

①

②

③

from                 to             temporary

T1 = 1

T2 = 2T1 +1 = 3 = 22 - 1

T3 = 2T2 +1 = 7 = 23 - 1

T4 = 2T3 +1 = 15 = 24 - 1

……

Tn = 2n - 1

// http://en.wikipedia.org/wiki/Mersenne_number

• hanoi.c

#include <stdio.h>

void hanoi_tower(int n, char from, char tmp, char to);

int main(void)

{

int i;

printf("no of disks> ");

scanf("%d", &i);

hanoi_tower(i, 'A', 'B', 'C');  // i - number of disks

return 0;

}

void hanoi_tower(int n, char from, char tmp, char to)

{

if (n==1)

printf("원판 1을 %c에서 %c로 옮긴다.\n", from, to);

else{

hanoi_tower(n-1, from, to, tmp); // from에서 tmp로 n-1을 옮김

printf("원판 %d을 %c에서 %c로 옮긴다.\n", n, from, to);

// 맨 밑 n번째 원판을 from에서 to로 옮김

hanoi_tower(n-1, tmp, from, to); // tmp에서 to로 n-1을 옮김

}

}

①

②

③

from                      tmp                  to

e.g., no of disks> 10의 경우

no of disks> 20의 경우

e.g., 1초에 원판을 한 개씩 옮길 수 있다면

T64 = 264 - 1 초

= 18,446,744,073,709,551,616 초

= 584,942,417,400년

컴퓨터의 경우, 1μs = 1 * 10-6에 연산을 한 번 한다고 한다면

약 584,942년

• [본문] p.223 - p.262: Chap 05-2 PPT

- 4.2 집합연산

합집합

교집합

차집합

- 4.5 순열과 조합

http://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4 (순열)

http://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9 (조합)

- 4.6 암호화와 복호화

http://ko.wikipedia.org/wiki/%EC%95%94%ED%98%B8%ED%95%99 (암호학)

http://en.wikipedia.org/wiki/Caesar_cipher

e.g., by a brute force attack

"exxegoexsrgi"

shift left 1: dwwdfndwrqfh

2: cvvcemcvqpeg

3: buubdlbupodf

4: attackatonce

- 4-6-1.c : Caesar 암호

#include <stdio.h>

#include <string.h>

char* substitution_cipher(int shift, char text[]);

char* decryption(int shift, char cipher[]);

char s[]="yesterday";

char cipher[41]={'\n'};

char text[41]={'\n'};

int main(void)

{

printf("암호문: %s\n\n", substitution_cipher(1, s));

printf("암호문: %s\n\n", substitution_cipher(2, s));

printf("암호문: %s\n\n", substitution_cipher(3, s));

printf("평문: %s\n\n", decryption(1,substitution_cipher(1, s)));

printf("평문: %s\n\n", decryption(2,substitution_cipher(2, s)));

printf("평문: %s\n\n", decryption(3,substitution_cipher(3, s)));

return 0;

}

char* substitution_cipher(int shift, char text[])

{

int i, length;

length=strlen(text);

printf("\n환자암호 - 암호화\n");

printf("평문  : %s\n", text);

for(i=0;i<length;i+=1)

cipher[i]=((text[i]-'a')+shift)%26; // ((0-25까지의 숫자 부여)+shift) mod 26

for(i=0;i<length;i+=1)

cipher[i]=toupper(cipher[i]+'a');   // ASCII 소문자로 변환 후 대문자 변환

return cipher;

}

char* decryption(int shift, char cipher[])

{

int i, length;

length=strlen(cipher);

printf("\n환자암호 - 복호화\n");

printf("암호문: %s\n", cipher);

for(i=0;i<length;i+=1)

text[i]=((cipher[i]-'A')-shift+26)%26+'a';  // (암호문-n)이 음수인 경우 +26

return text;

}

- 암호화: char* substitution_cipher(int shift, char text[])

text[i]-'a'

암호화 cipher[i]

toupper(cipher[i]+'a')

- 복호화: char* decryption(int shift, char cipher[])

②

③

① 숫자화:   cipher[i]-'A'

② 복호화:   ((cipher[i]-'A')-shift+26)%26	// (암호문-n)이 음수인 경우...

// %26하기 전에 +26

e.g., 'B': (1-3+26)%26 = 24 → 'y'

'H': (7-3+26)%26 = 4  → 'e'

③ 문자화:   ((cipher[i]-'A')-shift+26)%26+‘a'

- 4-6-3.c : 단순전치 암호

e.g., p.258 참조

평문:

배열 index	0	1	2	3	4	5
text[]	s	u	n	d	a	y

암호화

복호화

key[] index

key[] value

key:

배열 index	0	1	2	3	4	5
key[]	2	4	0	5	3	1

암호문:

배열 index	0	1	2	3	4	5
cipher[]	n	a	s	y	d	u

for (j=0;j<6;j+=1)	// 암호화 코드

cipher[ j ] = text[ key[j] ];  // text[key[j]] 값을 cipher[j]로 옮김

for (i=0;i<6;i+=1)	// 복호화 키값

inv_key[ key[i] ] = i ; //key[]의 ‘value’가 inv_key의 ‘index’로 변환

암호문:

배열 index	0	1	2	3	4	5
cipher[]	n	a	s	y	d	u

inv_key:

배열 index	0	1	2	3	4	5
inv_key[]	2	5	0	4	1	3

⇒ key[]의 ‘value’를 ‘index’로 역변환

평문:

배열 index	0	1	2	3	4	5
text[]	s	u	n	d	a	y

for(j=0;j<6;j+=1)	// 복호화 코드

text[j]=cipher[inv_key[j]];

#include <stdio.h>

#include <string.h>

char* simple_transposition_cipher(int key[], char text[]);

char* decryption(int key[], char cipher[]);

char s[]="sundaywar";

char add_text[]="abcde";

char cipher[41]={'\n'};

char text[41]={'\n'};

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

int inv_key[6];

int main(void)

{

printf("암호문: %s\n\n", simple_transposition_cipher(key, s));

printf("평문: %s\n\n", decryption(key, cipher));

return 0;

}

char* simple_transposition_cipher(int key[], char text[])

{

int i, j, length, loop;

for(i=0;i<6;i+=1)

key[i]=key[i]-1;

length=strlen(text);

loop=length/6;

strcat(text, add_text);

printf("\n단순전치암호 - 암호화\n");

printf("평문 : %s\n", text);

for(i=0;i<=loop;i+=1)

for(j=0;j<6;j+=1)

cipher[j+i*6]=text[key[j]+i*6];

return cipher;

}

char* decryption(int key[], char cipher[])

{

int i, j, length, loop;

length=strlen(cipher);

loop=length/6;

printf("\n단순전치암호 - 복호화\n");

printf("암호문 : %s\n", cipher);

for(i=0;i<6;i+=1)

inv_key[key[i]]=i;

for(i=0;i<=loop;i+=1)

for(j=0;j<6;j+=1)

text[j+i*6]=cipher[inv_key[j]+i*6];

return text;

}