Microsoft PowerPoint - 04알고리즘

Size: px
Start display at page:

Download "Microsoft PowerPoint - 04알고리즘"

Transcription

1 이산수학 Discrete Mathematics 알고리즘 (Algorithm) 인천대학교컴퓨터공학과공학시인이숙이철호교수 모바일컴퓨팅연구실 호

2 상어가바다의절대제왕이된이유 출처 : 조영탁의행복한경영이야기 상어는물고기중유일하게부레가없다. 부레없는물고기는물속에서생존이불가능하다. 행동이매우불편하고, 조금만바다속에머물러있어도바닥으로가라앉아죽고만다. 상어는태어난순간부터죽을때까지끊임없이몸을움직여야했다. 에릭호퍼는말합니다. 불완전한열등동물인인간이자연계에서동물이상의존재가될수있었던것은약점을이점으로바꾸는비범한천재적재능덕분이었다. 주어진조건이아닌나의대응이결과를만듭니다. 힘겨운노력이쌓여상어는바다의절대제왕으로거듭났다. - 유대인생각공부 ( 쑤린지음 ) 에서 2

3 지난주에 어떤회사에근무하는 60 명의직원에게해외여행경험을물었다. 유럽여행을가본사람은 35 명, 동남아여행을가본사람은 28 명이었다. 해외여행을한번도가본적이없는사람은 5 명이었다. 동남아여행은가봤지만유럽여행을가본적없는사람은몇명일까? 유럽여행자 : A = 35 명동남아여행자 : B = 28 명전체 : U = 60 명 ~(A U B) = 5 명 A U B = U 5 = 55 명 A B = (A + B) (A U B ) = = 8 ~A = B - A B = 28 8 = 20 유럽만가본사람 : 27 동남아만가본사람 : 20 둘다가본사람 : A B = 8 그러므로여행경험자중유럽을가본적없는사람은 20 명 ( 즉동남아만가본사람 ) 유럽여행경험자 전체 60 명 A U A B 동남아여행 B 경험자 5명 3

4 오늘의강의목표 알고리즘 (Algorithm) - 알고리즘 - 탐색 (search) - 정렬 (sort) - 함수의증가 - 알고리즘복잡도 4

5 알고리즘이란? 알고리즘 (algorithm) : 컴퓨터프로그램으로특정한일을수행하는명령어의유한한순서있는집합 가장효율적인알고리즘을찾는것이중요 수학 문제를풀기위해정의나정리들을활용 컴퓨터 수행가능한효율적인알고리즘을사용 1830 년배비지 (Babbage) 와러브레이스 (Lovelace) 처음주창 1973 년컴퓨터과학자인크누스 (Knuth) 정립 컴퓨터프로그래밍의기술 (The Art of Computer Programming) 5

6 알고리즘 알고리즘 (algorithm) 특정문제를해결하기위해기술한일련의명령문 프로그램 (program) 알고리즘을컴퓨터가이해하고실행할수있는특정프로그래밍언어로표현한것표현 : 순서도 (flow chart), 유사코드 (pseudo code), 언어 (language) 6

7 알고리즘의주요특성 1) 입력 (input) : 문제를풀기위한입력 2) 출력 (output) : 문제를해결했을때답의출력 3) 명확성 (definiteness) : 각단계가실행된후에는결과가확정 ( 정의 ) 4) 정확성 (correctness) : 주어진문제를정확하게해결해야함 5) 유한성 (finiteness) : 유한횟수의명령이수행된후출력을만들어야 6) 효율성 (effectiveness) : 정확하면서도효율적으로유한시간내에수행 7) 일반성 (generality) : 요구되는형태의모든문제에적용 7

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

9 탐색 (search) 알고리즘 탐색 (search) 주어진파일또는원소들중에서어떤특정한원소를찾는것 선형 ( 순차 ) 탐색 (sequential search) : 원소들이정렬되어있지않을경우 원소들을처음부터비교하여찾는것 이진탐색 (binary search) : 원소들이정렬되어있을경우 순차탐색보다빠름배열가운데의원소값과찾으려는값을비교하여, 비교된결과에따라왼쪽원소의배열또는오른쪽원소의배열중에서다시찾기를계속함 9

10 선형탐색 (sequential search) 10

