1장. 리스트

Size: px
Start display at page:

Download "1장. 리스트"

Transcription

1 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리

2 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터

3 순차탐색 (sequential search) 탐색방법중에서가장간단하고직접적인탐색방법 정렬되지않은배열의항목들을처음부터마지막까지하나씩검사하여원하는항목을찾아가는방법 int seq_search(int key, int low, int high) { int i; for(i=low; i<=high; i++) if(list[i]==key) return i; // 탐색성공 return -1; // 탐색실패 }

4 순차탐색에서비교횟수를줄이기위해리스트의끝에찾고자하는키값을저장하고반복문의탈출조건을키값을찾을때까지로설정 int seq_search2(int key, int low, int high) { int i; list[high+1] = key; // 키값을찾으면종료 for(i=low; list[i]!= key; i++) } ; if(i==(high+1)) return -1; // 탐색실패 else return i; // 탐색성공

5 자기구성순차탐색 (Self-Organizing Sequential Search) 자주사용되는항목을데이터집합의앞쪽에배치함으로써순차탐색의검색효율을끌어올리는방법 전진이동법 (Move To Front) 전위법 (Transpose) 빈도계수법 (Frequency Count)

6 전진이동법 (Move to front method) 어느항목이한번탐색되고나면, 그항목을데이터집합의가장앞 ( 링크드리스트에서는헤드 ) 에위치시키는방법

7 전위법 (Transpose method) 탐색된항목을바로이전항목과교환한다는것말고는기본적으로전진이동법과같은전략을취하는알고리즘

8 계수법 (Frequency count method) 데이터집합내의각요소들이탐색된횟수를별도의공간에저장해두고, 탐색된횟수가높은순으로데이터집합을재구성 계수결과를저장하는별도의공간을유지해야하고계수결과에따라데이터집합을재배치해야한다.

9 정렬된데이터집합에서사용할수있는 고속 탐색알고리즘 데이터집합의중앙에있는요소선택 중앙요소의값과찾고자하는목표값을비교 목표값이중앙요소의값보다작다면중앙을기준으로데이터집합의왼편에대 해새로검색을수행하고크다면오른편에대해이진탐색을새로이수행 찾고자하는값을찾을때까지 1 번 ~3 번과정을반복

10 배열의중앙에있는값을조사하여찾고자하는항목이왼쪽또는오른쪽부분배열에있는지를알아내어탐색의범위를반으로줄인다. ( 예 ) 10억명중에서이진탐색을이용하여특정한이름을탐색 이진탐색은단지 30번의비교 순차탐색에서는평균 5억번의비교 5 을탐색하는경우 영어사전 ⅹ 7과비교 < 7이므로앞부분만을다시탐색 를 3과비교 > 3 이므로뒷부분만을다시탐색 ==5 이므로탐색성공

11 이진탐색예

12 search_binary(list, low, high) middle low 에서 high 사이의중간위치 if( 탐색값 list[middle] ) return TRUE; else if ( 탐색값 < list[middle] ) return list[0] 부터 list[middle-1] 에서의탐색 ; else if ( 탐색값 > list[middle] ) return list[middle+1] 부터 list[high] 에서의탐색 ;

13 이진탐색의성능 탐색대상의범위 : ½ ¼ 1/16 Let n : 데이터집합의크기 x : 탐색반복횟수 1 = n x (1/2) x x = log 2 n 100 만개의데이터집합 : 최대 20 회 1000 만개의데이터집합 : 최대 23 회

14 이진탐색의구현 ElementType BinarySearch(ElementType DataSet[], int Size, ElementType Target) { int Left, Right, Mid; Left = 0; Right = Size - 1; while ( Left <= Right ) { Mid = (Left + Right) / 2; } if ( Target == DataSet[Mid] ) return DataSet[Mid]; else if ( Target > DataSet[Mid] ) Left = Mid + 1; else Right = Mid - 1; } return NULL;

15 C 표준라이브러리의이진탐색함수 bsearch() void *bsearch( const void *key, /* 찾고자하는목표값데이터의주소 */ const void *base, /* 데이터집합배열의주소 */ size_t num, /* 데이터요소의개수 */ size_t width, /* 한데이터요소의크기 */ int ( cdecl *compare)(const void *, const void *) /* 비교함수에대한포인터 */ );

16 각노드가다음규칙을따르는이진트리 왼쪽자식노드는부모보다작고, 오른쪽자식노드는부모보다크다 이진탐색트리의예

17 이진탐색 (binary search) vs. 이진탐색트리 (binary search tree) 근본적으로같은원리에의한탐색구조 이진탐색은배열에저장된데이터를탐색 동적으로크기가변하는데이터집합탐색에는부적합 삽입과삭제가상당히힘들다. 이진탐색트리는연결리스트데이터에대한탐색 비교적빠른시간안에삽입과삭제를끝마칠수있는구조 삽입, 삭제가빈번히이루어진다면반드시이진탐색트리를사용하여야한다. 이진탐색트리에서의시간복잡도 균형트리 : O(logn) 불균형트리 : O(n), 순차탐색과동일

18 이진탐색트리의연산 노드탐색 노드삽입 노드삭제

19 이진탐색트리에서의이진탐색 > <

20 이진탐색트리에서의노드삽입

21 이진탐색트리에서의노드삭제 #1 삭제할노드가잎노드인경우

22 이진탐색트리에서의노드삭제 #2 삭제할노드가잎노드가아닌경우 && 왼쪽 / 오른쪽중어느한쪽자식노드만갖고있는경우 23 삭제된노드의부모노드가삭제된노드의자식을가리키게합니다

23 이진탐색트리에서의노드삭제 #3 삭제할노드가잎노드가아닌경우 && 양쪽자식노드를모두갖고있는경우 삭제 최소값노드

24 문제 : 순수이진탐색트리는다음과같은모습을가질수있게되며, 이때탐색효율은극도로떨어진다. 해결책 : 트리가균형잡힌모습으로자라도록하는알고리즘

25 레드블랙트리 : 모든노드가검은색또는붉은색 다음의규칙을가진다. 1. 모든노드는빨간색아니면검은색이다. 2. 루트노드는검은색이다. 3. 잎노드는검은색이다. 4. 빨간노드의자식들은모두검은색이다 ( 하지만검은색노드의자식이빨간색일필요는없다.). 5. 루트노드에서모든잎노드사이에있는검은색노드의수는모두동일하다.

26 레드블랙트리의예 4. 빨간노드의자식들은모두검은색이다 2. 루트노드는검은색이다. NIL NIL NIL NIL NIL NIL 5. 루트노드에서모든잎노드사이에있는검은색노드의수는모두동일하다. NIL NIL 3. 잎노드는모두검은색이다.

27 레드블랙트리의구현예

28 노드색상전환 (Color Flipping) 노드의색상을바꾸는연산 노드회전 (Rotation) 8 우회전 좌회전 6 9 우회전을할때에는왼쪽자식노드의오른쪽자식노드를부모노드의왼쪽자식으로연결한다. 좌회전을할때에는오른쪽자식노드의왼쪽자식노드를부모노드의오른쪽자식으로연결한다.

29 레드블랙트리연산 노드탐색연산 노드삽입연산 노드삭제연산 노드탐색연산 이진탐색트리에서의노드탐색연산과동일 이진탐색트리에대한중위순회 ( in-order traversal)

30 노드삽입연산 레드블랙트리의노드삽입연산 1 이진탐색트리의노드삽입연산을수행한다. 2 새노드를빨간색으로칠하고양쪽자식에 NIL 을연결한다. 3 무너진레드블랙트리규칙을고치기위해트리를재구성한다. 삽입연산후에어긋나는레드블랙트리규칙 루트노드는검은색이어야한다. 빨간색노드의자식노드들은검은색이어야한다.

31 노드삽입연산의후처리 (1) 빨간색노드의자식은검은색이어야한다 는규칙을복원 가정 : 부모노드가빨간색이고할아버지노드의왼쪽자식인경우 다음의 3 가지경우로나누어해결 삼촌노드도빨간색인경우 삼촌노드는검은색이고, 삽입노드가부모노드의오른쪽자식인경우 삼촌노드는검은색이고, 삽입노드가부모노드의왼쪽자식인경우

32 노드삽입연산의후처리 (2) 삼촌노드도빨간색인경우

33 노드삽입연산의후처리 (3) 삼촌노드는검은색이고, 삽입노드가부모노드의오른쪽자식인경우 세번째경우로전환

34 노드삽입연산의후처리 (4) 삼촌노드는검은색이고, 삽입노드가부모노드의왼쪽자식인경우

35 노드삭제연산 레드블랙트리의노드삭제연산 1 이진탐색트리의노드삭제연산을수행한다. 2 무너진레드블랙트리규칙을고치기위해트리를재구성한다. 삭제노드의색깔이빨간색인경우 레드블랙트리규칙이그대로보전된다 별도의후처리가필요없음 삭제노드의색깔이검은색인경우 다음의레드블랙트리규칙이무너질수있다. 1 빨간색노드의자식은검은색이어야한다. 2 루트노드에서잎노드까지의모든경로에서검은색노드수는동일하여야한다.

36 노드삭제연산의후처리 (1) 빨간색노드의자식은검은색이어야한다 규칙복원 삭제노드의자식은삭제노드의색상속성을상속한다

37 노드삭제연산의후처리 (2) 삭제노드와삭제후이동하는노드모두검은색인경우 5 번위반을 1 번위반으로전환하여문제를축소

38 노드삭제연산의후처리 (3) (1) 이중흑색노드의형제노드가빨간색인경우

39 노드삭제연산의후처리 (4) (2) 이중흑색노드의형제노드가검은색이고, 형제노드의양쪽자식이모두검은색인경우

40 노드삭제연산의후처리 (5) (3) 이중흑색노드의형제노드가검은색이고, 형제노드의왼쪽자식은빨간색이고오른쪽자식은검은색인경우 넷번째경우로전환

41 노드삭제연산의후처리 (6) (4) 이중흑색노드의형제노드가검은색이고, 형제노드의오른쪽자식은빨간색인경우

42 Adelson-Velskii와 Landis에의해 1962년에제안된트리각노드에서왼쪽서브트리의높이와오른쪽서브트리의높이차이가 1 이하인이진탐색트리 트리가비균형상태로되면스스로노드들을재배치하여균형상태로만든다. AVL 트리는균형트리가항상보장되기때문에탐색이 O(logn) 시간안에끝나게된다. 균형인수 (balance factor)=( 왼쪽서브트리의높이 - 오른쪽서브트리의높이 ) 모든노드의균형인수가 ±1 이하이면 AVL 트리이다.

43 탐색연산 : 이진탐색트리와동일균형을이룬이진탐색트리에서균형상태가깨지는것은삽입연산과삭제연산시이다. 삽입연산시에는삽입되는위치에서루트까지의경로에있는조상노드들의균형인수에영향을줄수있다. 새로운노드의삽입후에불균형상태로변한가장가까운조상노드, 즉균형인수가 ±2가된가장가까운조상노드의서브트리들에대하여다시균형을잡아야한다.

44 균형트리로만드는방법 : 회전 (rotation) AVL 트리에서균형이깨지는경우에는다음의 4 가지의경우가있다. 새로삽입된노드 N 로부터가장가까우면서균형인수가가된조상노드를 A 라고하자. LL 타입 : N 이 A 의왼쪽서브트리의왼쪽서브트리에삽입된다. LR 타입 : N 이 A 의왼쪽서브트리의오른쪽서브트리에삽입된다. RR 타입 : N 이 A 의오른쪽서브트리의오른쪽서브트리에삽입된다. RL 타입 : N 이 A 의오른쪽서브트리의왼쪽서브트리에삽입된다.

45

46

47 LL 회전 :A 부터 N 까지의경로상의노드들을오른쪽으로회전시킨다. LR 회전 : A 부터 N 까지의경로상의노드들을왼쪽 - 오른쪽으로회전시킨다. RR 회전 : A 부터 N 까지의경로상의노드들을왼쪽으로회전시킨다. RL 회전 : A 부터 N 까지의경로상의노드들을오른쪽 - 왼쪽으로회전시킨다.

48

49

50

Microsoft PowerPoint - 6장 탐색.pptx

Microsoft PowerPoint - 6장 탐색.pptx 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

1장. 리스트

1장. 리스트 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 05. AVL 트리 06. B- 트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리,

More information

슬라이드 1

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

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

14장.탐색

14장.탐색 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 탐색 1/28 탐색 (search) 이란? 여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열,

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

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

슬라이드 1

슬라이드 1 CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소

More information

Microsoft PowerPoint - lec07_tree [호환 모드]

Microsoft PowerPoint - lec07_tree [호환 모드] Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만

More information

Microsoft PowerPoint - chap10_tree

Microsoft PowerPoint - chap10_tree Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-

More information

7장

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

More information

08장.트리

08장.트리 ---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조

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

Ch.1 Introduction

Ch.1 Introduction Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?

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

제 11 장 다원 탐색 트리

제 11 장 다원 탐색 트리 제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산

More information

슬라이드 1

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

More information

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 트리의개념 트리 (Tree) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 정의 (1) 하나의루트 (root) 노드 (2) 다수의서브트리 (subtree) 트리는부모-자식관계의노드들로이루어짐

More information

제 1 장 기본 개념

제 1 장 기본 개념 이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)

More information

05_tree

05_tree Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical

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

1장. 리스트

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

More information

입학사정관제도

입학사정관제도 자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)

