슬라이드 1

Size: px
Start display at page:

Download "슬라이드 1"

Transcription

1 Data Structure Chapter 1. 자료구조와알고리즘 Dong Kyue Kim Hanyang University

2 자료구조와알고리즘

3 일상생활에서의사물의조직화 해야할일리스트 조직도 일상생활에서의사물의조직화 사전 Ticket Box 3

4 일상생활과자료구조의비교 일상생활 vs 자료구조 자료구조 스택 큐 리스트 사전, 탐색구조 그래프 트리 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 영어사전 지도 조직도 해야할일리스트 Ticket Box a b c NULL C B A 전단 (front) 후단 (rear) 4

5 자료구조와알고리즘 프로그램 = 자료구조 + 알고리즘 예 ) 최대값탐색프로그램 = 배열 + 순차탐색 자료구조 score[ ] 알고리즘 tmp score[0]; for i 1 to n do if score[i]>tmp then tmp score[i]; 5

6 알고리즘 알고리즘 (algorithm) : 컴퓨터로문제를풀기위한단계적인절차 알고리즘의조건 입력 : 0개이상의입력이존재하여야한다. 출력 : 1개이상의출력이존재하여야한다. 명백성 : 각명령어의의미는모호하지않고명확해야한다. 유한성 : 한정된수의단계후에는반드시종료되어야한다. 유효성 : 각명령어들은실행가능한연산이어야한다. 6

7 알고리즘의기술방법 영어나한국어와같은자연어 흐름도 (Flow Chart) 유사코드 (Pseudo Code) C와같은프로그래밍언어 7

8 알고리즘의기술방법 ( 자연어 ) 자연어 인간이읽기가쉬움 자연어의단어들을정확하게정의하지않으면의미전달이모호해짐 예 ) 배열에서최대값찾기알고리즘 ArrayMax(A,n) 1. 배열 A 의첫번쨰요소를변수 tmp 에복사 2. 배열 A 의다음요소들을차례대로 tmp 와비교하면더크면 tmp 로복사 3. 배열 A 의모든요소를비교했으면 tmp 를반환 8

9 알고리즘의기술방법 ( 흐름도 ) 흐름도 (Flow Chart) 직관적이고이해하기쉬운알고리즘기술방법 복잡한알고리즘의경우상당히복잡해짐 예 ) 배열에서최대값찾기알고리즘 ArrayMax tmp A[0] i 1 i < n no no yes A[i]>tmp yes tmp A[i] return tmp i++ 9

10 알고리즘의기술방법 ( 유사코드 ) 유사코드 (Pseudo Code) 알고리즘의고수준기술방법 자연어보다는더구조적인표현방법 프로그래밍언어보다는덜구체적인표현방법 알고리즘기술에가장많이사용 프로그램을구현할때의여러가지문제들을감출수있다. 알고리즘의핵심적인내용에만집중 ArrayMax(A,n) tmp A[0]; for i 1 to n-1 do if tmp < A[i] then tmp A[i]; return tmp; 10

11 알고리즘의기술방법 ( 프로그래밍언어 ) 프로그래밍언어 알고리즘의가장정확한기술이가능 실제구현시, 많은구체적인사항들이알고리즘의핵심적인내용에대한 이해를방해 #define MAX_ELEMENTS 100 int score[max_elements]; int find_max_score(int n) { int i, tmp; tmp=score[0]; for( I = 1; i < n; i++){ if( score[i] > tmp ){ tmp = score[i]; } } return tmp; } 11

12 버블정렬 (Bubble Sort) 인접한 2 개의레코드를비교하여순서대로되어있지않으면서로교환 이러한비교 - 교환과정을리스트의왼쪽끝에서오른쪽끝까지반복 ( 스캔 ) 초기상태 초기상태 와 3 을교환 스캔 교환없음 스캔 과 1 을교환 스캔 과 2 를교환 스캔 과 7 을교환 스캔 하나의스캔완료 정렬완료 12

13 버블정렬알고리즘 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void bubble_sort(int list[], int n) { int i, j, temp; for( i = n-1; i > 0; i-- ) for( j = 0; j < i; j++ ) if( list[j] > list[j+1] ) SWAP(list[j], list[j+1], temp); } 13

14 추상데이터타입

15 데이터타입 데이터타입 (Data Type) 데이터의집합과연산의집합 예 )int 데이터타입 데이터 : {, -2, -1, 0, 1, 2, } 연산 : +, -, /, *, % 추상데이터타입 (ADT: Abstract Data Type) 데이터타입을추상적 ( 수학적 ) 으로정의한것 데이터나연산이무엇 (what) 인가는정의되지만데이터나연산을어떻게 (how) 컴퓨터상에서구현할것인지는정의되지않는다. 15