11 이진탐색 (binary search) 11

12 이진탐색 (binary search) 예제 3-page 220 1, 2, 3, 5, 6, 7, 8, 10, 12,13,15,16,18,19,20,22 19를찾음??? 1. 두개로나눔 a) 1, 2, 3, 5, 6, 7, 8, 10 b) 12,13,15,16,18,19,20,22 2. 찾으려는 19와 a) 의가장마지막큰항과비교하면 19가큼으로 b) 를둘로쪼개서탐색 c) 12,13,15,16 d) 18,19,20,22 3. c) 의마지막항과 19 를비교하여크므로 d) 를둘로나누어탐색 e) 18,19 f) 20,22 4. e) 의마지막항과 19 를비교, 크지않으므로둘로나눔 g) 18 h) 탐색하려는 19 가 g) 의 18 보다크므로 h) 항으로탐색 6. 탐색처음포이트가끝포이트보다작지않으며, 19 와같은지를비교하여, 같으면탐색결과를찾았다고보고. 12

13 분할정복알고리즘 (divide and conquer algorithms) 그대로해결할수없는문제를작은문제로분할하여, 문제를해결하는방법이나알고리즘알고리즘이효율적인이유 큰문제를작은문제로나누어서해결할수있음 13

14 정렬 (sort) 알고리즘 임의로나열되어있는데이터주어진항목에따라크기순서대로작은순서부터 ( 오름차순, ascending order) 또는큰순서부터 ( 내림차순, descending order) 늘어놓는것 정렬되어있는데이터들은다음과같은작업을수행할때응용 (1) 데이터를탐색할때 (2) 리스트 (list) 에있는다른항목들을비교할때 14

15 버블정렬 (bubble sort) 15

16 삽입정렬 (insert sort) 예제 5 : 3, 2, 4, 1, 5 1) [3] 과앞의원소처음부터비교 : 3, [2], 4, 1, 5 2, [3], 4, 1, 5 2) [4] 와앞의원소처음부터비교 : 2, 3, [4], 1, 5 2, 3, [4], 1, 5 3) [1] 과앞의원소처음부터비교 : 2, 3, 4, [1], 5 1, 2, 3, 4, [5] 4) [5] 와앞의원소처음부터비교 : 1, 2, 3, 4, [5] 1, 2, 3, 4, 5 16

17 욕심쟁이알고리즘 (greedy algorithm) 최적해문제 매선택에서지금당장의순간에최적인해를수행 전체적으로최적해가아닐수있음 17

18 욕심쟁이알고리즘 (greedy algorithm) 예제 6 거스름돈문제 25 센트, 10 센트, 5 센트, 1 센트동전으로가장적은수의동전을사용하여 67 센트를거슬러주는방법 1) = 42 센트 25 센트 1 개 2) = 17 센트 25 센트 1 개 3) = 7 센트 10 센트 1 개 4) 7 5 = 2 센트 5 센트 1 개 5) 2 1 = 1 센트 1 센트 1 개 6) 1-1 = 0 센트 1 센트 1 개전체해 ) 25 센트 2 개, 10 센트 1 개, 5 센트 1 개, 1 센트 2 개 18

19 욕심쟁이알고리즘 (greedy algorithm) 예제 6 거스름돈문제 25 센트, 10 센트, (5 센트 : 사용안함 ), 1 센트동전으로가장적은수의동전을사용하여 30 센트를거슬러주는방법 1) = 5센트 25센트 1개 2) 5 1 = 4센트 1센트 1개 3) 4 1 = 3센트 1센트 1개 4) 3 2 = 2센트 1센트 1개 5) 2 1 = 1센트 1센트 1개 6) 1-1 = 0센트 1센트 1개 전체해 ) 25센트 1개, 1센트 5개 전체 6개사용 그러나 10센트 3개로해결가능 19

20 정렬알고리즘 퀵정렬 (quick sort) - 분할정복방법을통해리스트를정렬 - 리스트가운데서하나의원소를고름 ( 피벗 ) - 피벗앞에는피벗보다값이작은모든원소들이오고, 피벗뒤에는피벗보다값이큰모든원소들이오도록피벗을기준으로리스트를둘로나눔 ( 분할 ) - 분할을마친뒤에피벗은더이상움직이지않는다. - 분할된두개의작은리스트에대해 - 재귀 (Recursion) 적으로이과정을반복 - 재귀는리스트의크기가 0 이나 1 이될때까지반복 - 재귀호출이한번진행될때마다최소한하나의원소는최종적으로위치가정해짐. 20