More information

Chapter 08. 트리(Tree)

Chapter 08. 트리(Tree) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예

More information

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

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

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

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드,

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드, Tree & Heap SANGJI University Kwangman Ko kkman@sangji.ac.kr - 1 - o 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 - 2 - o 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.

More information

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table 쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table http://academy.hanb.co.kr 6장. 해시테이블 테이블 Hash Table 사실을많이아는것보다는이론적틀이중요하고, 기억력보다는생각하는법이더중요하다. - 제임스왓슨 - 2 - 학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 13 장. 균형탐색트리 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 균형 균형 2 AVL G. M. Adelson-Velskii and

More information

Microsoft PowerPoint - 제8장-트리.pptx

Microsoft PowerPoint - 제8장-트리.pptx 제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E > 제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다

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

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

Algorithms

Algorithms 자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것

More information

C 언어 강의노트

C 언어 강의노트 C언어 (CSE2035) (15-1 Lists) Linear list 의구성, Insertion, deletion 윤용운, Ph.D. Dept. of Computer Science and Engineering Sogang University Seoul, Korea Tel: 010-3204-6811 Email : yuyoon0@sogang.ac.kr 2018-01-11

More information

06장.리스트

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

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 균형탐색트리 13 장. 균형탐색트리 트리의작업효율을높이기위한다양한균형트리알고리즘을비교 학습목표 트리의균형이효율에미치는영향을이해한다. AVL 트리에서균형을회복하기위한방법을이해한다. 스플레이기법을이해한다. 2-3 트리에서균형을회복하기위한방법을이해한다. 2-3-4 트리와레드블랙트리의관계를이해한다. 1 Section 01 AVL 트리 - 균형 균형 2 AVL G.