16 추상데이터타입의정의 추상데이터타입 객체 : 추상데이터타입에속하는객체가정의된다. 연산 : 이들객체들사이의연산이정의된다. 이연산은추상데이터타입과외부를연결하는인터페이스의역할을한다. 2 3 객체 9 7 연산 8 추상데이터타입 16

17 추상데이터타입의예시 Nat_No 객체 : 0 에서시작하여 INT_MAX 까지의순서화된정수의부분범위 연산 zero() ::= return 0; is_zero() ::= if (x) return FALSE; else return TRUE; add(x,y) ::= if( (x+y) <= INT_MAX ) return x+y; else return INT_MAX sub(x,y) ::= if ( x<y ) return 0; else return x-y; equal(x,y) ::= if( x=y ) return TRUE; else return FALSE; successor(x) ::= if( (x+y) <= INT_MAX ) return x+1; 17

18 추상데이터 vs VCR 추상데이터 제공하는연산만을사용가능 어떻게사용하는지를알아야함 추상데이터타입내부의데이터접근불가 어떻게구현되었는지몰라도사용가능 구현이변경되어도인터페이스가변경되지않으면그대로사용가능 VCR 인터페이스가제공하는특정한작업만을수행 사용자는이러한작업들에대한이해필요 ( 비디오를시청하기위해서는무엇을해야하는지를알아야함 ) VCR의내부를볼수없음 VCR의내부에서무엇이일어나고있는지몰라도사용가능 내부의기계장치를교환되어도인터페이스가바뀌지않으면그대로사용가능 18

19 알고리즘의성능분석

20 알고리즘의성능분석 알고리즘의성능분석기법 수행시간측정 두개의알고리즘의실제수행시간을측정하는것 실제로구현하는것이필요 동일한하드웨어를사용하여야함 알고리즘의복잡도분석 직접구현하지않고서도수행시간을분석하는것 알고리즘이수행하는연산의횟수를측정하여비교 일반적으로연산의횟수는 n의함수 시간복잡도분석 : 수행시간분석 공간복잡도분석 : 수행시필요로하는메모리공간분석 20

21 알고리즘의성능분석 ( 수행시간 ) 수행시간측정 컴퓨터에서수행시간을측정하는방법에는주로 clock 함수가사용된다. clock_t clock(void); clock 함수는호출되었을때의시스템시각을 CLOCKS_PER_SEC 단위로반환 수행시간을측정하는전형적인프로그램 #include <stdio.h> #include <stdlib.h> #include <time.h> void main( void ) { clock_t start, finish; double duration; start = clock(); // 수행시간을측정하고하는코드... //... finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("%f 초입니다.\n", duration); } 21

22 알고리즘의성능분석 ( 복잡도분석 ) 시간복잡도 알고리즘을이루고있는연산들이몇번이나수행되는지를숫자로표시 산술연산, 대입연산, 비교연산, 이동연산의기본적인연산 수행시간이입력의크기에따라변하면안됨 알고리즘이수행하는연산의개수를계산하여두개의알고리즘비교가능 시간복잡도함수 : 입력의개수 n에대한연산의수행횟수. T(n) 이라고표기 22

23 복잡도분석의예 n 을 n 번더하는문제 각알고리즘이수행하는연산의개수를셈 단, for 루프제어연산은고려X 알고리즘 A 알고리즘 B 알고리즘 C sum n*n; sum 0; for i 1 to n do sum sum + n; sum 0; for i 1 to n do for j 1 to n do sum sum + 1; 알고리즘 A 알고리즘 B 알고리즘 C 대입연산 1 n + 1 n*n + 1 덧셈연산 n n*n 곱셈연산 1 나눗셈연산전체연산수 2 2n + 1 2n

24 연산의횟수를그래프로표현 그래프표현 연산의횟수 알고리즘 C 알고리즘 B 알고리즘 A 입력의개수 n 24

25 시간복잡도함수계산예 코드를분석해보면수행되는연산들의횟수를입력크기의함수로만들 수있다. ArrayMax(A,n) tmp A[0]; 1번의대입연산 for i 1 to n-1 do 루프제어연산은제외 if tmp < A[i] then n-1번의비교연산 tmp A[i]; n-1번의대입연산 ( 최대 ) return tmp; 1번의반환연산 총연산수 = 2n( 최대 ) 25