21 정렬알고리즘 병합정렬 (merge sort) 리스트의길이가 0 또는 1 이면이미정렬된것 정렬되지않은리스트를절반으로잘라비슷한크기의두부분리스트로나눔 각부분리스트를재귀적으로합병정렬 두부분리스트를다시하나의정렬된리스트로합병 21

22 정렬알고리즘 힙정렬 (heap sort) 1) n 개의노드에대한완전이진트리를구성루트노드부터부노드, 왼쪽자노드, 오른쪽자노드순으로구성 2) 최대힙을구성최대힙이란부노드가자노드보다큰트리를말함단말노드를자노드로가진부노드부터구성아래부터루트까지올라오며순차적으로만들어감 3) 가장큰수 ( 루트에위치 ) 를가장작은수와교환 4) 2) 와 3) 을반복한다. 힙 (heap) : 최댓값및최솟값을찾아내는연산을빠르게하기위해고안된완전이진트리 (Complete binary tree) 를기본으로한자료구조 (treebased structure) 22

23 알고리즘의복잡도 시간복잡도 (time complexity) 알고리즘수행시간분석결과 공간복잡도 (space complexity) 알고리즘의메모리사용량에대한분석결과 23

24 알고리즘복잡도 O(1) : 상수 (constant) O(log n) : 로그 (logarithmic) O(n) : 1차 (linear) O(n log n) : 선형연산 (linear-arithmetic) O(n 2 ) : 2차 (quadratic) O(n 3 ) : 3차 (cubic) O(2 n ) : 지수 (exponential) O(n!) : factorial 24

25 알고리즘복잡도 big-o 추정에따른함수들의증가그래프 함수의증가값 N 값 25

26 차수그래프 상한값표시하한값표시중간값표시 26

27 함수의증가 ( 복잡도 ) big-o 표기 : 최악의경우복잡도 ( 상한선표기법 ) big-omega 최선의복잡도 ( 하한선표기법 ) big-theta 평균복잡도 27

28 big-o 표기법 최악의경우복잡도 ( 상한선표기법 ) 임의의함수에대하여 " 함수의입력값 ( 정의역의원소 ) 이커짐에따라그출력값 ( 그원소의상 ) 이얼마나빠르게커지는가 " 를표현 28

29 big-omega 표기법 최선의복잡도 ( 하한선표기법 ) big-theta 표기법평균복잡도 29

30 big-o 표기법 ( 상한표기법 ) 어떤함수 g(n) 이 O(n 2 ) 에속한다는말은함수 g(n) 이임의의 N 값보다큰값에대하여어떤 2차함수 cn 2 보다는작은값을가지게된다는의미 그래프상에서아래에위치한다는의미 즉그함수 g(n) 은어떤 2차함수 cn 2 보다는궁극적으로좋다는의미 30

31 big-o 표기의예 ( 예제 1-page 234) 보이라 은 임을 풀이 ) x >1 일때, x < x 2 이고 1 < x 2 이다 x > 1에서 (C = 4, k=1) x > 2 에서 (C = 3, k=2) Big O 를보이는데단지한가지해답이있는것이아니다. 적당히큰 k 과 C 를선택하여풀면된다. 31

32 big-omega( ) ( 하한표기법 ) 어떤함수 g(n) 이 (n 2 ) 에속한다는말은그함수는궁극에가서는어떤임의의 N 값보다큰값에대해서는어떤 2차함수cn 2 의값보다는큰값을가지게된다는것을의미 그래프상에서는윗부분에위치 그함수g(n) 은어떤2차함수cn 2 보다는궁극적으로나쁘다는의미 32

33 big-theta 표기법 함수 f(n) 에대해서 (f(n)) = O(f(n)) (f(n)) 의관계가성립즉, n N 인모든정수n에대해서 c f(n) g(n) d f(n) 이성립하는실수 c 0와 d 0, 그리고음이아닌정수 N이존재 33