More information

e-비즈니스 전략 수립

e-비즈니스 전략 수립 트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104 1. 트리 트리 (tree) 원소들간에 1:

More information

슬라이드 1

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

More information

슬라이드 1

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

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

11장 포인터

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

More information

Microsoft PowerPoint - 자료구조2008Chap07

Microsoft PowerPoint - 자료구조2008Chap07 제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint

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

제 10 장 최적 이원 탐색 트리

제 10 장 최적 이원 탐색 트리 제 1 장 최적이원탐색트리 Copyright 27 DBLAB, Seoul National University 최적이원탐색트리 (1/11) 개요 정적원소들의집합에대한이원탐색트리구조 삽입이나삭제는하지않고탐색만수행 정렬된리스트 함수 Get( 프로그램 5.19 참고 ) 이용 비용측정방법 함수 Get 이용 for 루프를 l 번반복 1 5 15 리스트 (5,1,15)

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 3. 트리 3.1 트리의개요 3.2 이진트리 3.3 트리의운행 3.1 트리의개요 트리 : 그래프의일종 데이터 : 노드 순환적정의 T = {R, T 1,T 2, T n } R : 루트 T i : 서브-트리 ( 트리 ) 3.1 트리의개요 1. 노드 2. 근노드 3. 서브트리 4. 차수 5. 단노드 6. 간노드 (nonterminal node) 7. 부-노드,

