자료구조 세미나 발표 주제: 자료구조 기초 - 1회 차: 자료구조의 정의, 기초 지식 (함수, 포인터, 레퍼런스) - 2회 차: 메모리 구조와 할당 (메모리 구조, 배열, 동적할당) 발표자: SGA15기 남궁곤

자료 구조란? (Data Structure) “자료를 목적에 따라서 효율적으로 사용하기 위해서 구조화 시켜놓은 것” 자료구조 세미나: 자료구조의 기초 (1) 자료 구조란? (Data Structure) 전산학에서 자료구조(資料構造, data structure)는 자료를 효율적으로 이용 할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. “자료를 목적에 따라서 효율적으로 사용하기 위해서 구조화 시켜놓은 것” SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

알고리즘 이란? (Algorithm) “어떤 문제를 해결하기 위한 최선의 방법” 자료구조 세미나: 자료구조의 기초 (1) 알고리즘 이란? (Algorithm) 알고리즘(algorithm [ǽlɡərìðm])이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다 위키백과 참조 “어떤 문제를 해결하기 위한 최선의 방법” SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

자료구조 구현을 위한 기초지식 1. 함수 (function) 2. 포인터 (pointer) 3. 레퍼런스 (reference) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 자료구조 구현을 위한 기초지식 1. 함수 (function) 2. 포인터 (pointer) 3. 레퍼런스 (reference) SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

자료구조를 위한 기초지식 #1 함수 (function) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 자료구조를 위한 기초지식 #1 함수 (function) - 수학적 표현: F(x) - 그림으로 표현 입력 출력 - 입력과 출력간의 관계를 정의 하는 것을 함수라고 한다. “Divide and conquer” - 코드의 재 사용성 높이기 - 복잡한 문제를 단순하게 해결 SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

1) 함수의 기본 구성 2) 함수의 기본 형태 int main (void) { 함수의 몸체 (body) } 함수의 호출 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 1) 함수의 기본 구성 출력의 형태 함수의 이름 입력의 형태 int main (void) { 함수의 몸체 (body) } 함수의 시작 함수의 끝 2) 함수의 기본 형태 함수의 호출 전달인자 有, 반환 값 有 전달인자 有, 반환 값 無 전달인자 無, 반환 값 有 전달인자 無, 반환 값 無 - 숫자 두 개를 입력 받아 출력하는 프로그램 int main(void) { int i, j, sum; Intro(); i = Input (); j = Input (); sum = Add(i, j); Result_Print(sum); return 0; } int Add(int i, int j) { int result = i + j; return result; } void Result_Print(int val) { cout << “결과: “ << val << endl; } int Input(void) { int input; cin >> input; return input; } void Intro(void) { cout << “계산기프로그램” << endl; return result; } SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

3) 함수의 설계 1단계: 문제 분석 2단계: 기능 정의 3단계: 함수 구조 설계 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 3) 함수의 설계 1단계: 문제 분석 2단계: 기능 정의 3단계: 함수 구조 설계 - 함수의 시그니쳐와 구현부 작성 (Pseudo Code로 작성) 4단계: 코드 작성 5단계: 컴파일 / 디버깅 SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

4) 재귀적 함수 (recursion function) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 4) 재귀적 함수 (recursion function) - 재귀적 함수 호출이란 함수 내에서 자기 자신을 다시 호출하는 형태의 함수 #include <iostream> using namespace std; void Recursive(void) { cout << "Recursive Call!" << endl; Recursive(); } void main(void) Recursive Call! Recursive Call! Recursive Call! Recursive Call! . forever… “마지막에는 메모리 부족으로 실행이 중지된다.” “탈출 조건에 대한 설계가 재귀 함수에서 가장 중요!” #include <iostream> using namespace std; void Recursive(int a) { cout << "Recursive Call!" << endl; if (n == 1) return; Recursive(n-1); } void main(void) int a=2; Recursive(a); “2번만 호출된다.” “탈출 조건!” SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