34 쉬어가는시간 1 g 또하나의천칭문제??? 1 g 단위로자를수있는 40 g 짜리분동이있다. 이것을잘라서 1 ~ 40 g까지무게를측정하려한다. 40 g짜리분동을가장적은수의토막으로잘라만들려면어떻게잘라야할까? (40 개 ) 이름, 학번, 답과이유를설명 1 g 짜리 40 개가위와같이있다. 어떻게잘라야할까? 34

Microsoft PowerPoint - 04알고리즘

Microsoft PowerPoint - 04알고리즘 이산수학 Discrete Mathematics 알고리즘 (Algorithm) 인천대학교컴퓨터공학과공학시인이숙이철호교수 Jullio@chol.com zullio@inu.ac.kr 010 3957 6683 모바일컴퓨팅연구실 07 401 호 상어가바다의절대제왕이된이유 출처 : 조영탁의행복한경영이야기 상어는물고기중유일하게부레가없다. 부레없는물고기는물속에서생존이불가능하다.

More information

Microsoft PowerPoint - 05알고리즘.pptx

Microsoft PowerPoint - 05알고리즘.pptx 이산수학 Discrete Mathematics 알고리즘 (Algorithm) 인천대학교컴퓨터공학과공학시인이숙이철호교수 Jullio@chol.com zullio@inu.ac.kr 010 3957 6683 모바일컴퓨팅연구실 07 401 호 꿈의중독자가되라 출처 : 조영탁의행복한경영이야기나는여러분이 꿈중독자 가되었으면합니다. 꿈이크고꿈이선명하면남이하지말라고해도스스로열심히노력하게될것입니다.

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

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

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 장. 정렬 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

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

슬라이드 1

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

More information

슬라이드 1

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

More information

알고리즘 1장 기본개념

알고리즘 1장 기본개념 Video & Image VIPLProcessing Lab. 2013-1 Myoung-Jin Kim, Ph.D. (webzealer@ssu.ac.kr) Research Professor(Soongsil University) 컴퓨터학과이관용교수 Myoung-Jin Kim, Ph.D. (webzealer@ssu.ac.kr) 알고리즘의기본개념 알고리즘의중요성 자료구조파일처리

More information

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

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

More information

Algorithms

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

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 1. 자료구조와알고리즘 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 자료구조와알고리즘 일상생활에서의사물의조직화 해야할일리스트 조직도 일상생활에서의사물의조직화 사전 Ticket Box 3 일상생활과자료구조의비교 일상생활 vs 자료구조 자료구조 스택 큐 리스트 사전, 탐색구조

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

chap x: G입력

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

More information

슬라이드 1

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

More information

-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth

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

More information

Ch.8 Procedures and Environments

Ch.8 Procedures and Environments Chapter 9 정렬 (sorting) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 정렬 (sorting) 이란? 정의 물건을크기순으로오름차순이나내림차순으로나열하는것 컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬알고리즘의개요

More information

Discrete Mathematics

Discrete Mathematics 이산수학 () 알고리즘 (Algorithms) 0 년봄학기 강원대학교컴퓨터과학전공문양세 Algorithms The foundation of computer programming. ( 컴퓨터프로그래밍의기초 / 기반이다.) Most generally, an algorithm just means a definite procedure for performing some

More information

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

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

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

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

Microsoft PowerPoint - 26.pptx

Microsoft PowerPoint - 26.pptx 이산수학 () 관계와그특성 (Relations and Its Properties) 2011년봄학기 강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계

More information

슬라이드 1

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

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

슬라이드 1

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

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

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

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

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

More information

Microsoft PowerPoint - 6장 탐색.pptx

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

More information

설계란 무엇인가?

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

More information

06_sorting

06_sorting 정렬 Data Structures and Algorithms 목차 버블정렬 선택정렬 삽입정렬 힙정렬 병합정렬 퀵정렬 기수정렬 Data Structures and Algorithms 2 버블정렬 Data Structures and Algorithms 3 버블정렬 Data Structures and Algorithms 4 버블정렬 Data Structures and

More information

Microsoft PowerPoint - chap10_tree

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

More information

Visual Basic 반복문