More information

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1

More information

Algorithms

Algorithms 자료구조 & 알고리즘 정렬과탐색알고리즘 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 기초적인정렬알고리즘 고급정렬알고리즘 탐색알고리즘 2 정 렬 (Sort) 정렬 (sort) 의개념 순서없이배열되어있는자료들을재배열하는것 정렬의대상 : 레코드 정렬의기준 : 정렬키 (sort key) 필드 정렬방법의분류

More information

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D> 연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다.

More information

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ

1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ Linked List 2010 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트

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

Microsoft PowerPoint - chap4_list

Microsoft PowerPoint - chap4_list Chap. 4 : 리스트 (list) 2007 학년도 2 학기 리스트 1. 리스트개념 ~ 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 ~ 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 ~ 요일 : ( 일요일, 월요일,, 토요일 ) ~ 한글자음의모임 : (ᆨ,ᆫ,,ᄒ) ~ 핸드폰의문자메시지리스트

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

Microsoft PowerPoint - 5장 정렬

Microsoft PowerPoint - 5장 정렬 01. 버블 02. 삽입 03. 퀵 04. C 표준 라이브러리의 퀵 정렬 정렬 정렬 정렬 함수 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적이다. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬은왜하는가? 학생들의레코드 이름학번주소연락처 레코드 필드 필드 필드 필드

