정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [4,2,3,1,6,8,3,2,6,7] 다음과같이된다. [1,2,2,3,3,4,6,6,7,8] 이장에서는정수리스트를오름차순으로정렬하는함수를다양한알고
|
|
|
- 영숙 은
- 6 years ago
- Views:
Transcription
1 CSE117 프로그래밍기초강의노트 1 10 프로그램디자인사례 : 정렬 Program Design Case Study: Sorting 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2013년 2학기 (version 0.8) 1 c 도경구 (2013). 본문서는한양대학교 ERICA 캠퍼스컴퓨터공학과프로그래밍기초강의용으로제 작되었습니다. 강의이외의용도로저자의허락없이무단복제하여배포할수없습니다.
2 정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [4,2,3,1,6,8,3,2,6,7] 다음과같이된다. [1,2,2,3,3,4,6,6,7,8] 이장에서는정수리스트를오름차순으로정렬하는함수를다양한알고리즘을적용하여파이썬함수로작성해본다. 먼저리스트구조부터공부하자. 1. ( 진짜 ) 리스트갖고놀기 Python의리스트는배열 (array) 과같이위치번호로접근과수정이가능하기때문에리스트연산이가능하고모양이리스트와같음에도불구하고엄밀히따져서리스트라고할수없다. 진짜리스트를공부해보자. 정수리스트는다음과같이귀납으로정의할수있다. 1. nil은정수리스트이다. 2. n이정수이고, ns가정수리스트이면, cons(n,ns) 는정수리스트이다. 3. 다른정수리스트는없다. 이정의를사용하면다음과같이정수리스트를만들수있다. nil cons(3,nil) cons(3,cons(4,nil)) cons(7,cons(2,cons(4,nil)))... 잘보면, cons( 콘스 로읽음 ) 는주어진정수와정수리스트를결합하여새로운정수리스트를만드는연산자이다. 리스트를결합하는연산자가있으므로분리하는연산자도있어야한다. 전통적으로 (1950년대만든 LISP라는언어에서유래 ) 분리연산자는 car( 카 로읽음 ) 와 cdr( 쿠더 로읽음 ) 라고하며다음과같이작동한다. car(cons(n,ns)) = n cdr(cons(n,ns)) = ns 이연산자로리스트계산을직접해보기위해서 Python으로함수를다음과같이정의하고이연산자만사용하여프로그램을만들어보자. 1
3 nil = [] def null(ns): return ns == nil def cons(n,ns): return [n] + ns def car(ns): return ns[0] def cdr(ns): return ns[1:] 리스트를취급하는프로그램을디자인할때이러한귀납적인구조를이용하여재귀프로그램을만들수있다. 정수리스트길이계산하기정수리스트 xs의길이를계산하는함수 length는정수리스트의귀납구조를따라서다음과같이고안할수있다. 1. 정수리스트 xs가 nil이면, 길이는 0이다. 2. 정수리스트 xs의길이가 l이면, cons(x,xs) 의길이는 l + 1이다. 이아이디어로재귀함수를짜면다음과같다. def length(xs): if null(xs): return 0 else: return 1 + length(cdr(xs)) 꼬리재귀형태로바꾸면, def length(xs): def loop(xs,l): if null(xs): return l else: return loop(cdr(xs),l+1) return loop(xs,0) 2
4 while 루프로바꾸면, def length(xs): = 0 while not null(xs): xs = cdr(xs) l = l + 1 return l 정수리스트붙이기두개의정수리스트 xs와 ys를붙이는함수 append는첫인수정수리스트 xs의귀납구조를따라서다음과같이작성할수있다. def append(xs,ys): if null(xs): return ys else: return cons(car(xs),append(cdr(xs),ys)) 이함수를꼬리재귀형태로그대로바꾸려면쉽지않다. 하지만 xs를뒤집어놓으면자연스럽게꼬리재귀함수를만들수있다. 리스트를뒤집는함수 reverse가있다고가정하고만들어보자. def append(xs,ys): def loop(xs,rs): if null(xs): return rs else: return loop(cdr(xs),cons(car(xs),rs)) return loop(reverse(xs),ys) while 루프로바꾸면, def append(xs,ys): xs = reverse(xs) rs = ys while not null(xs): xs, rs = cdr(xs), cons(car(xs),rs) return rs 3
5 정수리스트뒤집기정수리스트 xs를뒤집는함수 reverse는 xs의귀납구조를따라서다음과같이작성할수있다. append를사용할수밖에없음에주목하자. def reverse(xs): if null(xs): return xs else: return append(reverse(cdr(xs)),cons(car(xs),nil)) 이함수를꼬리재귀형태로바꾸면아주자연스러워진다. def reverse(xs): def loop(xs,rs): if null(xs): return rs else: return loop(cdr(xs),cons(car(xs),rs)) return loop(xs,nil) while 루프로바꾸면, def reverse(xs): rs = nil while not null(xs): xs, rs = cdr(xs), cons(car(xs),rs) return rs 2. 삽입정렬 (Insertion Sort) 삽입정렬은다음과같은전략으로정렬한다. 정렬할정수리스트 xs에서수를앞에서부터하나씩꺼내서새로운리스트를만들면서정렬이되도록제위치에끼워넣는다. 예를들어, cons(3,cons(6,cons(5,cons(2,cons(4,nil))))) 은다음과같이정렬한다. 3을꺼내어 cons(3,nil) 을만든다. 6을꺼내어 cons(3,nil) 의제위치에끼워넣어 cons(3,cons(6,nil)) 을만든다. 5를꺼내어 cons(3,cons(6,nil)) 의제위치에끼워넣어 cons(3,cons(5,cons(6,nil))) 을만든다. 4
6 2를꺼내어 cons(3,cons(5,cons(6,nil))) 의제위치에끼워넣어 cons(2,cons(3,cons(5,cons(6,nil)))) 을만든다. 4를꺼내어 cons(2,cons(3,cons(5,cons(6,nil)))) 의제위치에끼워넣어 cons(2,cons(3,cons(4,cons(5,cons(6,nil))))) 을만든다. 삽입정렬프로그램디자인정수리스트의귀납적구조를이용하여재귀적으로삽입정렬프로그램을디자인해보자. 정수리스트 xs를정렬하는함수 isort(xs) 는다음과같이디자인한다. xs가비어있으면, 정렬할필요가없다. xs가비어있지않으면, 재귀적으로 isort(cdr(xs)) 를호출하여 cdr(xs) 를먼저정렬한후, 그리스트의정렬이흩틀어지지않도록적절한위치에첫째아이템 car(xs) 을끼워넣는다. 이를프로그램으로작성하면다음과같다. 1 def isort(xs): 2 if null(xs): 3 return nil 4 else: 5 return insert(car(xs),isort(cdr(xs))) 이제아이템 x를정렬된리스트 ss에정렬을흩트리지않으면서제위치에끼워넣는 insert(x,ss) 를디자인해보자. ss가 nil이면 ( 비어있으면 ), x를끼워넣은결과는 cons(x,nil) 가된다. ss가 nil이아니고, x가 ss의첫째아이템 car(ss) 보다작거나같으면, x를 ss의맨앞에붙여서 cons(x,ss) 를만들면된다. ss가 nil이아니고, x가 ss의첫째아이템 car(ss) 보다크면, insert(x,cdr(ss)) 를재귀호출하여 x를정렬된리스트 cdr(ss) 에끼워넣는다. 이를프로그램으로작성하면다음과같다. 1 def insert(x,ss): 2 if null(ss): 3 return cons(x,nil) 4 elif x <= car(ss): 5 return cons(x,ss) 6 else: 7 return cons(car(ss),insert(x,cdr(ss))) 5
7 실행추적 다음과같이특정입력리스트로실행추적을해보면프로그램이어떻게실행되는지살펴볼수 있다. isort(cons(3,cons(6,cons(5,cons(2,cons(4,nil)))))) insert(3,isort(cons(6,cons(5,cons(2,cons(4,nil)))))) insert(3,insert(6,isort(cons(5,cons(2,cons(4,nil)))))) insert(3,insert(6,insert(5,isort(cons(2,cons(4,nil)))))) insert(3,insert(6,insert(5,insert(2,isort(cons(4,nil)))))) insert(3,insert(6,insert(5,insert(2,insert(4,isort(nil)))))) insert(3,insert(6,insert(5,insert(2,insert(4,nil))))) insert(3,insert(6,insert(5,insert(2,cons(4,nil))))) insert(3,insert(6,insert(5,cons(2,cons(4,nil))))) insert(3,insert(6,cons(2,insert(5,cons(4,nil))))) insert(3,insert(6,cons(2,cons(4,insert(5,nil))))) insert(3,insert(6,cons(2,cons(4,cons(5,nil))))) insert(3,cons(2,insert(6,cons(4,cons(5,nil))))) insert(3,cons(2,cons(4,insert(6,cons(5,nil))))) insert(3,cons(2,cons(4,cons(5,insert(6,nil))))) insert(3,cons(2,cons(4,cons(5,cons(6,nil))))) cons(2,insert(3,cons(4,cons(5,cons(6,nil))))) cons(2,cons(3,cons(4,cons(5,cons(6,nil))))) 성능분석 이함수들은원초적재귀함수형식으로작성하였다. 삼입정렬하는작업은재귀함수 isort 로구현하였고, 정렬된리스트에원소를하나씩끼워넣는작업은재귀함수 insert 로구현하 였다. 정렬할리스트 xs 의길이를 n 이라고하면, isort 함수는 n 번호출된다. insert 함수는 원소를하나씩정렬된리스트의제위치에끼워넣는다. 정렬된리스트의길이가 k 이면, 맨뒤에 끼워넣는경우 insert 함수를 k 번호출한다. 하지만운이좋아맨앞에끼워넣는경우 1 번밖에 호출하지않는다. 즉, insert 함수를호출하는횟수는끼워넣는원소와대상리스트의내용에 따라서다르다. 맨앞에붙이는경우가최선의경우이며, 맨뒤에붙이는경우가최악의경우이 다. 정렬할리스트가완전히역순으로정렬이되어있으면최악의경우이고, 정렬할리스트가 이미완전히정렬되어있으면최선의경우이다. 최선의경우에는 insert 함수호출횟수는 n 번 밖에안되지만, 최악의경우에는 Σ n i=1i = n(n + 1)/2 가되어, insert 함수를호출하는횟수로 기준으로최악의경우실행시간은리스트의길이의제곱에비례한다고할수있다. 6
8 공간효율향상원초적재귀함수형식은재귀호출에서돌아온후해야할계산을남기므로이를기록하는만큼의저장공간이추가로필요하다. 이를피하기위해서위의두함수를꼬리재귀함수형식으로변환한뒤, 루프버전으로변환해보자. 먼저 insert 함수를꼬리재귀함수형식으로변환하면다음과같이된다. 1 def insert(x,ss): 2 def loop(ss,rs): 3 if null(ss): 4 return append(rs,cons(x,nil)) 5 elif x <= car(ss): 6 return append(rs,cons(x,ss)) 7 else: 8 return loop(cdr(ss),append(rs,cons(car(ss),nil))) 9 return loop(ss,nil) 다음, isort 함수도꼬리재귀함수형식으로변환하면다음과같이된다. 1 def isort(xs): 2 def loop(xs,ss): 3 if null(xs): 4 return ss 5 else: 6 return loop(cdr(xs),insert(car(xs),ss)) 7 return loop(xs,nil) while 루프를사용하여변환하면다음과같다. 이두프로그램은모양만다를뿐작동방식이같으므로성능의차이는없다. 1 def insert(x,ss): 2 rs = nil 3 while not null(ss): 4 if x <= car(ss): 5 break 6 else: 7 rs = append(rs,cons(car(ss,nil))) 8 ss = cdr(ss) 9 return append(rs,cons(x,ss)) 7
9 1 def isort(xs): 2 ss = nil 3 while not null(xs): 4 ss = insert(car(xs),ss) 5 xs = cdr(xs) 6 return ss 파이썬의 for 루프를사용하면프로그램이더간결해진다. 1 def isort(xs): 2 ss = nil 3 for x in xs: 4 ss = insert(x,ss) 5 return ss 공간은절약하였지만 insert 함수를호출하는횟수는줄지않는다. 즉, 시간적인효율성은 변함이없다. 3. 선택정렬 (Selection Sort) 선택정렬은다음과같은전략으로정렬한다. 정수리스트 xs가주어지면, 그리스트를정렬되지않은리스트로놓고, 그리스트전체를훑어서제일작은수하나를꺼내어정렬된리스트로만들어나간다. 정렬되지않은리스트가빌때까지그과정을반복한다. 예를들어, [3,6,5,2,4] 은다음과같이정렬한다. [3,6,5,2,4] 에서 2을꺼내어 [2] 를만든다. [3,6,5,4] 에서 3을꺼내어 [2,3] 을만든다. [6,5,4] 에서 4를꺼내어 [2,3,4] 를만든다. [6,5] 에서 5를꺼내어 [2,3,4,5] 를만든다. [6] 에서 6을꺼내어 [2,3,4,5,6] 을만든다. 선택정렬프로그램디자인정수리스트의귀납구조를이용하여재귀적으로선택정렬프로그램을원초적재귀함수형식으로디자인해보자. 정수리스트 xs를정렬하는함수 ssort는다음과같이디자인한다. xs가비어있으면, 정렬된결과리스트도비어있다. 8
10 xs가비어있지않으면, xs에서가장작은아이템을하나떼어와서줄세우고, 나머지리스트도같은방법으로재귀적으로정렬한다. 그러면리스트에서가장작은아이템을어떻게떼어올까? 여러가지방법이있을텐데우리는다음과같은방법을써보자. 리스트전체를훑어서가장작은값을찾은뒤그값을맨앞으로옮긴다. 이역할을하는함수를 select라고하자. 그러면 select(xs) 를호출하면 xs에서가장작은값을맨앞으로옮긴리스트를결과로내주게될것이다. select 함수를써서선택정렬함수를작성하면다음과같다. 1 def ssort(xs): 2 if null(xs): 3 return nil 4 else: 5 ys = select(xs) 6 return cons(car(ys),ssort(cdr(ys))) 이제 select 함수를역시재귀로디자인해보자. 입력리스트 xs가주어졌을때, xs에원소가하나밖에없으면그냥그대로내주면된다. xs에원소가둘이상있으면, 앞의두원소를꺼내서비교한다. 둘중작은원소를선택하여나머지리스트와붙여서재귀적으로호출하여결과리스트를얻은후, 큰원소는뒤에붙인다. 이를원초적재귀함수형식으로작성하면다음과같다. 1 def select(xs): 2 if length(xs) <= 1: 3 return xs 4 else: 5 first = car(xs) 6 second = car(cdr(xs)) 7 if first < second: 8 rest = cdr(cdr(xs)) 9 return append(select(cons(first,rest)),cons(second,nil)) 10 else: 11 rest = cdr(xs) 12 return append(select(rest),cons(first,nil)) 9
11 실행추적 다음과같이특정입력리스트로실행추적을해보면프로그램이어떻게실행되는지살펴볼수 있다. ssort(cons(3,cons(6,cons(5,cons(2,cons(4,nil)))))) ys = select(cons(3,cons(6,cons(5,cons(2,cons(4,nil)))))) first = 3 second = 6 rest = cons(5,cons(2,cons(4,nil))) append(select(cons(3,cons(5,cons(2,cons(4,nil))))),cons(6,nil)) first = 3 second = 5 rest = cons(2,cons(4,nil)) append(select(cons(3,cons(2,cons(4,nil)))),cons(5,nil)) first = 3 second = 2 rest = cons(2,cons(4,nil)) append(select(cons(2,cons(4,nil))),cons(3,nil)) first = 2 second = 4 rest = nil append(select(cons(2,nil)),cons(4,nil)) cons(2,nil) cons(2,cons(4,nil)) cons(2,cons(4,cons(3,nil))) cons(2,cons(4,cons(3,cons(5,nil)))) cons(2,cons(4,cons(3,cons(5,cons(6,nil))))) cons(2,ssort(cons(4,cons(3,cons(5,cons(6,nil)))))) ys = select(cons(4,cons(3,cons(5,cons(6,nil))))) first = 4 second = 3 rest = cons(3,cons(5,cons(6,nil))) append(select(cons(3,cons(5,cons(6,nil)))),cons(4,nil)) first = 3 second = 5 rest = cons(6,nil) append(select(cons(3,cons(6,nil))),cons(5,nil)) first = 3 second = 6 rest = nil append(select(cons(3,nil)),cons(6,nil)) cons(3,nil) cons(3,cons(6,nil)) cons(3,cons(6,cons(5,nil))) cons(3,cons(6,cons(5,cons(4,nil)))) 10
12 cons(3,ssort(cons(6,cons(5,cons(4,nil))))) ys = select(cons(6,cons(5,cons(4,nil)))) first = 6 second = 5 rest = cons(5,cons(4,nil)) append(select(cons(5,cons(4,nil))),cons(6,nil)) first = 5 second = 4 rest = cons(4,nil) append(select(cons(4,nil)),cons(5,nil)) cons(4,nil) cons(4,cons(5,nil)) cons(4,cons(5,cons(6,nil))) cons(4,ssort(cons(5,cons(6,nil)))) ys = select(cons(5,cons(6,nil))) first = 5 second = 6 rest = nil append(select(cons(5,nil)),cons(6,nil)) cons(5,nil) cons(5,cons(6,nil)) cons(5,ssort(cons(6,nil))) ys = select(cons(6,nil)) cons(6,nil) cons(6,ssort(nil)) nil cons(6,nil) cons(5,cons(6,nil)) cons(4,cons(5,cons(6,nil))) cons(3,cons(4,cons(5,cons(6,nil)))) cons(2,cons(3,cons(4,cons(5,cons(6,nil))))) 성능분석 이함수들은원초적재귀함수형식으로작성하였다. 선택정렬하는작업은재귀함수 ssort 로 구현하였고, 리스트에서제일작은값을맨앞에옮기는작업은재귀함수 select 로구현하였 다. ssort 함수는입력리스트 xs 의길이만큼재귀호출되고, select 함수도입력리스트 xs 의 길이만큼재귀호출된다. 전체적으로 xs 의길이를 n 으로놓고 select 함수를호출하는횟수를 기준단위로실행시간을따져보면정확하게 Σ n i=1i = n(n + 1)/2 가되어, 입력리스트의길이의제곱에비례한다고할수있다. 여기서입력리스트의내용과무관하게항상 select 함수호출 횟수는같다. 11
13 공간효율향상원초적재귀함수형식은재귀호출에서돌아온후해야할계산을남기므로이를기록하는만큼의저장공간이추가로필요하다. 이를피하기위해서위의두함수를꼬리재귀함수형식으로변환해보자. 먼저 select 함수를꼬리재귀함수형식으로변환하면다음과같이된다. 1 def select(xs): 2 def loop(xs,rs): 3 if length(xs) <= 1: 4 return append(xs,rs) 5 else: 6 first = car(xs) 7 second = car(cdr(xs)) 8 if first < second: 9 rest = cdr(cdr(xs)) 10 return loop(cons(first,rest),cons(second,rs)) 11 else: 12 rest = cdr(xs) 13 return loop(rest,cons(first,rs)) 14 return loop(xs,nil) 다음, ssort 함수도꼬리재귀함수형식으로변환하면다음과같이된다. 1 def ssort(xs): 2 def loop(xs,rs): 3 if null(xs): 4 return rs 5 else: 6 ys = select(xs) 7 return loop(cdr(ys),append(rs,cons(car(ys),nil))) 8 return loop(xs,nil) 실행추적꼬리재귀함수도같은입력리스트로실행추적해보자. ssort1([3,6,5,2,4]) loop([3,6,5,2,4],[]) ys = select1([3,6,5,2,4]) 12
14 loop([3,6,5,2,4],[]) loop([3,5,2,4],[6]) loop([3,2,4],[5,6]) loop([2,4],[3,5,6]) loop([2],[4,3,5,6]) [2,4,3,5,6] loop([4,3,5,6],[2]) ys = select1([4,3,5,6]) loop([4,3,5,6],[]) loop([3,5,6],[4]) loop([3,6],[4,5]) loop([3],[4,5,6]) [3,4,5,6] loop([4,5,6],[2,3]) ys = select1([4,5,6]) loop([4,5,6],[]) loop([4,6],[5]) loop([4],[5,6]) [4,5,6] loop([5,6],[2,3,4]) ys = select1([5,6]) loop([5,6],[]) loop([5],[6]) [5,6] loop([6],[2,3,4,5]) ys = select1([6]) [6] loop([],[2,3,4,5,6]) [2,3,4,5,6] 꼬리재귀호출은돌아와서할계산을남기지않으므로그만큼의공간을절약할수있다. 하지만 select 함수를호출하는횟수를원천적으로줄일수있는방법은없다. 즉, 시간적인효율성은같다. 루프버전 꼬리재귀함수프로그램은 while 루프를사용하여다음과같이재작성할수있다. 이두프로 그램은모양만다를뿐작동방식이같으므로성능의차이는없다. 13
15 1 def select(xs): 2 rs = nil 3 while length(xs) > 1: 4 first = car(xs) 5 second = car(cdr(xs)) 6 if first < second: 7 rest = cdr(cdr(xs)) 8 xs = cons(first,rest) 9 rs = cons(second,rs) 10 else: 11 rest = cdr(xs) 12 xs = rest 13 rs = cons(first,rs) 14 return append(xs,rs) 1 def ssort(xs): 2 rs = nil 3 while not null(xs): 4 ys = select(xs) 5 xs = cdr(ys) 6 rs = append(rs,cons(car(ys),nil)) 7 return rs 4. 합병정렬 (Merge Sort) 합병정렬은다음과같은전략으로정렬한다. 정수리스트 xs가주어지면, 그리스트를반으로나누어각각재귀적으로정렬한후, 두정렬된리스트를하나의정렬된리스트로합병한다. 예를들어, [3,6,5,2,4,1,8,7] 는다음과같이정렬한다. [3,6,5,2] 와 [4,1,8,7] 로반으로나누어각각정렬한다. 정렬된두리스트 [2,3,5,6] 과 [1,4,7,8] 을앞에서부터차례로훑어가며작은수를먼저선택하는방식으로하나로합병한다. 그결과로 [1,2,3,4,5,6,7,8] 을얻는다. 14
16 합병정렬프로그램디자인앞에서와마찬가지로정수리스트의귀납적구조를이용하여재귀적으로합병정렬프로그램을디자인해보자. 정수리스트 xs를합병정렬하는함수 msort는다음과같이디자인한다. xs가비어있거나아이템이하나밖에없으면정렬할필요가없다. 그렇지않으면, xs를반으로쪼개서각각 ls와 rs하고하고 msort(ls) 와 msort(rs) 를각각재귀적으로호출하여정렬하고 두개의정렬된리스트를하나의정렬된리스트로합병한다. 아래프로그램은이방법을그대로적용하여원초적재귀함수형식으로작성한정렬함수이다. split 함수는리스트를반으로쪼개서내주는일을하고, 재귀함수 merge는두개의정렬된리스트를하나의정렬된리스트로합병하는일을하고, 재귀함수 msort는합병정렬하는일을한다. 1 def split(xs,mid): 2 def lefthalf(xs,mid): 3 if mid <= 0: 4 return nil 5 else: 6 return cons(car(xs),lefthalf(cdr(xs),mid-1)) 7 def righthalf(xs,mid): 8 if mid <= 0: 9 return xs 10 else: 11 return righthalf(cdr(xs),mid-1) 12 return lefthalf(xs,mid),righthalf(xs,mid) 1 def msort(xs): 2 if null(xs) or null(cdr(xs)): 3 return xs 4 else: 5 mid = length(xs) // 2 6 ls, rs = split(xs,mid) 7 return merge(msort(ls),msort(rs)) 1 def merge(xs,ys): 2 if null(xs) or null(ys): 15
17 3 return append(xs,ys) 4 elif car(xs) < car(ys): 5 return cons(car(xs),merge(cdr(xs),ys)) 6 else: 7 return cons(car(ys),merge(xs,cdr(ys))) 실행추적 msort를호출하여계산절차을추적해보자. msort(cons(3,cons(6,cons(5,cons(2,cons(4,cons(1,cons(8,cons(7,nil))))))))) merge(msort(cons(3,cons(6,cons(5,cons(2,nil))))), msort(cons(4,cons(1,cons(8,cons(7,nil)))))) merge(merge(msort(cons(3,cons(6,nil))),msort(cons(5,cons(2,nil)))), merge(msort(cons(4,cons(1,nil))),msort(cons(8,cons(7,nil))))) merge(merge(merge(msort(cons(3,nil)),msort(cons(6,nil))), merge(msort(cons(5,nil)),msort(cons(2,nil)))), merge(merge(msort(cons(4,nil)),msort(cons(1,nil))), merge(msort(cons(8,nil)),msort(cons(7,nil))))) merge(merge(merge(cons(3,nil),cons(6,nil)), merge(cons(5,nil),cons(2,nil))), merge(merge(cons(4,nil),cons(1,nil)), merge(cons(8,nil),cons(7,nil)))) merge(merge(cons(3,cons(6,nil)),cons(2,cons(5,nil))), merge(cons(1,cons(4,nil)),cons(7,cons(8,nil)))) merge(cons(2,cons(3,cons(5,cons(6,nil)))), cons(1,cons(4,cons(7,cons(8,nil))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil)))))))) 위의계산추적에서는 merge 함수의실행추적은자세히보여주지않았다. 하나만대표로추적해보자. merge(cons(2,cons(3,cons(5,cons(6,nil)))), cons(1,cons(4,cons(7,cons(8,nil))))) cons(1,merge(cons(2,cons(3,cons(5,cons(6,nil)))), cons(4,cons(7,cons(8,nil))))) cons(1,cons(2,merge(cons(3,cons(5,cons(6,nil))),cons(4,cons(7,cons(8,nil)))))) cons(1,cons(2,cons(3,merge(cons(5,cons(6,nil)),cons(4,cons(7,cons(8,nil))))))) cons(1,cons(2,cons(3,cons(4,merge(cons(5,cons(6,nil)),cons(7,cons(8,nil))))))) 16
18 cons(1,cons(2,cons(3,cons(4,cons(5,merge(cons(6,nil),cons(7,cons(8,nil))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,merge(nil,cons(7,cons(8,nil))))))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,append(nil,cons(7,cons(8,nil))))))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil)))))))) split 함수를순수리스트로만들다보니복잡해졌지만, Python 리스트 ( 사실상배열 ) 의범위자르기를이용하면다음과같이간단해진다. 1 def split(xs,mid): 2 return xs[:mid], xs[mid:] 시간및공간효율향상 merge 함수를꼬리재귀형식으로변환하면다음과같이된다. 1 def merge(xs,ys): 2 def loop(xs,ys,rs): 3 if null(xs) or null(ys): 4 return append(rs,append(xs,ys)) 5 elif car(xs) < car(ys): 6 return loop(cdr(xs),ys,append(rs,cons(car(xs),nil))) 7 else: 8 return loop(xs,cdr(ys),append(rs,cons(car(ys),nil))) 9 return loop(xs,ys,nil) 이꼬리재귀형식의프로그램은쉽게 while 루프형식으로프로그램으로다음과같이변환할수있다. 1 def merge(xs,ys): 2 rs = nil 3 while not null(xs) and not null(ys): 4 if car(xs) < car(ys): 5 rs = append(rs,cons(car(xs),nil)) 6 xs = cdr(xs) 7 else: 8 rs = append(rs,cons(car(ys),nil)) 9 ys = cdr(ys) 10 return append(rs,append(xs,ys)) 17
19 성능분석합병절렬알고리즘은일반적으로앞에서공부한삽입정렬과선택정렬과비교해서정렬하는시간이빠르다. 이를계산하는건알고리즘을분석하는수학적기술을이해해야하므로여기서자세한언급은피하겠다. 추후에 알고리즘설계및분석 과목에서자세히배우게될것이다. 연습문제 split 함수를꼬리재귀형태로바꾼뒤, while 루프로된프로그램으로변환해보자. 5. 퀵정렬 (Quick Sort) 퀵정렬은영국의유명한컴퓨터학자 C.A.R. Hoare가 60년대에고안해낸알고리즘이다. 이알고리즘은합병정렬과비슷하나대상리스트를무조건반으로쪼개는대신피봇 (pivot) 이라고하는기준값을선택하고그값을기준으로작은값만들어있는리스트와큰값만들어있는리스트로나눈후, 재귀적으로정렬한다. 합병정렬은무조건반으로나누어재귀적으로정렬하므로추후에합병절차가필요하지만. 퀵정렬은피봇값을중심으로작은값과큰값을따로끼리끼리나누는수고를미리하고재귀적으로정렬하므로뒤에합병하는절차는필요없다. 퀵정렬프로그램디자인정수리스트 xs를퀵정렬하는함수 qsort는다음과같이디자인한다. xs가비어있거나아이템이하나밖에없으면정렬할필요가없다. 그렇지않으면, pivot이라고하는기준아이템을리스트에서하나고른다. 여기에서는편의상맨앞아이템을고르기로한다. ( 사실피봇값을잘골라서리스트가항상반으로쪼개질때퀵정렬의성능이가장좋으므로피봇값을고르는작업은중요하다.) 그 pivot 아이템을기준으로작은아이템은왼쪽리스트에, 큰아이템은오른쪽리스트에있도록옮긴다음리스트를쪼갠다. 왼쪽리스트를재귀적으로정렬하고, 오른쪽리스트를재귀적으로정렬한다음, pivot 아이템은그사이에끼운다. 다음프로그램은이전략을그대로적용하여, 원초적재귀함수형식으로작성한정렬함수이다. 퀵정렬하는작업은재귀함수 qsort로구현하였고, pivot 아이템을기준으로작거나같은아이템은왼쪽리스트에, 큰아이템은오른쪽리스트에있도록리스트를쪼개는작업은재귀함수 partition으로구현하였다. 1 def qsort(xs): 2 if null(xs): 18
20 3 return xs 4 else: 5 pivot = car(xs) 6 ls, rs = partition(pivot,cdr(xs)) 7 return append(qsort(ls),cons(pivot,qsort(rs))) 1 def partition(pivot,xs): 2 if null(xs): 3 return nil,nil 4 else: 5 ls, rs = partition(pivot,cdr(xs)) 6 if car(xs) <= pivot: 7 return cons(car(xs),ls), rs 8 else: 9 return ls, cons(car(xs),rs) 실행추적 qsort를호출하여계산절차을추적해보자. qsort(cons(3,cons(6,cons(5,cons(2,cons(4,cons(1,cons(8,cons(7,nil))))))))) append(qsort(cons(2,cons(1,nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(qsort(cons(1,nil)), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(append(qsort(nil),cons(1,qsort(nil)))), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(append(nil,cons(1,qsort(nil)))), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(append(nil,cons(1,nil))), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) append(append(cons(1,nil)), cons(2,qsort(nil))), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) 19
21 append(append(cons(1,nil)), cons(2,nil)), cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) cons(3,qsort(cons(6,cons(5,cons(4,cons(8,cons(7,nil)))))))) cons(3,append(qsort(cons(5,cons(4,nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(qsort(cons(4,nil)), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(append(qsort(nil),cons(4,qsort(nil))), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(append(nil,cons(4,qsort(nil))), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(append(nil,cons(4,nil)), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(cons(4,nil), cons(5,qsort(nil))), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(append(cons(4,nil), cons(5,nil)), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,qsort(cons(8,cons(7,nil))))))) cons(3,append(cons(4,cons(5,nil)), 20
22 cons(6,append(qsort(cons(7,nil)), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(append(qsort(nil), cons(7,qsort(nil))), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(append(nil, cons(7,qsort(nil))), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(append(nil, cons(7,nil)), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(cons(7,nil), cons(8,qsort(nil))))))) cons(3,append(cons(4,cons(5,nil)), cons(6,append(cons(7,nil), cons(8,nil)))))) cons(3,append(cons(4,cons(5,nil)), cons(6,cons(7,cons(8,nil)))))) cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil))))))) cons(1,cons(2,cons(3,cons(4,cons(5,cons(6,cons(7,cons(8,nil)))))))) 위의계산추적에서는 partition 함수의실행추적은자세히보여주지않았다. 하나만대표로해보자. partition(6,cons(5,cons(4,cons(8,cons(7,nil))))) xs = cons(5,cons(4,cons(8,cons(7,nil)))) ls,rs = partition(6,cons(4,cons(8,cons(7,nil)))) xs = cons(4,cons(8,cons(7,nil))) 21
23 ls,rs = partition(6,cons(8,cons(7,nil))) xs = cons(8,cons(7,nil)) ls,rs = partition(6,cons(7,nil)) xs = cons(7,nil) ls,rs = partition(6,nil) nil,nil nil,cons(car(xs),nil) nil,cons(7,nil) nil,cons(car(xs),cons(7,nil)) nil,cons(8,cons(7,nil)) cons(car(xs),nil),cons(8,cons(7,nil)) cons(4,nil),cons(8,cons(7,nil)) cons(car(xs),cons(4,nil)),cons(8,cons(7,nil)) cons(5,cons(4,nil)),cons(8,cons(7,nil)) 이함수도꼬리재귀형태로재작성해보자. 1 def partition(pivot,xs): 2 def loop(xs,ls,rs): 3 if null(xs): 4 return ls, rs 5 elif car(xs) <= pivot: 6 return loop(cdr(xs),cons(car(xs),ls),rs) 7 else: 8 return loop(cdr(xs),ls,cons(car(xs),rs)) 9 return loop(xs,nil,nil) 위와같은예로실행추적을해보면다음과같다. partition(6,cons(5,cons(4,cons(8,cons(7,nil))))) loop(cons(5,cons(4,cons(8,cons(7,nil)))),nil,nil) loop(cons(4,cons(8,cons(7,nil))),cons(5,nil),nil) loop(cons(8,cons(7,nil)),cons(4,cons(5,nil))) loop(cons(7,nil),cons(4,cons(5,nil)),cons(8,nil)) loop(nil,cons(4,cons(5,nil)),cons(7,cons(8,nil))) cons(4,cons(5,nil)),cons(7,cons(8,nil)) 결과는다르지만정렬에는영향을미치지않는다. 위의꼬리재귀함수는다음과같이 while 루프로만된함수로변환할수있다. 22
24 1 def partition(pivot,xs): 2 ls, rs = nil, nil 3 while not null(xs): 4 if car(xs) <= pivot: 5 ls = cons(car(xs),ls) 6 else: 7 rs = cons(car(xs),rs) 8 xs = cdr(xs) 9 return ls, rs 제자리정렬지금까지살펴본퀵정렬프로그램은 partition을할때마다새로운리스트를만들어나간다. 정렬대상리스트의길이가 n일때, 최선의경우 log n배에서최악의경우 n배만큼의리스트를저장할메모리를추가로사용해야한다. 정렬하면서새로운리스트를만들어가면서추가메모리를사용하는대신, 있는그자리에서서로위치만바꾸면서정렬할수있으면공간을절약할수있다. 이와같이추가공간을사용하지않고서로위치만바꾸면서하는정렬을제자리정렬 in-place sorting이라고한다. 순수리스트를조작해서는제자리정렬이불가능하다. 배열 (Python의리스트 ) 을사용하면가능하다. 제자리정렬하는퀵정렬프로그램을만들어보자. 1 def quicksort(xs): 2 def loop(xs,start,finish): 3 if start >= finish: 4 return xs 5 else: 6 pivotindex = start # 맨앞의값을 pivot으로정함 7 pivotindex = permutepivot(xs,start,finish,pivotindex) 8 xs = loop(xs,start,pivotindex-1) 9 return loop(xs,pivotindex+1,finish) 10 return loop(xs,0,len(xs)-1) 다음함수 swap(xs,i,j) 는리스트 xs 에서 i 번째값과 j 번째값을바꾼다. 1 def swap(xs,i,j): 2 xs[i], xs[j] = xs[j], xs[i] 다음함수 permutepivot(xs,start,finish,pivotindex) 는리스트 xs 의시작위치 start, 끝 위치 finish, 피봇위치 pivotindex 의인덱스를가지고, pivotindex 의값을기준으로작은값은 23
25 모두왼쪽으로옮기고, 큰값은모두오른쪽으로옮긴후, 피봇값을그사이에넣고, 그위치인텍스를결과로내준다. 1 def permute_pivot(xs,start,finish,pivot_index): 2 def loop(xs,i,j): 3 if i == j: 4 if xs[i] > pivot: 5 i = i swap(xs,start,i) 7 return i 8 else: 9 if xs[j] >= pivot: 10 return loop(xs,i,j-1) 11 else: 12 swap(xs,i,j) 13 return loop(xs,i+1,j) 14 swap(xs,start,pivot_index) 15 pivot = xs[start] 16 return loop(xs,start+1,finish) 위프로그램을 while루프로바꾸면다음과같다. 1 def permutepivot(xs,start,finish,pivotindex): 2 swap(xs,start,pivotindex) 3 pivot = xs[start] 4 i = start+1 5 j = finish 6 while i < j: 7 if xs[j] >= pivot: 8 j = j else: 10 swap(xs,i,j) 11 i = i if xs[i] > pivot: 13 i = i swap(xs,start,i) 15 return i 24
26 연습문제 집합집합을순수리스트로표현해보자. 그러면원소 x가집합 xs에속해있는지검사하는 member 함수는다음과같이작성할수있을것이다. def member(x,xs): if null(xs): return False else: return x == car(xs) or member(x,cdr(xs)) 집합에는같은원소가 2개이상있는것이의미가없으므로리스트에같은원소가반복되지않도록하면다루기간편해진다. 그러기위해서집합에원소를추가할때는다음과같이해당원소가이미집합에속해있는지검사해보고그렇지않은경우에만원소를추가해서중복을피할수있다. def add(x,xs): if member(x,xs): return xs else: return cons(x,xs) 집합에서특정원소를제거하고싶으면다음과같이원소를하나만찾아서제거하면충분하다. def remove(x,xs): if null(xs): return nil elif x == car(xs): return cdr(xs) else: return cons(car(xs),remove(x,cdr(xs))) 1. 위에서정의한 add 함수와 remove 함수를모두꼬리재귀함수로변환한뒤, while 루프형태로변환하시오. 2. 위에서정의한세함수를최대한이용하여아래의함수를작성하시오. (a) 두집합의합집합을구하는 union 함수 (b) 두집합의차집합을구하는 difference 함수 (c) 두집합의교집합을구하는 intersection 함수 25
27 묶기다음 zip 함수는두개의순수리스트를받아서그리스트의원소의쌍 ( 튜플 ) 의리스트를내주는함수이다. def zip(xs,ys): if null(xs) or null(ys): return nil else: return cons((car(xs),car(ys)),zip(cdr(xs),cdr(ys))) 다음은이함수의실행결과를보여준다. >>> zip([1,3],[2,4]) [(1, 2), (3, 4)] >>> zip([1,3,5,7],[2,4]) [(1, 2), (3, 4)] 1. 위의 zip 함수는두인수리스트의길이가다른경우긴리스트의남는부분은무시한다. 긴리스트의남는부분을아래예와같이버리지않는 sprice 함수를원초적재귀형식으로작성해보자. >>> sprice([1,3],[2,4]) [(1, 2), (3, 4)] >>> sprice([1,3,5,7],[2,4]) [(1, 2), (3, 4), (5, 5), (7, 7)] 2. zip 함수와 sprice 함수를모두꼬리재귀형식으로변환하시오. 3. zip 함수와 sprice 함수를 while 루프형식으로변환하시오. 26
쉽게 배우는 알고리즘 강의노트
쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,
슬라이드 1
CHAP 9: 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수 ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬의단위 레코드 정렬의대상 학생들의레코드 이름학번주소연락처 레코드 필드필드필드필드 키 (key) 정렬알고리즘의개요 많은정렬알고리즘존재 단순하지만비효율적인방법
Ch.8 Procedures and Environments
Chapter 9 정렬 (sorting) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 정렬 (sorting) 이란? 정의 물건을크기순으로오름차순이나내림차순으로나열하는것 컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬알고리즘의개요
-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth
-09- 쉽게배우는알고리즘 장. 정렬 Sortng http://academy.hanb.co.kr 장. 정렬 Sortng 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 한빛미디어 1 -09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다.
Algorithms
자료구조 & 알고리즘 정렬과탐색알고리즘 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 기초적인정렬알고리즘 고급정렬알고리즘 탐색알고리즘 2 정 렬 (Sort) 정렬 (sort) 의개념 순서없이배열되어있는자료들을재배열하는것 정렬의대상 : 레코드 정렬의기준 : 정렬키 (sort key) 필드 정렬방법의분류
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,
Microsoft PowerPoint - 5장 정렬
01. 버블 02. 삽입 03. 퀵 04. C 표준 라이브러리의 퀵 정렬 정렬 정렬 정렬 함수 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적이다. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬은왜하는가? 학생들의레코드 이름학번주소연락처 레코드 필드 필드 필드 필드
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 를가리키도록변경
chap x: G입력
재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19) 이진검색의재귀알고리즘
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)
설계란 무엇인가?
금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 6 강. 함수와배열, 포인터, 참조목차 함수와포인터 주소값의매개변수전달 주소의반환 함수와배열 배열의매개변수전달 함수와참조 참조에의한매개변수전달 참조의반환 프로그래밍연습 1 /15 6 강. 함수와배열, 포인터, 참조함수와포인터 C++ 매개변수전달방법 값에의한전달 : 변수값,
슬라이드 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
17장 클래스와 메소드
17 장클래스와메소드 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 17 장클래스와메소드 1 / 18 학습내용 객체지향특징들객체출력 init 메소드 str 메소드연산자재정의타입기반의버전다형성 (polymorphism) 박창이 ( 서울시립대학교통계학과 ) 17 장클래스와메소드 2 / 18 객체지향특징들 객체지향프로그래밍의특징 프로그램은객체와함수정의로구성되며대부분의계산은객체에대한연산으로표현됨객체의정의는
금오공대 컴퓨터공학전공 강의자료
C 프로그래밍프로젝트 Chap 14. 포인터와함수에대한이해 2013.10.09. 오병우 컴퓨터공학과 14-1 함수의인자로배열전달 기본적인인자의전달방식 값의복사에의한전달 val 10 a 10 11 Department of Computer Engineering 2 14-1 함수의인자로배열전달 배열의함수인자전달방식 배열이름 ( 배열주소, 포인터 ) 에의한전달 #include
슬라이드 1
Recursion SANGJI University KO Kwangman () 1. 개요 재귀 (recursion) 의정의, 순환 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로되어있는경우에적합한방법 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색
Vector Differential: 벡터 미분 Yonghee Lee October 17, 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표
Vector Differential: 벡터 미분 Yonhee Lee October 7, 08 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표기법을 정의하는 방법이다 보통 스칼라(scalar)에 대한 미분은 일분수 함수 f : < < 또는 다변수 함수(function
정보
정보 Sangwook Lee Deogi High School III 문제해결과프로그래밍 1 추상화 2 알고리즘 3 프로그래밍 2 알고리즘 2-1 알고리즘설계 2-2 알고리즘분석 3 2-1 알고리즘설계 (p.108) 학습목표 순차, 선택, 반복구조의흐름을설명할수있다. 다양한제어구조를활용하여논리적이고효율적인알고리즘을설계할수있다. 4 [1] 알고리즘제어구조 (p.109)
PowerPoint 프레젠테이션
대표적인분할정복알고리즘 4 장. 재귀호출 학습목표 재귀호출이라는개념자체를명확히이해한다. 재귀호출함수의내부구조를이해한다. 재귀호출에내재하는효율성에대해이해한다. 1 Section 01 상징적의미 - 도미노 도미노 2 도미노 100 번째것이반드시쓰러진다는사실을증명하라. 수학적귀납법 (Mathematical Induction) 처음것 (K=1) 은반드시쓰러진다. K
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
CSE117 프로그래밍기초강의노트 1 7 재귀함수 Recursive Functions 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2013년 2학기 (version 0.6) 1 c 도경구 (2013). 본문서는한양대학교 ERICA 캠퍼스컴퓨터공학과프로그래밍기초강의용으로제
CSE117 프로그래밍기초강의노트 1 7 재귀함수 Recursive Functions 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2013년 2학기 (version 0.6) 1 c 도경구 (2013). 본문서는한양대학교 ERICA 캠퍼스컴퓨터공학과프로그래밍기초강의용으로제 작되었습니다. 강의이외의용도로저자의허락없이무단복제하여배포할수없습니다. 1. 귀납정의 Inductive
정렬 강의자료
CHAP 9 : 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학을포함한모든과학기술분야에서가장기본적이고중요한알고리즘중하나 정렬은자료탐색에있어서필수적 ( 예 ) 만약영어사전에서단어들이알파벳순으로정렬되어있지않다면? 정렬의대상 일반적으로정렬시켜야될대상은레코드 (record) 레코드는다시필드 (field) 라는보다작은단위로구성 학생들의레코드
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) 란? 간접참조연산자
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)
PowerPoint 프레젠테이션
Chapter 08 함수 01 함수의개요 02 함수사용하기 03 함수와배열 04 재귀함수 함수의필요성을인식한다. 함수를정의, 선언, 호출하는방법을알아본다. 배열을함수의인자로전달하는방법과사용시장점을알아본다. 재귀호출로해결할수있는문제의특징과해결방법을알아본다. 1.1 함수의정의와기능 함수 (function) 특별한기능을수행하는것 여러가지함수의예 Page 4 1.2
제 3강 역함수의 미분과 로피탈의 정리
제 3 강역함수의미분과로피탈의정리 역함수의미분 : 두실수 a b 와폐구갂 [ ab, ] 에서 -이고연속인함수 f 가 ( a, b) 미분가능하다고가정하자. 만일 f '( ) 0 이면역함수 f 은실수 f( ) 에서미분가능하고 ( f )'( f ( )) 이다. f '( ) 에서 증명 : 폐구갂 [ ab, ] 에서 -이고연속인함수 f 는증가함수이거나감소함수이다 (
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 이항계수
Lab 3. 실습문제 (Single linked list)_해답.hwp
Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.
06_sorting
정렬 Data Structures and Algorithms 목차 버블정렬 선택정렬 삽입정렬 힙정렬 병합정렬 퀵정렬 기수정렬 Data Structures and Algorithms 2 버블정렬 Data Structures and Algorithms 3 버블정렬 Data Structures and Algorithms 4 버블정렬 Data Structures and
Microsoft PowerPoint - 제11장 포인터(강의)
쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조
비트와바이트 비트와바이트 비트 (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,
Microsoft PowerPoint 알고리즘 개요(Part 1).pptx
알고리즘 (Algorithm) 알고리즘개요 ( 효율, 분석, 차수 ) Part 1 2011년봄학기 강원대학교컴퓨터과학전공문양세 강의내용 프로그램과알고리즘순차검색과이진검색피보나찌수구하기알고리즘분석차수 (O,, ) Part 2 Page 2 프로그램의설계과정 설계분석예문제알고리즘만족? 프로그램 아니오 재설계 알고리즘은주어진문제를논리적으로해결하는과정이다. 분석을통해작성한알고리즘의정확성을파악할수있고,
Microsoft PowerPoint Android-SDK설치.HelloAndroid(1.0h).pptx
To be an Android Expert 문양세강원대학교 IT 대학컴퓨터학부 Eclipse (IDE) JDK Android SDK with ADT IDE: Integrated Development Environment JDK: Java Development Kit (Java SDK) ADT: Android Development Tools 2 JDK 설치 Eclipse
10장 리스트
10 장리스트 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 10 장리스트 1 / 32 학습내용 리스트가변성 (mutability) 가로지르기 (traversing) 연산부분추출메소드 (method) 맵, 필터, 리듀스 (map, filter, and reduce) 원소제거하기 (deleting element) 리스트와문자열객체와값별명 (aliasing)
Lab 4. 실습문제 (Circular singly linked list)_해답.hwp
Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular
11장 포인터
누구나즐기는 C 언어콘서트 제 9 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다. 첫번째바이트의주소는 0, 두번째바이트는 1, 변수와메모리
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 학습목표 포인터를 사용하는 다양한 방법에
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
< 고급 C 프로그래밍및실습 > 11 장구조체실습문제 문제에대한안내 - 특별한언급이없으면문제의조건에맞지않는입력은입력되지않는다고가정하라. - 특별한언급이없으면, 각줄의맨앞과맨뒤에는공백을출력하지않는다. - 출력예시에서 는각줄의맨앞과맨뒤에출력되는공백을의미한다. - 입출력예시
문제에대한안내 - 특별한언급이없으면문제의조건에맞지않는입력은입력되지않는다고가정하라. - 특별한언급이없으면, 각줄의맨앞과맨뒤에는공백을출력하지않는다. - 출력예시에서 는각줄의맨앞과맨뒤에출력되는공백을의미한다. - 입출력예시에서 이후는각입력과출력에대한설명이다. 11장2절 [ 문제 1 ] 3차원벡터를저장할구조체를선언후두개의 3차원벡터 (V 1, V 2 ) 를입력받으시오.
Chapter 4. LISTS
연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는
Microsoft PowerPoint - chap06-2pointer.ppt
2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.
슬라이드 1
6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,
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
<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>
계산복잡도 Computatioal Complexity 계산복잡도개론정렬문제 알고리즘의분석 어떤특정알고리즘의효율 (efficiecy 을측정 시간복잡도 (time complexity 공간복잡도 (space/memory complexity 문제의분석 일반적으로 계산복잡도분석 이란이를지칭 어떤문제에대해서그문제를풀수있는모든알고리즘의효율의하한 (lower-bou 을결정한다.
Microsoft PowerPoint - chap05-제어문.pptx
int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); 1 학습목표 제어문인,, 분기문에 대해 알아본다. 인 if와 switch의 사용 방법과 사용시 주의사항에 대해 알아본다.
0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x = (12 + 6) / 2 * 3; x = 27 x = 3 * (8 / 4
Introduction to software design 2012-1 Final 2012.06.13 16:00-18:00 Student ID: Name: - 1 - 0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x
gnu-lee-oop-kor-lec11-1-chap15
어서와 Java 는처음이지! 제 15 장컬렉션 컬렉션 (collection) 은자바에서자료구조를구현한클래스 자료구조로는리스트 (list), 스택 (stack), 큐 (queue), 집합 (set), 해쉬테이블 (hash table) 등이있다. 자바는컬렉션인터페이스와컬렉션클래스로나누어서제공한다. 자바에서는컬렉션인터페이스를구현한클래스도함께제공하므로이것을간단하게사용할수도있고아니면각자필요에맞추어인터페이스를자신의클래스로구현할수도있다.
제 5강 리만적분
제 5 강리만적분 리만적분 정의 : 두실수, 가 을만족핚다고가정하자.. 만일 P [, ] 이고 P 가두끝점, 을모두포함하는유핚집합일때, P 을 [, ] 의분핛 (prtitio) 이라고핚다. 주로 P { x x x } 로나타낸다.. 분핛 P { x x x } 의노름을다음과같이정의핚다. P x x x. 3. [, ] 의두분핛 P 와 Q 에대하여만일 P Q이면 Q
2015 개정교육과정에따른정보과평가기준개발연구 연구책임자 공동연구자 연구협력관
2015 개정교육과정에따른정보과평가기준개발연구 연구책임자 공동연구자 연구협력관 2015 개정교육과정에따른정보과평가기준개발연구 연구협력진 머리말 연구요약 차례 Ⅰ 서론 1 Ⅱ 평가준거성취기준, 평가기준, 성취수준, 예시평가도구개발방향 7 Ⅲ 정보과평가준거성취기준, 평가기준, 성취수준, 예시평가도구의개발 25 Ⅳ 정보과평가준거성취기준, 평가기준, 성취수준, 예시평가도구의활용방안
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) 를 대응시키는규칙이다.
슬라이드 1
Data Structure Chapter 1. 자료구조와알고리즘 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 자료구조와알고리즘 일상생활에서의사물의조직화 해야할일리스트 조직도 일상생활에서의사물의조직화 사전 Ticket Box 3 일상생활과자료구조의비교 일상생활 vs 자료구조 자료구조 스택 큐 리스트 사전, 탐색구조
슬라이드 1
기초 PYTHON 프로그래밍 14. 함수 - 1 1. 함수 2. 파이썬내장함수 3. 사용자정의함수 4. 함수의인수와반환값 5. 함수의위치와 main 작성하기 1. 함수 블랙박스 (black box) 함수는입력과출력을갖는 black box이다. 주어진입력에대해서어떤과정을거쳐출력이나오는지가숨겨져있다. >>> print('hello world') Hello world
설계란 무엇인가?
금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 5 강. 배열, 포인터, 참조목차 배열 포인터 C++ 메모리구조 주소연산자 포인터 포인터연산 배열과포인터 메모리동적할당 문자열 참조 1 /20 5 강. 배열, 포인터, 참조배열 배열 같은타입의변수여러개를하나의변수명으로처리 int Ary[10]; 총 10 개의변수 : Ary[0]~Ary[9]
실험 5
실험. OP Amp 의기초회로 Inverting Amplifier OP amp 를이용한아래와같은 inverting amplifier 회로를고려해본다. ( 그림 ) Inverting amplifier 위의회로에서 OP amp의 입력단자는 + 입력단자와동일한그라운드전압, 즉 0V를유지한다. 또한 OP amp 입력단자로흘러들어가는전류는 0 이므로, 저항에흐르는전류는다음과같다.
Microsoft PowerPoint - 제11장 포인터
쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조
<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >
제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다
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,
슬라이드 1
-Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역
<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>
삼각함수. 삼각함수의덧셈정리 삼각함수의덧셈정리 삼각함수 sin (α + β ), cos (α + β ), tan (α + β ) 등을 α 또는 β 의삼각함수로나 타낼수있다. 각 α 와각 β 에대하여 α >0, β >0이고 0 α - β < β 를만족한다고가정하 자. 다른경우에도같은방법으로증명할수있다. 각 α 와각 β 에대하여 θ = α - β 라고놓자. 위의그림에서원점에서거리가
Microsoft PowerPoint - chap-11.pptx
쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.
이 장에서 사용되는 MATLAB 명령어들은 비교적 복잡하므로 MATLAB 창에서 명령어를 직접 입력하지 않고 확장자가 m 인 text 파일을 작성하여 실행을 한다
이장에서사용되는 MATLAB 명령어들은비교적복잡하므로 MATLAB 창에서명령어를직접입력하지않고확장자가 m 인 text 파일을작성하여실행을한다. 즉, test.m 과같은 text 파일을만들어서 MATLAB 프로그램을작성한후실행을한다. 이와같이하면길고복잡한 MATLAB 프로그램을작성하여실행할수있고, 오류가발생하거나수정이필요한경우손쉽게수정하여실행할수있는장점이있으며,
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 물건중심프로그래밍
Microsoft PowerPoint - ch11_정렬 [호환 모드]
![Microsoft PowerPoint - ch11_정렬 [호환 모드]](/thumbs/81/84659580.jpg "Microsoft PowerPoint - ch11_정렬 [호환 모드]")
정렬 자바로배우는쉬운자료구조 이장에서다룰내용 1 정렬 6 셸정렬 2 선택정렬 7 병합정렬 3 버블정렬 8 기수정렬 4 퀵정렬 9 힙정렬 5 삽입정렬 10 트리정렬 2 정렬 (1) 정렬 (sort) 2 개이상의자료를작은것부터큰순서 ( 오름차순, ascending) 로정렬또는큰것부터작은것순서 ( 내림차순, descending) 로재배열하는것 키 : 자료를정렬하는데사용하는기준값
statistics
수치를이용한자료요약 statistics hmkang@hallym.ac.kr 한림대학교 통계학 강희모 ( 한림대학교 ) 수치를이용한자료요약 1 / 26 수치를 통한 자료의 요약 요약 방대한 자료를 몇 개의 의미있는 수치로 요약 자료의 분포상태를 알 수 있는 통계기법 사용 중심위치의 측도(measure of center) : 어떤 값을 중심으로 분포되어 있는지
PowerPoint 프레젠테이션
Chapter 06 반복문 01 반복문의필요성 02 for문 03 while문 04 do~while문 05 기타제어문 반복문의의미와필요성을이해한다. 대표적인반복문인 for 문, while 문, do~while 문의작성법을 알아본다. 1.1 반복문의필요성 반복문 동일한내용을반복하거나일정한규칙으로반복하는일을수행할때사용 프로그램을좀더간결하고실제적으로작성할수있음.
Microsoft PowerPoint - additional01.ppt [호환 모드]
![Microsoft PowerPoint - additional01.ppt [호환 모드]](/thumbs/90/102753799.jpg "Microsoft PowerPoint - additional01.ppt [호환 모드]")
1.C 기반의 C++ part 1 함수 오버로딩 (overloading) 디폴트매개변수 (default parameter) 인-라인함수 (in-line function) 이름공간 (namespace) Jong Hyuk Park 함수 Jong Hyuk Park 함수오버로딩 (overloading) 함수오버로딩 (function overloading) C++ 언어에서는같은이름을가진여러개의함수를정의가능
[ 마이크로프로세서 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](/thumbs/100/144889077.jpg "[ 마이크로프로세서 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. 함수의개념 입력에대해적절한출력을발생시켜주는것 내가 ( 프로그래머 ) 작성한명령문을연산, 처리, 실행해주는부분 ( 모듈 ) 자체적으로실행되지않으며,
OCW_C언어 기초
초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향
2007_2_project4
Programming Methodology Instructor: Kyuseok Shim Project #4: external sort with template Due Date: 0:0 a.m. between 2007-12-2 & 2007-12-3 Introduction 이프로젝트는 C++ 의 template을이용한 sorting algorithm과정렬해야할데이터의크기가
(Hyunoo Shim) 1 / 24 (Discrete-time Markov Chain) * 그림 이산시간이다연쇄 (chain) 이다왜 Markov? (See below) ➀ 이산시간연쇄 (Discrete-time chain): : Y Y 의상태공간 = {0, 1, 2,..., n} Y n Y 의 n 시점상태 {Y n = j} Y 가 n 시점에상태 j 에있는사건
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]
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으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될
Microsoft PowerPoint 세션.ppt
웹프로그래밍 () 2006 년봄학기 문양세강원대학교컴퓨터과학과 세션변수 (Session Variable) (1/2) 쇼핑몰장바구니 장바구니에서는사용자가페이지를이동하더라도장바구니의구매물품리스트의내용을유지하고있어야함 PHP 에서사용하는일반적인변수는스크립트의수행이끝나면모두없어지기때문에페이지이동시변수의값을유지할수없음 이러한문제점을해결하기위해서 PHP 에서는세션 (session)
제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.
제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.
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
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
C 언어 프로그래밊 과제 풀이
과제풀이 (1) 홀수 / 짝수판정 (1) /* 20094123 홍길동 20100324 */ /* even_or_odd.c */ /* 정수를입력받아홀수인지짝수인지판정하는프로그램 */ int number; printf(" 정수를입력하시오 => "); scanf("%d", &number); 확인 주석문 가필요한이유 printf 와 scanf 쌍
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]
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 프로그램의
PowerPoint 프레젠테이션
실습 1 배효철 th1g@nate.com 1 목차 조건문 반복문 System.out 구구단 모양만들기 Up & Down 2 조건문 조건문의종류 If, switch If 문 조건식결과따라중괄호 { 블록을실행할지여부결정할때사용 조건식 true 또는 false값을산출할수있는연산식 boolean 변수 조건식이 true이면블록실행하고 false 이면블록실행하지않음 3
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
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 관계성립
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
<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) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.
쉽게 풀어쓴 C 프로그래밍
Power Java 제 22 장제네릭과컬렉션 이번장에서학습할내용 제네릭클래스 제네릭메소드 컬렉션 ArrayList LinkedList Set Queue Map Collections 클래스 일반적인하나의코드로다양한자료형을처리하는기법을살펴봅시다. 제네릭이란? 제네릭프로그래밍 (generic programming) 다양한타입의객체를동일한코드로처리하는기법 제네릭은컬렉션라이브러리에많이사용
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",
Infinity(∞) Strategy
반복제어 표월성 passwd74@cherub.sungkyul.edu 개요 for() 문 break문과 continue문 while문 do-while문 for() 문 for() 문형식 for( 표현식1; 표현식2; 표현식3) 여러문장들 ; 표현식 1 : 초기화 (1 번만수행 ) 표현식 2 : 반복문수행조건 ( 없으면무한반복 ) 표현식 3 : 반복문수행횟수 for()
< E20C6DFBFFEBEEE20C0DBBCBAC0BB20C0A7C7D12043BEF0BEEE20492E707074>
Chap #2 펌웨어작성을위한 C 언어 I http://www.smartdisplay.co.kr 강의계획 Chap1. 강의계획및디지털논리이론 Chap2. 펌웨어작성을위한 C 언어 I Chap3. 펌웨어작성을위한 C 언어 II Chap4. AT89S52 메모리구조 Chap5. SD-52 보드구성과코드메모리프로그래밍방법 Chap6. 어드레스디코딩 ( 매핑 ) 과어셈블리어코딩방법
31. 을전개한식에서 의계수는? 를전개한식이 일 때, 의값은? 을전개했을때, 의계수와상수항의합을구하면? 을전개했을때, 의 계수는? 를전개했을때, 상수항을 구하여라. 37
21. 다음식의값이유리수가되도록유리수 의값을 정하면? 1 4 2 5 3 26. 을전개하면상수항을 제외한각항의계수의총합이 이다. 이때, 의값은? 1 2 3 4 5 22. 일때, 의값은? 1 2 3 4 5 27. 를전개하여간단히 하였을때, 의계수는? 1 2 3 4 5 23. 를전개하여 간단히하였을때, 상수항은? 1 2 3 4 5 28. 두자연수 와 를 로나누면나머지가각각
완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에
1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에대하여 AB=BA 1 가성립한다 2 3 (4) 이면 1 곱셈공식및변형공식성립 ± ± ( 복호동순 ), 2 지수법칙성립 (은자연수 ) < 거짓인명제 >
문제여섯사람이일곱개의발판위에있다. 빈발판을중심으로세사람은왼쪽에서가운데를보고서있고, 다른세사람은오른쪽에서가운데를보고서있다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 1 / 35 목표왼쪽에서있던세사람을오른쪽으로, 오른쪽에서있던사람을왼쪽으로이동한다. 가운데발판은여전히비어있어야한다. 최소의움직임으로목표를달성하도록한다.
집합 집합 오른쪽 l 3. (1) 집합 X 의각원소에대응하는집합 Y 의원소가단하나만인대응을 라할때, 이대응 를 X 에서 Y 로의라고하고이것을기호로 X Y 와같이나타낸다. (2) 정의역과공역정의역 : X Y 에서집합 X, 공역 : X Y 에서집합 Y (3) 의개수 X Y
어떤 다음 X 대응 1. 대응 (1) 어떤주어진관계에의하여집합 X 의원소에집합 Y 의원소를짝지어주는것을집합 X 에서집합 Y 로의대응이라고한다. l (2) 집합 X 의원소 에집합 Y 의원소 가짝지어지면 에 가대응한다고하며이것을기호로 와같이나타낸다. 2. 일대일대응 (1) 집합 A 의모든원소와집합 B 의모든원소가하나도빠짐없이꼭한개씩서로대응되는것을집합 A 에서집합
01장.자료구조와 알고리즘
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 자료구조와알고리즘 1/30 자료구조 일상생활에서자료를정리하고조직화하는이유는? 사물을편리하고효율적으로사용하기위함 다양한자료를효율적인규칙에따라정리한예 2/30 컴퓨터에서의자료구조 자료구조 (Data Structure) 컴퓨터에서자료를정리하고조직화하는다양한구조
C 프로그래밊 개요
함수 (2) 2009 년 9 월 24 일 김경중 공지사항 10 월 1 일목요일수업휴강 숙제 #1 마감 : 10 월 6 일화요일 기초 함수를만들어라! 입력 함수 ( 기능수행 ) 반환 사용자정의함수 정의 : 사용자가자신의목적에따라직접작성한함수 함수의원형 (Function Prototype) + 함수의본체 (Function Body) : 함수의원형은함수에대한기본적정보만을포함
확률 및 분포
확률및분포 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 확률및분포 1 / 15 학습내용 조건부확률막대그래프히스토그램선그래프산점도참고 박창이 ( 서울시립대학교통계학과 ) 확률및분포 2 / 15 조건부확률 I 첫째가딸일때두아이모두딸일확률 (1/2) 과둘중의하나가딸일때둘다딸일확률 (1/3) 에대한모의실험 >>> from collections import
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
Microsoft PowerPoint SDK설치.HelloAndroid(1.5h).pptx
To be an Android Expert 문양세강원대학교 IT 대학컴퓨터학부 개발환경구조및설치순서 JDK 설치 Eclipse 설치 안드로이드 SDK 설치 ADT(Androd Development Tools) 설치 AVD(Android Virtual Device) 생성 Hello Android! 2 Eclipse (IDE) JDK Android SDK with
슬라이드 1
Data Structure & Algorithms SANGJI University KO Kwangman () 자료 (data) 1. 자료와정보 현실세계로부터의단순한관찰이나측정을통하여수집한사실이나개념의값들또는값들의집합. 정보 (information) 의사결정에도움을주기위해유용한형태로다시작성된 (= 가공 ) 자료. Data Structure & Algorithms
WISHBONE System-on-Chip Interconnection Architecture for Portable IP Cores
프로젝트정리 1주차 : 미로를텍스트파일로만들어출력하는프로그램작성. 2주차 : 텍스트형태의미로를 MC의그래픽기능을이용하여그리는프로그램작성. 3주차 : 미로에서길찾는프로그램작성. Dept. of CS, Sogang Univ. 1 DS를이용한미로길찾기문제 DS를이용한미로길찾기문제는 2주차까지설계한미로의출발점과도착점을연결하는가장짧은경로를탐색해출력하는문제이다. NxM
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
18강.hwp
------------------8강 데이터 관리------------------ **주요 키워드 ** () 레코드관리 () 정렬 () 자동필터, 고급필터 () 그룹과 윤곽설정, 텍스트나누기, 외부데이터 () 레코드관리********************************** [08/]. 다음 중 [데이터]-[레코드 관리]에 대한 설명으로 옳지 않은 것