“팩토리얼 (Factorial) 계산을 위한 함수를 구현” 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 - 재귀 함수 디자인 사례 “팩토리얼 (Factorial) 계산을 위한 함수를 구현” - 팩토리얼의 정의 n! = n × (n-1) × (n-2) × (n-3) ………………….. × 2 × 1 n × f(n-1) n이 1이상인 경우 1 n이 0인 경우 (탈출 조건) f(n) = #include <iostream> using namespace std; int Fatorial (int n); void main(void) { int val; int result; cin >> val; result = Fatorial(val); cout << val << "! = " << result << endl; } int Fatorial (int n) { if (n == 0) return 1; else return n*Fatorial (n-1); } SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

자료구조를 위한 기초지식 #2 포인터 (Pointer) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 자료구조를 위한 기초지식 #2 포인터 (Pointer) “포인터는 주소 값을 저장하기 위한 변수이다.” 0x1000 C = ‘a’ 0x1001 n= 7 0x1002 0x1003 int main(void) { char c = ‘a’; int n = 15; double d = 3.14 } 0x1004 0x1005 d = 3.14 0x1006 0x1007 0x1008 0x1009 0x100a 0x100b 0x100c “변수가 선언되면 메모리 공간에 할당된다.” 운영체제로부터 메모리 공간 어딘가에……………… SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

“포인터는 말 그대로 주소를 통해 다른 것을 가리킨다.” 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 “포인터는 말 그대로 주소를 통해 다른 것을 가리킨다.” 0x1000 n= 7 0x1001 0x1002 0x1003 “포인터는 말 그대로 다른 주소를 가리킨다.” “포인터pN이 변수 N을 가리킨다” 0x1004 0x1005 0x2012 pN = 0x1000 0x2013 0x2014 0x2015 0x2016 0x2017 0x2018 SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

- 포인터 선언하기 int * a 남선생님이 말한다면 아마도 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 - 포인터 선언하기 가리키는 주소에 저장되어 있는 데이터 형 포인터 변수 지정 변수의 이름 int * a 남선생님이 말한다면 아마도 “ 운영체제로부터 메모리 공간 어딘가에 주소를 저장할 수 있는 4바이트의 공간을 할당 받고 그 주소 값 위에 정수형 변수를 가리킬 수 있는 a라는 방을 만들고 그 방안에는 쓰레기 주소가 들어있다.” 라고 정의할 수도 있다. int main(void) { int *a; char *b; double *c; } 질문1) sizeof(a)는 4바이트이다. 그럼 sizeof(b), sizeof(c)의 값은 몇일까요? “포인터의 타입은 메모리를 참조하는 방법을 알려주는 역할을 한다.” SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

“가리키는 대상의 데이터 형이 정해지지 않은 포인터” 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 - void 포인터 “가리키는 대상의 데이터 형이 정해지지 않은 포인터” 그럼 void 포인터는 좋은 포인터(?)인데 왜 가르치지 않을까? 1. *연산(역 참조)이 불가 2. 가리키는 곳의 데이터 형이 없음으로 +, -와 같은 포인터 연산 불가 단, 포인터의 형 변환을 하면 하면 1, 2번 둘 다 가능하다. #include <iostream> using namespace std; void main(void) { void *a; int b=4; a = &b; cout << “*a= ” << *a << endl; } #include <iostream> using namespace std; void main(void) { void *a; int b=4; a = &b; cout << “*a= ” << *(int*)a << endl; } Error C2100: illegal indirection! 우리가 원하는 값이 출력된다. SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

- 주소와 관련된 연산자 1) 주소 값을 참조할 때 사용하는 연산자: Ampersand (&) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 - 주소와 관련된 연산자 1) 주소 값을 참조할 때 사용하는 연산자: Ampersand (&) ※ Ampersand의 어원: and(&) per se and per se = (라틴어로 it self) 즉 and(&) 기호는 그 자체가 &이다. - 변수에 &를 붙이면 주소 값을 반환 2) 포인터가 가리키는 메모리 참조: Asterisk (*) - 포인터 변수 앞에 *를 붙이면 포인터가 가리키는 메모리 공간에 존재하는 값을 참조 하는 것을 의미한다. 3) 포인터가 가리키는 것들 - 포인터는 변수 뿐 아니라 “배열, 다른 포인터, 구조체, 함수, 클래스 등을 가리킬 수 있다.” #include <iostream> using namespace std; void main(void) { int *a; int b=4; a = &b; cout << “a= 주소는” << &a << endl; cout << “b= 주소는” << a << endl; cout << “*a =” << *a << endl; } SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