More information

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센

리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센 Linked List 2014 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트

More information

슬라이드 1

슬라이드 1 Linked List 2015 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 10 장. 트리 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색,

More information

슬라이드 1

슬라이드 1 컬렉션프레임워크 (Collection Framework) 의정의 - 다수의데이터를쉽게처리할수있는표준화된방법을제공하는클래스들 - 데이터의집합을다루고표현하기위한단일화된구조 (architecture) - JDK 1.2 이전까지는 Vector, Hashtable, Properties와같은컬렉션클래스로서로다른각자의방식으로처리 - 컬렉션프레임워크는다수의데이터를다루는데필요한다양하고풍부한클래스들을제공하므로프로그래머의부담을상당부분덜어준다.

More information

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li

리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li Linked List 2011 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트

More information

쉽게배우는알고리즘 5 장. 검색트리 IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1

쉽게배우는알고리즘 5 장. 검색트리   IT COOKBOOK 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 한빛미디어 1 쉽게배우는알고리즘 5 장. 검색트리 htt://academy.hanb.co.k 5 장. 검색트리 나는보다응용력있는유형의수학이라는이유때문에컴퓨터과학을하고싶었다. - 로버트타잔 - 2 - 한빛미디어 1 학습목표 검색에서레코드와키의역할을구분한다. 이진검색트리에서의검색 삽입 삭제작업의원리를이해한다. 이진검색트리의균형이작업의효율성에미치는영향을이해하고, 레드블랙트리의삽입

More information

Microsoft PowerPoint - 제9장-트리의응용.pptx

Microsoft PowerPoint - 제9장-트리의응용.pptx 제 9 강의. 트리의탐색 1. 이진트리탐색알고리즘 2. 쓰레드 (Threaded) 이진트리 3. 이진트리를다루는알고리즘 1 1. 이진트리탐색알고리즘 트리의탐색 (traversal) 은트리의각노드를방문하는작업을말한다. ( 왜방문할까요?) 다음과같은방법들을생각해볼수있다. 방법 1) 레벨순 : 레벨이낮은순으로방문 A B C D E F G H 3가지다른방법이나올수있다.

More information

Chapter 4. LISTS

Chapter 4. LISTS 연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는

More information

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

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

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

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 트리 10 장. 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색,

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

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

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

More information

v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su

v 이원탐색트리 (binary search tree) u 인덱스를조직하는한가지방법 u 이진트리 (binary tree) 유한한수의노드를가진트리 공백 (empty) 이거나루트와두개의분리된이진트리즉, 왼쪽서브트리 (left subtree) 와오른쪽서브트리 (right su 6장인덱스구조 v 인덱스 (index) u 특징 화일의레코드들에대한효율적접근을위한조직 < 키값, 레코드주소 ( 포인터 )> 쌍으로구성 u 종류 키값의유형에따른인덱스 기본인덱스 (primary index) : 키값이기본키인인덱스 보조인덱스 (secondary index) : 기본인덱스이외의인덱스 화일조직에따른인덱스 집중인덱스 (clustered index) :

More information

02장.배열과 클래스

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

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 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템

More information

PowerPoint 프레젠테이션

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

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)