26 빅오표기법 빅오표기법 연산의횟수를대략적 ( 점근적 ) 으로표기한것 두개의함수 f(n) 과 g(n) 이주어졌을때, 모든 n n0에대하여 f(n) c g(n) 을만족하는 2개의상수 c와 n0가존재하면 f(n)=o(g(n)) 이다. 빅오는함수의상한을표시한다. 예 ) n 5 이면 2n+1 <10n 이므로 2n+1 = O(n) 연산의횟수 O( f ( n)) f (n) n 0 26

27 빅오표기법의예 예제 1.1 빅오표기법 f n = 5이면 O 1 이다. n 0 = 1, c = 10일때, n 1에대하여 이된다. f n = 2n + 1이면 O n 이다. n 0 = 2, c = 3일때, n 2에대하여 2n + 1 3n이된다. f n = 3n 이면 O n 2 이다. n 0 = 100, c = 5일때, n 100에대하여 3n n 2 이된다. f n = 5 2 n +10n 이면 O 2 n 이다. n 0 = 1000, c = 10일때, n 1000에대하여 5 2 n +10n n 이된다. 27

28 빅오표기법의종류 종류 O(1) : 상수형 O(logn) : 로그형 O(n) : 선형 O(nlogn) : 로그선형 O(n 2 ) : 2차형 O(n 3 ) : 3차형 O(n k ) : k차형 O(2 n ) : 지수형 O(n!) : 팩토리얼형 28

29 그외표기법 빅오메가표기법 모든 n n 0 에대하여 f(n) c g(n) 을만족하는 2 개의상수 c 와 n 0 가존재하면 f(n)=ω(g(n)) 이다. 빅오메가는함수의하한을표시한다. 예 ) n 5 이면 2n+1 <10n 이므로 n = Ω(n) 연산의수 O( f ( n)) 상한 f (n) ( f ( n)) 하한 n 0 입력의개수 n 29

30 수행시간 최선, 평균, 최악의경우 (1/3) 알고리즘의수행시간은입력자료집합에따라다를수있다. 예 ) 정렬알고리즘의수행시간 최선의경우 (best case) : 수행시간이가장빠른경우 평균의경우 (average case) : 수행시간이평균적인경우 최악의경우 (worst case) : 수행시간이가장늦은경우 최악의경우 평균적인경우 최선의경우 A B C D E F G 입력집합 30

31 최선, 평균, 최악의경우 (3/3) 순차탐색 최선의경우 : 찾고자하는숫자가맨앞에있는경우 O(1) 최악의경우 : 찾고자하는숫자가맨뒤에있는경우 O(n) 평균적인경우 : 각요소들이균일하게탐색된다고가정하면 (1+2+ +n)/n=(n+1)/2 O(n) 인덱스 0 에서값 5 발견숫자비교횟수 = 1 인덱스 9 에서값 43 발견숫자비교횟수 = 10 인덱스 5 에서값 26 발견숫자비교횟수 =

32 자료구조표기법

33 자료구조의 C 언어표현방법 자료구조와관련된데이터들을구조체로정의 연산을호출할경우, 이구조체를함수의파라미터로전달 예 ) // 자료구조스택과관련된자료들을정의 typedef int element; typedef struct { int top; element stack[max_stack_size]; } StackType; 자료구조의요소 관련된데이터를구조체로정의 // 자료구조스택과관련된연산들을정의 void push(stacktype *s, element item) { if( s->top >= (MAX_STACK_SIZE -1)){ stack_full(); return; } s->stack[++(s->top)] = item; } 연산을호출할때구조체를함수의파라미터로전달 33

34 자료구조기술규칙 (1/2) 상수 대문자로표기 예 ) #define MAX_ELEMENT 100 변수의이름 소문자를사용하였으며언더라인을사용하여단어와단어를분리 예 ) int increment; int new_node; 함수의이름 동사를이용하여함수가하는작업을표기 예 ) int add(listnode *node) // 혼동이없는경우 int list_add(listnode *node) // 혼동이생길우려가있는경우 34

35 자료구조기술규칙 (2/2) typedef 의사용 C 언어에서사용자정의데이터타입을만드는경우에쓰이는키워드 typedef < 새로운타입의정의 > < 새로운타입이름 >; ( 예 ) typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; 35

슬라이드 1

슬라이드 1 CHAP 1: 자료구조와알고리즘 일상생활에서의사물의조직화 조직도 일상생활에서의사물의조직화 Ticket Box 일상생활과자료구조의비교 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 자료구조 스택 큐 리스트 a b c NULL C B A 영어사전사전, 탐색구조 Ticket Box 지도 조직도 그래프 트리 전단 (front) 후단 (rear) 자료구조와알고리즘