자료구조를 위한 기초지식 #2 참조자 (Reference) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 자료구조를 위한 기초지식 #2 참조자 (Reference) “참조자는 참조하는 변수에 별명(alias)을 붙이는 것이다.” a int a = 10; 10 “a를 참조한다는 것은 a라는 방에 또 다른 이름을 붙이는 것이다.” int a = 10; a 10 int &b = a; b “만약 a의 주소가 0x0ac8 이라면 b의 주소를 알 수 있을까?” SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

- 참조자의 선언 a * b int *a; *a = 4 a & b; (bit 단위 and 연산) 1) 참조자를 선언할 사용하는 연산자: Ampersand (&) ※ Ampersand의 어원: and(&) per se and per se = (라틴어로 it self) 즉 and(&) 기호는 그 자체가 &이다. 어라? 어디선가 본듯한…… 절대 ctrl + c , v 아님 - 같은 연산자가 다른 의미로 쓰이는 경우가 많다! a * b int *a; *a = 4 a & b; (bit 단위 and 연산) a = &b; (주소 값 참조 연산자) &a = b; (참조자 선언 연산자) * & - 각 각의 형태와 용도를 잘 기억 해 놓는 방법밖에 없다. 2) 참조자는 선언과 동시에 참조되어야 한다. - int &ref - int &ref = 20; - int &ref = NULL “다음 중 올바르게 선언된 참조자는?” 3) 참조자는 수의 제한이 없으며 참조자를 대상으로도 참조 가능 4) 일단 선언되면 일반 변수와 거의 동일하게 사용가능하며 변경이 불가능

“참조자는 포인터와 유사하다. (포인터의 사촌쯤)” 5) 참조자를 ‘변수’를 참조 가능하다. - 배열의 요소도 변수로 취급하여 참조가능 - 포인터도 변수로 취급하여 참조가능 int a[3] = {0, 1, 2}; int &ref = a; int &ref = a[1]; int b = 3; int *a = &b int &ref = a error C2440: 'initializing' : cannot convert from 'int [3]' to 'int &' OK OK “참조자는 포인터와 유사하다. (포인터의 사촌쯤)” “주소의 개념이 아닌 이름의 개념으로 참조하기 때문에 보다 쉽게 이해가 가능할 수 있다.” “그러나 참조자 보다 포인터가 더 많이 쓰인다.”

(Passing by Reference) 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 자료구조를 위한 기초지식 #3 참조에 의한 전달 (Passing by Reference) Call by value Call by reference void main(void) { int a = 10; int b = 20; Swap(a, b); } Swap(int a, b) int Temp = a; a = b; b = Temp; void main(void) { int a = 10; int b = 20; Swap(a, b); } Swap(int &a, &b) int Temp = a; a = b; b = Temp; “ 결과 값은 어떻게 될 것인가? “ SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

Call by reference “참조자를 이용해서 참조“ “ 주소를 이용해서 참조 “ “이해하고 쓰기 쉽다“ 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 Call by reference “참조자를 이용해서 참조“ “ 주소를 이용해서 참조 “ void main(void) { int a = 10; int b = 20; Swap(a, b); } Swap(int &a, &b) int Temp = a; a = b; b = Temp; void main(void) { int a = 10; int b = 20; Swap(&a, &b); } Swap(int *a, *b) int Temp = *a; *a = *b; *b = Temp; “이해하고 쓰기 쉽다“ “이해하고 어렵고 쓰기 어렵다 그러나 다양한 것을 할 수 있다.“ SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771

- 반환형이 참조 형인 경우 “return 값은 상수 취급이다.” “return 값은 참조자 다.” 자료구조 세미나: 자료구조의 기초 (2) –자료구조 구현을 위한 기본 지식 - 반환형이 참조 형인 경우 void main(void) { int a = 10; int b = func(a); int &c = func(a); } int Swap(int &ref) ref ++; return ref; void main(void) { int a = 10; int b = func(a); int &c = func(a); } int &Swap(int &ref) ref ++; return ref; “return 값은 상수 취급이다.” “return 값은 참조자 다.” int &c = func(a); int &c = func(a); Error!!! SGA (Seoul Game Academy) Program-15th Seminar NamgungGon_a.k.a torch: email: gonii78@gmail.com mobile: 010-9959-9771