More information

설계란 무엇인가?

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

More information

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입

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

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

09J1_ _R.hwp

09J1_ _R.hwp 상수삽입전이시간을가지는양단우선순위큐 217 DOI: 10.3745/KIPSTA.2009.16-A.3.217 상수삽입전이시간을가지는양단우선순위큐 정해재 요 약 우선순위큐는스케줄링, 정렬, 유전자검색과같은우선순위에따른검색, 최단거리계산과같은응용에사용될수있다. 본논문에서제안하는배열을이용한양단우선순위큐자료구조는삽입과삭제연산에각각 O(1) 전이시간과 O(logn) 시간이걸린다.

More information

EA0015: 컴파일러

EA0015: 컴파일러 5 Context-Free Grammar 무엇을공부하나? 앞에서배운 " 정규식 " 은언어의 " 어휘 (lexeme)" 를표현하는도구로사용되었다. 언어의 " 구문 (syntax)" 은 " 정규언어 " 의범위를벗어나기때문에 " 정규식 " 으로표현이불가능하다. 본장에서배우는 " 문맥자유문법 " 은언어의 " 구문 (syntax)" 을표현할수있는도구이다. 어떤 " 문맥자유문법

More information

Microsoft PowerPoint - 07-chap05-Stack.ppt

Microsoft PowerPoint - 07-chap05-Stack.ppt / 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070> #include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0

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

문제여섯사람이일곱개의발판위에있다. 빈발판을중심으로세사람은왼쪽에서가운데를보고서있고, 다른세사람은오른쪽에서가운데를보고서있다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 1 / 35 목표왼쪽에서있던세사람을오른쪽으로, 오른쪽에서있던사람을왼쪽으로이동한다. 가운데발판은여전히비어있어야한다. 최소의움직임으로목표를달성하도록한다.

More information

Microsoft PowerPoint - chap-11.pptx

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

More information

Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레

Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레 Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레드 블랙 트리를 구현하고자 한다. 1.1 2-3트리와 동등한 레드 블랙 트리 2-3트리와 동등한

More information

11강-힙정렬.ppt

11강-힙정렬.ppt 11 (Heap ort) leejaku@shinbiro.com Topics? Heap Heap Opeations UpHeap/Insert, DownHeap/Extract Binary Tree / Index Heap ort Heap ort 11.1 (Priority Queue) Operations ? Priority Queue? Priority Queue tack

More information

WISHBONE System-on-Chip Interconnection Architecture for Portable IP Cores

WISHBONE System-on-Chip Interconnection Architecture for Portable IP Cores 프로젝트정리 1주차 : 미로를텍스트파일로만들어출력하는프로그램작성. 2주차 : 텍스트형태의미로를 MC의그래픽기능을이용하여그리는프로그램작성. 3주차 : 미로에서길찾는프로그램작성. Dept. of CS, Sogang Univ. 1 DS를이용한미로길찾기문제 DS를이용한미로길찾기문제는 2주차까지설계한미로의출발점과도착점을연결하는가장짧은경로를탐색해출력하는문제이다. NxM

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

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

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 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

Microsoft PowerPoint - 자료구조2008Chap06

Microsoft PowerPoint - 자료구조2008Chap06 제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보

More information

Microsoft PowerPoint - chap06-1Array.ppt

Microsoft PowerPoint - chap06-1Array.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-1 참고자료 배열 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 배열의선언과사용 같은형태의자료형이많이필요할때배열을사용하면효과적이다. 배열의선언 배열의사용 배열과반복문 배열의초기화 유연성있게배열다루기 한빛미디어

More information

5 장 트 리

5 장  트 리 5 장 트리 Copyright 2007 DBLAB, Seoul National University 트리구조 Copyright 2007 DBLAB, Seoul National University 2 트리 트리 : 하나이상의노드 (node) 로이루어진유한집합 1 하나의루트 (root) 노드 2 나머지노드들은 n( 0) 개의분리집합 T 1, T 2,, T n 으로분할

More information