More information

슬라이드 1

슬라이드 1 CHAP 1: 자료구조와알고리즘 C 로쉽게풀어쓴자료구조 생능출판사 2005 일상생활에서의사물의조직화 조직도 일상생활에서의사물의조직화 Ticket Box 일상생활과자료구조의비교 a b c N 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 자료구조 스택 큐 리스트 영어사전사전, 탐색구조 지도 조직도 그래프 트리 Ticket Box C B A 전단 (front)

More information

01장.자료구조와 알고리즘

01장.자료구조와 알고리즘 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 자료구조와알고리즘 1/30 자료구조 일상생활에서자료를정리하고조직화하는이유는? 사물을편리하고효율적으로사용하기위함 다양한자료를효율적인규칙에따라정리한예 2/30 컴퓨터에서의자료구조 자료구조 (Data Structure) 컴퓨터에서자료를정리하고조직화하는다양한구조

More information

슬라이드 1

슬라이드 1 Data Structure & Algorithms SANGJI University KO Kwangman () 자료 (data) 1. 자료와정보 현실세계로부터의단순한관찰이나측정을통하여수집한사실이나개념의값들또는값들의집합. 정보 (information) 의사결정에도움을주기위해유용한형태로다시작성된 (= 가공 ) 자료. Data Structure & Algorithms

More information

chap x: G입력

chap x: G입력 재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19) 이진검색의재귀알고리즘

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

02장.배열과 클래스

02장.배열과 클래스 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 배열과구조체 1/20 많은자료의처리? 배열 (array), 구조체 (struct) 성적처리프로그램에서 45 명의성적을저장하는방법 주소록프로그램에서친구들의다양한정보 ( 이름, 전화번호, 주소, 이메일등 ) 를통합하여저장하는방법 홍길동 이름 :

More information

chap01_time_complexity.key

chap01_time_complexity.key 1 : (resource),,, 2 (time complexity),,, (worst-case analysis) (average-case analysis) 3 (Asymptotic) n growth rate Θ-, Ο- ( ) 4 : n data, n/2. int sample( int data[], int n ) { int k = n/2 ; return data[k]

More information

Chapter 4. LISTS

Chapter 4. LISTS C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or

More information

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures 단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct

More information

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - ch07 - 포인터 pm0415 2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자

More information

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-chap06-Queue.ppt / 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해

More information

11장 포인터

11장 포인터 누구나즐기는 C 언어콘서트 제 9 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다. 첫번째바이트의주소는 0, 두번째바이트는 1, 변수와메모리

More information

Microsoft PowerPoint - chap-11.pptx

Microsoft PowerPoint - chap-11.pptx 쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.

More information

Microsoft PowerPoint - 08-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In

More information

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]

More information

중간고사

중간고사 중간고사 예제 1 사용자로부터받은두개의숫자 x, y 중에서큰수를찾는알고리즘을의사코드로작성하시오. Step 1: Input x, y Step 2: if (x > y) then MAX

More information

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경

More information

Chapter 4. LISTS

Chapter 4. LISTS 6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립

More information

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.

More information

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,

More information

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

untitled

untitled - -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front) A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top #define MAX_STACK_SIZE 100 int

More information

Chap 6: Graphs

Chap 6: Graphs 5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1) 5.1 AOV

More information

슬라이드 1