Visual Basic 반복문 학습목표 반복문 For Next문, For Each Next문 Do Loop문, While End While문 구구단작성기로익히는반복문 2 5.1 반복문 5.2 구구단작성기로익히는반복문 3 반복문 주어진조건이만족하는동안또는주어진조건이만족할때까지일정구간의실행문을반복하기위해사용 For Next For Each Next Do Loop While Wend 4 For

More information

<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D> 계산복잡도 Computatioal Complexity 계산복잡도개론정렬문제 알고리즘의분석 어떤특정알고리즘의효율 (efficiecy 을측정 시간복잡도 (time complexity 공간복잡도 (space/memory complexity 문제의분석 일반적으로 계산복잡도분석 이란이를지칭 어떤문제에대해서그문제를풀수있는모든알고리즘의효율의하한 (lower-bou 을결정한다.

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

6장정렬알고리즘.key

6장정렬알고리즘.key 6 : :. (Internal sort) (External sort) (main memory). :,,.. 6.1 (Bubbble Sort).,,. 1 (pass). 1 pass, 1. (, ), 90 (, ). 2 40-50 50-90, 50 10. 50 90. 40 50 10 비교 40 50 10 비교 40 50 10 40 10 50 40 10 50 90

More information

Microsoft PowerPoint Merging and Sorting Files.ppt

Microsoft PowerPoint Merging and Sorting Files.ppt 자료처리 () 006 년봄학기문양세강원대학교컴퓨터과학과 정렬 / 합병의개요 정렬의종류 : 내부정렬, 외부정렬 내부정렬 (internal sorting) 데이타가적어서메인메모리내에모두저장시켜정렬가능할때사용함 레코드의판독 (read) 및기록 (write) 에걸리는시간이문제가되지않음 외부정렬 (external sorting) 데이타가많아서메인메모리의용량을초과하여보조기억장치

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

Microsoft PowerPoint - 5장 정렬

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

More information

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture 2014-1 프로그래밍언어 프로그래밍언어강의소개 2014. 3. 1. 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 프로그래밍언어강의개요 목적 C 프로그래밍언어를기반으로한공학문제의해결방법습득, C++

More information

Microsoft PowerPoint - chap-11.pptx

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

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 대표적인분할정복알고리즘 4 장. 재귀호출 학습목표 재귀호출이라는개념자체를명확히이해한다. 재귀호출함수의내부구조를이해한다. 재귀호출에내재하는효율성에대해이해한다. 1 Section 01 상징적의미 - 도미노 도미노 2 도미노 100 번째것이반드시쓰러진다는사실을증명하라. 수학적귀납법 (Mathematical Induction) 처음것 (K=1) 은반드시쓰러진다. K

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

SNU =10100 =minusby by1000 ÇÁto0.03exÇÁto0.03exÇÁ=10100 =minusby by1000 ·Îto0.03ex·Îto0.03ex·Î=10100 =minusby by1000

SNU =10100 =minusby by1000 ÇÁto0.03exÇÁto0.03exÇÁ=10100 =minusby by1000 ·Îto0.03ex·Îto0.03ex·Î=10100 =minusby by1000 SNU 4190.210 프로그래밍 원리 (Principles of Programming) Part III Prof. Kwangkeun Yi 차례 1 값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 2 프로그램의이해 : 환경과메모리 (environment & memory) 다음 1 값중심 vs 물건중심프로그래밍

More information

Microsoft PowerPoint - ch11_정렬 [호환 모드]

Microsoft PowerPoint - ch11_정렬 [호환 모드] 정렬 자바로배우는쉬운자료구조 이장에서다룰내용 1 정렬 6 셸정렬 2 선택정렬 7 병합정렬 3 버블정렬 8 기수정렬 4 퀵정렬 9 힙정렬 5 삽입정렬 10 트리정렬 2 정렬 (1) 정렬 (sort) 2 개이상의자료를작은것부터큰순서 ( 오름차순, ascending) 로정렬또는큰것부터작은것순서 ( 내림차순, descending) 로재배열하는것 키 : 자료를정렬하는데사용하는기준값

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

윈도우즈프로그래밍(1)

윈도우즈프로그래밍(1) 제어문 (2) For~Next 문 윈도우즈프로그래밍 (1) ( 신흥대학교컴퓨터정보계열 ) 2/17 Contents 학습목표 프로그램에서주어진특정문장을부분을일정횟수만큼반복해서실행하는문장으로 For~Next 문등의구조를이해하고활용할수있다. 내용 For~Next 문 다중 For 문 3/17 제어문 - FOR 문 반복문 : 프로그램에서주어진특정문장들을일정한횟수만큼반복해서실행하는문장

More information

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B 2015-1 프로그래밍언어 프로그래밍언어강의소개 2015. 3. 1. 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 프로그래밍언어강의개요 목적 C 프로그래밍언어를기반으로한공학문제의해결방법습득, C++

More information

입학사정관제도

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

More information

Microsoft PowerPoint Predicates and Quantifiers.ppt

Microsoft PowerPoint Predicates and Quantifiers.ppt 이산수학 () 1.3 술어와한정기호 (Predicates and Quantifiers) 2006 년봄학기 문양세강원대학교컴퓨터과학과 술어 (Predicate), 명제함수 (Propositional Function) x is greater than 3. 변수 (variable) = x 술어 (predicate) = P 명제함수 (propositional function)

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

01

01 2019 학년도대학수학능력시험 9 월모의평가문제및정답 2019 학년도대학수학능력시험 9 월모의평가문제지 1 제 2 교시 5 지선다형 1. 두벡터, 모든성분의합은? [2 점 ] 에대하여벡터 의 3. 좌표공간의두점 A, B 에대하여선분 AB 를 로외분하는점의좌표가 일때, 의값은? [2점] 1 2 3 4 5 1 2 3 4 5 2. lim 의값은? [2점] 4. 두사건,

More information

Microsoft PowerPoint Relations.pptx

Microsoft PowerPoint Relations.pptx 이산수학 () 관계와그특성 (Relations and Its Properties) 2010년봄학기강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계

More information

14장.탐색

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

More information

7장

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

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

쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP)

쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP) 쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP) http://academy.hanb.co.kr IT COOKBOOK 8장. 동적프로그래밍 Dynamic Programming (DP) 계시란바깥어딘가에서우리한테갑자기주어지는객관적지식이아니다. 만물의근원에대한본질적인귀속감, 우리가거기에아주밀접하게닿아있다는관계성을스스로가발견해내는것이계시다.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Chapter 08 함수 01 함수의개요 02 함수사용하기 03 함수와배열 04 재귀함수 함수의필요성을인식한다. 함수를정의, 선언, 호출하는방법을알아본다. 배열을함수의인자로전달하는방법과사용시장점을알아본다. 재귀호출로해결할수있는문제의특징과해결방법을알아본다. 1.1 함수의정의와기능 함수 (function) 특별한기능을수행하는것 여러가지함수의예 Page 4 1.2

More information

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 비트연산자 1 1 비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 진수법! 2, 10, 16, 8! 2 : 0~1 ( )! 10 : 0~9 ( )! 16 : 0~9, 9 a, b,

More information

statistics

statistics 수치를이용한자료요약 statistics hmkang@hallym.ac.kr 한림대학교 통계학 강희모 ( 한림대학교 ) 수치를이용한자료요약 1 / 26 수치를 통한 자료의 요약 요약 방대한 자료를 몇 개의 의미있는 수치로 요약 자료의 분포상태를 알 수 있는 통계기법 사용 중심위치의 측도(measure of center) : 어떤 값을 중심으로 분포되어 있는지

More information

<C6F7C6AEB6F5B1B3C0E72E687770>

<C6F7C6AEB6F5B1B3C0E72E687770> 1-1. 포트란 언어의 역사 1 1-2. 포트란 언어의 실행 단계 1 1-3. 문제해결의 순서 2 1-4. Overview of Fortran 2 1-5. Use of Columns in Fortran 3 1-6. INTEGER, REAL, and CHARACTER Data Types 4 1-7. Arithmetic Expressions 4 1-8. 포트란에서의

More information

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A 예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = 1 2 3 4 5 6 7 8 9 B = 8 7 6 5 4 3 2 1 0 >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = 0 0 0 0 1 1 1 1 1 >> tf = (A==B) % A 의원소와 B 의원소가똑같은경우를찾을때 tf = 0 0 0 0 0 0 0 0 0 >> tf

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

제 11 장 다원 탐색 트리

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

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

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

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

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

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

More information

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

More information

Microsoft Word - FunctionCall

Microsoft Word - FunctionCall Function all Mechanism /* Simple Program */ #define get_int() IN KEYOARD #define put_int(val) LD A val \ OUT MONITOR int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; } local auto variable stack

More information

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770> 삼각함수. 삼각함수의덧셈정리 삼각함수의덧셈정리 삼각함수 sin (α + β ), cos (α + β ), tan (α + β ) 등을 α 또는 β 의삼각함수로나 타낼수있다. 각 α 와각 β 에대하여 α >0, β >0이고 0 α - β < β 를만족한다고가정하 자. 다른경우에도같은방법으로증명할수있다. 각 α 와각 β 에대하여 θ = α - β 라고놓자. 위의그림에서원점에서거리가

More information

FGB-P 학번수학과권혁준 2008 년 5 월 19 일 Lemma 1 p 를 C([0, 1]) 에속하는음수가되지않는함수라하자. 이때 y C 2 (0, 1) C([0, 1]) 가미분방정식 y (t) + p(t)y(t) = 0, t (0, 1), y(0)

FGB-P 학번수학과권혁준 2008 년 5 월 19 일 Lemma 1 p 를 C([0, 1]) 에속하는음수가되지않는함수라하자. 이때 y C 2 (0, 1) C([0, 1]) 가미분방정식 y (t) + p(t)y(t) = 0, t (0, 1), y(0) FGB-P8-3 8 학번수학과권혁준 8 년 5 월 9 일 Lemma p 를 C[, ] 에속하는음수가되지않는함수라하자. 이때 y C, C[, ] 가미분방정식 y t + ptyt, t,, y y 을만족하는해라고하면, y 는, 에서연속적인이계도함수를가지게확 장될수있다. Proof y 은 y 의도함수이므로미적분학의기본정리에의하여, y 은 y 의어떤원시 함수와적분상수의합으로표시될수있다.

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

11장 포인터

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

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

歯MW-1000AP_Manual_Kor_HJS.PDF

歯MW-1000AP_Manual_Kor_HJS.PDF Page 2 Page 3 Page 4 Page 5 Page 6 Page 7 Page 8 Page 9 Page 10 Page 11 Page 12 Page 13 Page 14 Page 15 Page 16 Page 17 Page 18 Page 19 Page 20 Page 21 Page 22 Page 23 Page 24 Page 25 Page 26 Page 27 Page

More information

Overview Decision Tree Director of TEAMLAB Sungchul Choi

Overview Decision Tree Director of TEAMLAB Sungchul Choi Overview Decision Tree Director of TEAMLAB Sungchul Choi 머신러닝의학습방법들 - Gradient descent based learning - Probability theory based learning - Information theory based learning - Distance similarity based

More information

Poison null byte Excuse the ads! We need some help to keep our site up. List 1 Conditions 2 Exploit plan 2.1 chunksize(p)!= prev_size (next_chunk(p) 3

Poison null byte Excuse the ads! We need some help to keep our site up. List 1 Conditions 2 Exploit plan 2.1 chunksize(p)!= prev_size (next_chunk(p) 3 Poison null byte Excuse the ads! We need some help to keep our site up. List 1 Conditions 2 Exploit plan 2.1 chunksize(p)!= prev_size (next_chunk(p) 3 Example 3.1 Files 3.2 Source code 3.3 Exploit flow

More information

슬라이드 1

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

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

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 (   ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각 JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( http://java.sun.com/javase/6/docs/api ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각선의길이를계산하는메소드들을작성하라. 직사각형의가로와세로의길이는주어진다. 대각선의길이는 Math클래스의적절한메소드를이용하여구하라.

More information

Microsoft PowerPoint - 27.pptx

Microsoft PowerPoint - 27.pptx 이산수학 () n-항관계 (n-ary Relations) 2011년봄학기 강원대학교컴퓨터과학전공문양세 n-ary Relations (n-항관계 ) An n-ary relation R on sets A 1,,A n, written R:A 1,,A n, is a subset R A 1 A n. (A 1,,A n 에대한 n- 항관계 R 은 A 1 A n 의부분집합이다.)

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

데이터 구조의 개요

데이터 구조의 개요 자료구조와알고리즘 충북대학교 소프트웨어학과이충세 문의사항 Email : csrhee@cbnu.ac.kr 전화 : 043-26-2237 강의자료 : web.cbu.ac.kr/~algor 참조 2 알고리즘 : 주제 기초자료구조 알고리즘의분석기법 트리와그래프 점화식 알고리즘기법분할정복, 동적프로그램, Greedy 방법 3 . 데이터와데이터객체.. 데이터의개념 *

More information

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M. 오늘할것 5 6 HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M. Review: 5-2 7 7 17 5 4 3 4 OR 0 2 1 2 ~20 ~40 ~60 ~80 ~100 M 언어 e ::= const constant

More information

1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속

1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속 1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속 2 1.1 함수를표현하는네가지방법 함수 f : D E 는집합 D 의각원소 x 에집합 E 에속하는단하나의원소 f(x) 를 대응시키는규칙이다.

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

Microsoft PowerPoint - 30.ppt [호환 모드]

Microsoft PowerPoint - 30.ppt [호환 모드] 이중포트메모리의실제적인고장을고려한 Programmable Memory BIST 2010. 06. 29. 연세대학교전기전자공학과박영규, 박재석, 한태우, 강성호 hipyk@soc.yonsei.ac.kr Contents Introduction Proposed Programmable Memory BIST(PMBIST) Algorithm Instruction PMBIST

More information

슬라이드 1

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

More information

adfasdfasfdasfasfadf

adfasdfasfdasfasfadf C 4.5 Source code Pt.3 ISL / 강한솔 2019-04-10 Index Tree structure Build.h Tree.h St-thresh.h 2 Tree structure *Concpets : Node, Branch, Leaf, Subtree, Attribute, Attribute Value, Class Play, Don't Play.

More information

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로 3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로성립한다. Theorem 7 두함수 f : X Y 와 g : X Y 에대하여, f = g f(x)

More information

슬라이드 1

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

More information

스무살, 마음껏날아오르기위해, 일년만꾹참자! 2014학년도대학수학능력시험 9월모의평가 18번두이차정사각행렬 가 를만족시킬때, 옳은것만을 < 보기 > 에서있는대로고른것은? ( 단, 는단위행렬이다.) [4점] < 보기 > ㄱ. ㄴ. ㄷ. 2013학년도대학수학능력시험 16번

스무살, 마음껏날아오르기위해, 일년만꾹참자! 2014학년도대학수학능력시험 9월모의평가 18번두이차정사각행렬 가 를만족시킬때, 옳은것만을 < 보기 > 에서있는대로고른것은? ( 단, 는단위행렬이다.) [4점] < 보기 > ㄱ. ㄴ. ㄷ. 2013학년도대학수학능력시험 16번 친절한하영쌤의 수학 A형 약점체크집중공략오답률 Best 5 정복 하기! - 보충문제 행렬 2015학년도대학수학능력시험 9월모의평가 19번두이차정사각행렬 가 를만족시킬때, < 보기 > 에서옳은것만을있는대로고른것은? ( 단, 는단위행렬이고, 는영행렬이다.) [4점] < 보기 > ㄱ. 의역행렬이존재한다. ㄴ. ㄷ. 2015학년도대학수학능력시험 6월모의평가 19번두이차정사각행렬

More information

중간고사

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

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

정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [4,2,3,1,6,8,3,2,6,7] 다음과같이된다. [1,2,2,3,3,4,6,6,7,8] 이장에서는정수리스트를오름차순으로정렬하는함수를다양한알고

정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [4,2,3,1,6,8,3,2,6,7] 다음과같이된다. [1,2,2,3,3,4,6,6,7,8] 이장에서는정수리스트를오름차순으로정렬하는함수를다양한알고 CSE117 프로그래밍기초강의노트 1 10 프로그램디자인사례 : 정렬 Program Design Case Study: Sorting 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2013년 2학기 (version 0.8) 1 c 도경구 (2013). 본문서는한양대학교 ERICA 캠퍼스컴퓨터공학과프로그래밍기초강의용으로제 작되었습니다. 강의이외의용도로저자의허락없이무단복제하여배포할수없습니다.

More information