슬라이드 1 CHAP 2: 순환 (Recursion) 순환 (recursion) 이란? 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로 되어있는경우에적합한방법 순환 (recursion) 의예 팩토리얼값구하기 피보나치수열 1 n! n*( n 1)! fib( n) 0 1 fib( n 2) n n 0 ` 1 fib( n 1) if n 0 if

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임

More information

중간고사 (자료 구조)

중간고사 (자료 구조) Data Structures 215 중간고사 문제에서명시적으로기술하지않은부분은교재의내용에근거함. 215. 1. 27. 1 다음용어에대하여간단하게설명하시오 ( 각 3 점 *1=3 점 ) 1 abstract data type 6 Circular linked list 2 recursion 3 time complexity 4 space complexity 5 Single

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소

More information

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100 2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 연결리스트 (Linked List) 연결리스트연산 Stack

More information

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt 배열이란? Chapter. 배열구조체포인터 같은형의변수를여러개만드는경우에사용 int A, A, A, A,, A; int A[]; 4 5 6 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=;i tmp ) tmp = score[i]; Today...

More information

untitled

untitled int i = 10; char c = 69; float f = 12.3; int i = 10; char c = 69; float f = 12.3; printf("i : %u\n", &i); // i printf("c : %u\n", &c); // c printf("f : %u\n", &f); // f return 0; i : 1245024 c : 1245015

More information

2002년 2학기 자료구조

2002년 2학기 자료구조 자료구조 (Data Structures) Chapter 1 Basic Concepts Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3)

More information

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770> 연습문제해답 5 4 3 2 1 0 함수의반환값 =15 5 4 3 2 1 0 함수의반환값 =95 10 7 4 1-2 함수의반환값 =3 1 2 3 4 5 연습문제해답 1. C 언어에서의배열에대하여다음중맞는것은? (1) 3차원이상의배열은불가능하다. (2) 배열의이름은포인터와같은역할을한다. (3) 배열의인덱스는 1에서부터시작한다. (4) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.

More information

정보

정보 정보 Sangwook Lee Deogi High School III 문제해결과프로그래밍 1 추상화 2 알고리즘 3 프로그래밍 2 알고리즘 2-1 알고리즘설계 2-2 알고리즘분석 3 2-1 알고리즘설계 (p.108) 학습목표 순차, 선택, 반복구조의흐름을설명할수있다. 다양한제어구조를활용하여논리적이고효율적인알고리즘을설계할수있다. 4 [1] 알고리즘제어구조 (p.109)

More information

06장.리스트

06장.리스트 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :

More information

Microsoft PowerPoint - 제11장 포인터(강의)

Microsoft PowerPoint - 제11장 포인터(강의) 쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조

More information

5.스택(강의자료).key

5.스택(강의자료).key CHP 5: https://www.youtube.com/watch?v=ns-r91557ds ? (stack): (LIFO:Last-In First-Out):. D C B C B C B C B (element) C (top) B (bottom) (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=.

More information

03장.스택.key

03장.스택.key ---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():

More information

C 언어 프로그래밊 과제 풀이

C 언어 프로그래밊 과제 풀이 과제풀이 (1) 홀수 / 짝수판정 (1) /* 20094123 홍길동 20100324 */ /* even_or_odd.c */ /* 정수를입력받아홀수인지짝수인지판정하는프로그램 */ int number; printf(" 정수를입력하시오 => "); scanf("%d", &number); 확인 주석문 가필요한이유 printf 와 scanf 쌍

More information

OCW_C언어 기초

OCW_C언어 기초 초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음

More information

11장 포인터

11장 포인터 Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함

More information

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ 00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : (

More information

Microsoft PowerPoint - 제11장 포인터

Microsoft PowerPoint - 제11장 포인터 쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조

More information

1장. 리스트

1장. 리스트 01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef

More information

슬라이드 1

슬라이드 1 CHAP 3: 배열, 구조체, 포인터 C 로쉽게풀어쓴자료구조 Copyright 생능출판사 25 배열이란? 같은형의변수를여러개만드는경우에사용 int A, A, A2, A3,,A9; int A[]; 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=;i

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 순환알고리즘 C 로쉽게풀어쓴자료구조 순환 (recursion) 수행이끝나기전에자기자신을다시호출하여문제해결 - 직접순환, 간접순환 문제정의가순환적으로되어있는경우에적합한방법 ( 예제 ) 팩토리얼 피보나치수열 n! 1 n * ( n 1)! n n 0 fib( n) 1 fib ( n 2) fib( n 1) 1 ` 2 if if n 0 n 1 otherwise 이항계수

More information

본 강의에 들어가기 전

본 강의에 들어가기 전 C 기초특강 종합과제 과제내용 구조체를이용하여교과목이름과코드를파일로부터입력받아관리 구조체를이용하여학생들의이름, 학번과이수한교과목의코드와점수를파일로부터입력 학생개인별총점, 평균계산 교과목별이수학생수, 총점및평균을계산 결과를파일에저장하는프로그램을작성 2 Makefile OBJS = score_main.o score_input.o score_calc.o score_print.o

More information

슬라이드 1

슬라이드 1 CHAP 9: 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수 ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬의단위 레코드 정렬의대상 학생들의레코드 이름학번주소연락처 레코드 필드필드필드필드 키 (key) 정렬알고리즘의개요 많은정렬알고리즘존재 단순하지만비효율적인방법

More information

쉽게 배우는 알고리즘 강의노트

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,

More information

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Function) 1. 함수의개념 입력에대해적절한출력을발생시켜주는것 내가 ( 프로그래머 ) 작성한명령문을연산, 처리, 실행해주는부분 ( 모듈 ) 자체적으로실행되지않으며,

More information

Chap 6: Graphs

Chap 6: Graphs AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node

More information

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 제 8 장. 포인터 목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 포인터의개요 포인터란? 주소를변수로다루기위한주소변수 메모리의기억공간을변수로써사용하는것 포인터변수란데이터변수가저장되는주소의값을 변수로취급하기위한변수 C 3 포인터의개요 포인터변수및초기화 * 변수데이터의데이터형과같은데이터형을포인터 변수의데이터형으로선언 일반변수와포인터변수를구별하기위해

More information

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at

More information

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - 스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입

More information

Microsoft PowerPoint 알고리즘 개요(Part 1).pptx

Microsoft PowerPoint 알고리즘 개요(Part 1).pptx 알고리즘 (Algorithm) 알고리즘개요 ( 효율, 분석, 차수 ) Part 1 2011년봄학기 강원대학교컴퓨터과학전공문양세 강의내용 프로그램과알고리즘순차검색과이진검색피보나찌수구하기알고리즘분석차수 (O,, ) Part 2 Page 2 프로그램의설계과정 설계분석예문제알고리즘만족? 프로그램 아니오 재설계 알고리즘은주어진문제를논리적으로해결하는과정이다. 분석을통해작성한알고리즘의정확성을파악할수있고,

More information

금오공대 컴퓨터공학전공 강의자료

금오공대 컴퓨터공학전공 강의자료 C 프로그래밍프로젝트 Chap 14. 포인터와함수에대한이해 2013.10.09. 오병우 컴퓨터공학과 14-1 함수의인자로배열전달 기본적인인자의전달방식 값의복사에의한전달 val 10 a 10 11 Department of Computer Engineering 2 14-1 함수의인자로배열전달 배열의함수인자전달방식 배열이름 ( 배열주소, 포인터 ) 에의한전달 #include

More information

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.

More information

슬라이드 1

슬라이드 1 6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,

More information

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular

More information

제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 이중포인터란무엇인가? 포인터배열 함수포인터 다차원배열과포인터 void 포인터 포인터는다양한용도로유용하게활용될수있습니다. 2 이중포인터

More information

04장.큐

04장.큐 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 큐 1/33 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 A B C 전단 ( front) 후단 ( rea r) 2/33 큐 ADT 삽입과삭제는 FIFO

More information

Microsoft PowerPoint - chap11-포인터의활용.pptx

Microsoft PowerPoint - chap11-포인터의활용.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 포인터를 사용하는 다양한 방법에

More information

설계란 무엇인가?

설계란 무엇인가? 금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 6 강. 함수와배열, 포인터, 참조목차 함수와포인터 주소값의매개변수전달 주소의반환 함수와배열 배열의매개변수전달 함수와참조 참조에의한매개변수전달 참조의반환 프로그래밍연습 1 /15 6 강. 함수와배열, 포인터, 참조함수와포인터 C++ 매개변수전달방법 값에의한전달 : 변수값,

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Lecture 02 프로그램구조및문법 Kwang-Man Ko kkmam@sangji.ac.kr, compiler.sangji.ac.kr Department of Computer Engineering Sang Ji University 2018 자바프로그램기본구조 Hello 프로그램구조 sec01/hello.java 2/40 자바프로그램기본구조 Hello 프로그램구조

More information

슬라이드 1

슬라이드 1 -Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역

More information

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조

More information

untitled

untitled while do-while for break continue while( ) ; #include 0 i int main(void) int meter; int i = 0; while(i < 3) meter = i * 1609; printf("%d %d \n", i, meter); i++; return 0; i i< 3 () 0 (1)

More information

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx #include int main(void) { int num; printf( Please enter an integer "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; } 1 학습목표 을 작성하면서 C 프로그램의

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터

More information

KNK_C_05_Pointers_Arrays_structures_summary_v02

KNK_C_05_Pointers_Arrays_structures_summary_v02 Pointers and Arrays Structures adopted from KNK C Programming : A Modern Approach 요약 2 Pointers and Arrays 3 배열의주소 #include int main(){ int c[] = {1, 2, 3, 4}; printf("c\t%p\n", c); printf("&c\t%p\n",

More information

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7> 제14장 동적 메모리 할당 Dynamic Allocation void * malloc(sizeof(char)*256) void * calloc(sizeof(char), 256) void * realloc(void *, size_t); Self-Referece NODE struct selfref { int n; struct selfref *next; }; Linked

More information

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2 제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.

More information

K&R2 Reference Manual 번역본

K&R2 Reference Manual 번역본 typewriter structunion struct union if-else if if else if if else if if if if else else ; auto register static extern typedef void char short int long float double signed unsigned const volatile { } struct

More information

chap 5: Trees

chap 5: Trees Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection

More information

C 프로그래밊 개요

C 프로그래밊 개요 구조체 2009 년 5 월 19 일 김경중 강의계획수정 일자계획 Quiz 실습보강 5 월 19 일 ( 화 ) 구조체 Quiz ( 함수 ) 5 월 21 일 ( 목 ) 구조체저녁 6 시 5 월 26 일 ( 화 ) 포인터 5 월 28 일 ( 목 ) 특강 (12:00-1:30) 6 월 2 일 ( 화 ) 포인터 Quiz ( 구조체 ) 저녁 6 시 6 월 4 일 ( 목

More information

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE> 쉽게풀어쓴 C 언어 Express 제 17 장동적메모리와연결리스트 이번장에서학습할내용 동적메모리할당의이해 동적메모리할당관련함수 연결리스트 동적메모리할당에대한개념을이해하고응용으로연결리스트를학습합니다. 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것

More information

슬라이드 1

슬라이드 1 CHAP 5 : 스택 yicho@gachon.ac.kr 1 5.1 스택추상데이터타입 스택 (stack) 이란?: 쌓아놓은더미 2 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 3 스택의구조 요소 (element) 스택에저장되는것 C 스택상단 (top) : 스택에서입출력이이루어지는부분

More information

Microsoft PowerPoint - Chapter_08.pptx

Microsoft PowerPoint - Chapter_08.pptx 프로그래밍 1 1 Chapter 8. Pointers May, 2016 Dept. of software Dankook University http://embedded.dankook.ac.kr/~baeksj 포인터의개념 (1/6) 2 포인터란 : 다른객체를가리키는변수 객체의메모리주소를저장하는변수 기호적방식 (symbolic way) 으로주소사용 포인터와관련된연산자

More information

Microsoft PowerPoint - 제4장-스택과큐.pptx

Microsoft PowerPoint - 제4장-스택과큐.pptx 제 4 강의. 스택과큐자료구조 1 제 4 강. 스택과큐자료구조 학습목차 1. 스택과큐자료구조 2. 스택자료구조 3. 큐자료구조 4. 원형큐의구현 2 1. 스택 (Stack) 과큐자료구조 리스트, 스택과큐 (Stack and Queue) 스택과큐는리스트자료구조의특별한경우이다. 리스트 - 순서가있다 - 읽기, 삽입 (insert) 과삭제 (delete) 를리스트의어느곳에서나행함

More information

Microsoft PowerPoint - Chap1-전반부 [호환 모드]

Microsoft PowerPoint - Chap1-전반부 [호환 모드] 05666 데이터구조 (Data Structure) 2011 년봄학기 숙명여자대학교멀티미디어과학과 박영호 05666 데이터구조론강좌개요 담당교수 : 박영호 ( 내선 : 2077-7297, yhpark@sm.ac.kr, 새함관 508 호, 010-6417-5541) 강의시간 교재 : C 로쓴자료구조, 이석호역, 교보, 2008 년판 (Fundamentals of

More information

슬라이드 1

슬라이드 1 Recursion SANGJI University KO Kwangman () 1. 개요 재귀 (recursion) 의정의, 순환 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로되어있는경우에적합한방법 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색

More information

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 Data structure: Assignment 1 Seung-Hoon Na October 1, 018 1 1.1 Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 multiline으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될

More information

Microsoft PowerPoint - 제3장-배열.pptx

Microsoft PowerPoint - 제3장-배열.pptx 제 3 강. 배열 (Array) 자료구조 1 제 3 강. 배열자료구조 학습목차 1. 배열의개념 2. 구조체 3. 희소 (Sparce) 행렬 4. 다차원배열의저장 2 1. 배열의개념 리스트는일상생활에서가장많이쓰이는자료형태이다. 예 ) 학생의명단, 은행거래고객명단, 월별판매액등 배열 (Array) 은컴퓨터언어에서리스트를저장하는데이터타입이다. 리스트와배열은같은개념이지만다른차원의용어이다.

More information

Frama-C/JESSIS 사용법 소개

Frama-C/JESSIS 사용법 소개 Frama-C 프로그램검증시스템소개 박종현 @ POSTECH PL Frama-C? C 프로그램대상정적분석도구 플러그인구조 JESSIE Wp Aorai Frama-C 커널 2 ROSAEC 2011 동계워크샵 @ 통영 JESSIE? Frama-C 연역검증플러그인 프로그램분석 검증조건추출 증명 Hoare 논리에기초한프로그램검증도구 사용법 $ frama-c jessie

More information

JAVA PROGRAMMING 실습 08.다형성

JAVA PROGRAMMING 실습 08.다형성 2015 학년도 2 학기 1. 추상메소드 선언은되어있으나코드구현되어있지않은메소드 abstract 키워드사용 메소드타입, 이름, 매개변수리스트만선언 public abstract String getname(); public abstract void setname(string s); 2. 추상클래스 abstract 키워드로선언한클래스 종류 추상메소드를포함하는클래스

More information

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt 변수와상수 1 변수란무엇인가? 변수 : 정보 (data) 를저장하는컴퓨터내의특정위치 ( 임시저장공간 ) 메모리, register 메모리주소 101 번지 102 번지 변수의크기에따라 주로 byte 단위 메모리 2 기본적인변수형및변수의크기 변수의크기 해당컴퓨터에서는항상일정 컴퓨터마다다를수있음 short

More information

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint - chap06-2pointer.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.

More information

Microsoft PowerPoint - chap10-함수의활용.pptx

Microsoft PowerPoint - chap10-함수의활용.pptx #include int main(void) { int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; } 1 학습목표 중 값에 의한 전달 방법과

More information

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 #define _CRT_SECURE_NO_WARNINGS #include #include main() { char ch; printf(" 문자 1개를입력하시오 : "); scanf("%c", &ch); if (isalpha(ch))

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];

More information

ABC 10장

ABC 10장 10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;

More information

Microsoft PowerPoint - chap03-변수와데이터형.pptx

Microsoft PowerPoint - chap03-변수와데이터형.pptx #include int main(void) { int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num %d\n", num); return 0; } 1 학습목표 의 개념에 대해 알아본다.

More information

문서의 제목 나눔명조R, 40pt

문서의 제목  나눔명조R, 40pt 이문서는나눔글꼴로작성되었습니다. 설치하기 11차시 : 함수동적메모리할당다차원배열 프로그래밍및실험 제 11주 동국대학교조영석 6.6 함수인자로써의배열 - 함수정의에서배열로선언된형식매개변수는 pointer임. - 함수의인자로배열이전달되면배열의기본주소가 ( 배열의내용이아님 ) call-by-value로전달됨. - 배열원소는복사되지않음. 2 ( 예 ) #include

More information

PowerPoint Presentation

PowerPoint Presentation 자바프로그래밍 1 배열 손시운 ssw5176@kangwon.ac.kr 배열이필요한이유 예를들어서학생이 10 명이있고성적의평균을계산한다고가정하자. 학생 이 10 명이므로 10 개의변수가필요하다. int s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; 하지만만약학생이 100 명이라면어떻게해야하는가? int s0, s1, s2, s3, s4,

More information

1장. 유닉스 시스템 프로그래밍 개요

1장.  유닉스 시스템 프로그래밍 개요 Unix 프로그래밍및실습 7 장. 시그널 - 과제보충 응용과제 1 부모프로세스는반복해서메뉴를출력하고사용자로부터주문을받아자식프로세스에게주문내용을알린다. (SIGUSR1) ( 일단주문을받으면음식이완료되기전까지 SIGUSR1 을제외한다른시그널은모두무시 ) timer 자식프로세스는주문을받으면조리를시작한다. ( 일단조리를시작하면음식이완성되기전까지 SIGALARM 을제외한다른시그널은모두무시

More information

untitled

untitled if( ) ; if( sales > 2000 ) bonus = 200; if( score >= 60 ) printf(".\n"); if( height >= 130 && age >= 10 ) printf(".\n"); if ( temperature < 0 ) printf(".\n"); // printf(" %.\n \n", temperature); // if(

More information

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B62D DBFB5BBF3BCF6BEF72DC5E4BFE4C0CFBCF6BEF72E >

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B62D DBFB5BBF3BCF6BEF72DC5E4BFE4C0CFBCF6BEF72E > 1 장기본개념 1 자료와정보 컴퓨터 주기억장치 자료 정보 보조기억장치 자료, 프로그램 자료구조 자료저장, 이용알고리즘 프로그램 I = P(D) 2 자료구조의영역 3 자료구조 기본개념 선형구조 배열 ( 연속리스트 (continuous list) 스택 (stack), 큐 (queue) 연결리스트 (linked list) 비선형구조 트리 (tree), 그래프 (graph)

More information