<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>

Size: px
Start display at page:

Download "<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>"

Transcription

1 계산복잡도 Computatioal Complexity 계산복잡도개론정렬문제 알고리즘의분석 어떤특정알고리즘의효율 (efficiecy 을측정 시간복잡도 (time complexity 공간복잡도 (space/memory complexity 문제의분석 일반적으로 계산복잡도분석 이란이를지칭 어떤문제에대해서그문제를풀수있는모든알고리즘의효율의하한 (lower-bou 을결정한다. 알고리즘강의슬라이드 7 보기 : 행렬곱셈문제 일반알고리즘 : Θ( 3 Strasse의알고리즘 : Θ(.8 Coppersmith/Wiogra 의알고리즘 : Θ(.38 이문제의복잡도의하한은 Ω( 더빠른알고리즘이존재할까? 아직이하한만큼좋은알고리즘을찾지못하였고, 그렇다고하한이이보다더큰지도알아내지못하였다. 계산복잡도 복잡도하한이 Ω(f( 인문제에대해서복잡도가 Θ(f( 인알고리즘을만들어내는것이목표이다. 다시말하면, 문제의복잡도하한보다낮은알고리즘을만들어낸다는것은불가능하다. ( 물론상수적으로알고리즘을향상시키는것은가능하다. 보기 : 정렬문제 (sortig 교환정렬 (Exchage sort: Θ( 합병정렬 (ergesort: Θ( lg 정렬문제의시간복잡도하한은 Ω( lg ( 키를비교하여정렬하는경우에만해당됨 이정렬문제의경우는하한만큼의시간복잡도를가진알고리즘을찾았다. 알고리즘강의슬라이드 7 3 알고리즘강의슬라이드 7 삽입정렬알고리즘 Isertio Sort 이미정렬된배열에항목을끼워넣음으로서정렬하는알고리즘예 알고리즘 : 삽입정렬 문제 : 비내림차순을 개의키를정렬 입력 : 양의정수 ; 키의배열 S[..] 출력 : 비내림차순으로정렬된키의배열 S[..] 알고리즘강의슬라이드 7 5 알고리즘강의슬라이드 7 6

2 삽입정렬알고리즘 voi isertiosort(it, keytype S[]{ iex i,; keytype x; for(i; i<; i++{ x S[i]; i - ; while(>0 && S[]>x{ S[+] S[]; --; S[+] x; 알고리즘강의슬라이드 7 7 삽입정렬알고리즘의분석 최악의경우시간복잡도분석 - 비교하는횟수를기준 : i가주어졌을때, while-루프에서최대한 i-번의비교가이루어진다. 그러면비교하는총횟수는최대한 ( W ( ( i i 평균의경우시간복잡도분석 - 비교하는횟수를기준 : i가주어졌을때, x가삽입될수있는장소가i개있다. 삽입할장소의인덱스 비교횟수 i i x를삽입하는데필요한비교횟수는 : i i ( i i i i L + ( i + ( i k + + i i i i i k i i i i 따라서정렬하는데필요한평균비교횟수는 : i + i + ( + ( ( l i i i i i 공간복잡도분석 : 저장장소가추가로필요하지않다. 따라서 ( Θ(. - 제자리정렬 (i-place sortig 추가로소요되는저장장소의크기가상수인경우. L L i i 알고리즘강의슬라이드 7 8 선택정렬알고리즘 Selectio Sort 문제 : 비내림차순으로 개의키를정렬입력 : 양의정수 ; 키의배열 S[..] 출력 : 비내림차순으로정렬된키의배열 S[..] voi selectiosort(it, keytype S[]{ iex i,,smallest; for(i; i<-; i++{ smallest i; for(i+; <; ++ if(s[]<s[smallest] smallest ; exchage S[i] a S[smallest]; 알고리즘강의슬라이드 7 9 선택정렬알고리즘의분석 모든경우시간복잡도분석 - 비교하는횟수를기준 : i가 일때비교횟수는 -, i가 일때비교횟수는 -,, i 가 - 일때비교횟수는 이 ( 된다. 이를모두합하면, 이다. 따라서 T ( 모든경우시간복잡도분석 - 지정 (assigmet 하는횟수를기준 : 번교환하는데 3번지정하므로 T ( 3( 알고리즘강의슬라이드 7 0 Θ(( 정렬알고리즘의비교 알고리즘 비교횟수 지정횟수 추가저장장소사용량 교환정렬 T( / W( 3 / 제자리정렬 A( 3 / 삽입정렬 W( / W( / 제자리정렬 A( / A( / 선택정렬 T( / T( 3 제자리정렬 삽입정렬은교환정렬보다는항상최소한빠르게수행된다고할수있다. 선택정렬이교환정렬보다빠른가? - 일반적으로는선택정렬알고리즘이빠르다고할수있다. 그러나입력이이미정렬되어있는경우, 선택정렬은지정이이루어지지만교환정렬은지정이이루어지지않으므로교환정렬이빠르다. 선택정렬알고리즘이삽입정렬알고리즘보다빠른가? - 의크기가크고, 키의크기가큰자료구조일때는지정하는시간이많이걸리므로선택정렬알고리즘이더빠르다. 한번비교하는데최대한하나의역을제거하는알고리즘의하한선 개의별개의 ( 다른 키를정렬하는데, 정렬할키들을단순히양의정수,,, 이라고가정해도보편성이희생되지않는다. 개의양수는! 개의순열 (permutatio 이존재한다. 다시말하면,! 가지의다른순서로배열할수있다는뜻이다. k i 를 i번째자리에위치한정수라고할때, 순열은 [k, k,, k ] 으로나타낼수있다. 예를들면, [3,, ] 는 k 3, k, k 3 로표시할수있다. i < 와 k i > k 의조건을만족하는쌍 (pair (k i, k 를순열에존재하는역 (iversio 이라고한다. 예를들어순열 [3,,,, 6, 5] 에는몇개의역이존재할까? 답 : 5개 알고리즘강의슬라이드 7 알고리즘강의슬라이드 7

3 한번비교하는데최대한하나의역을제거하는알고리즘의하한선 정리 7: 7.: 서로다른 개의키를키끼리비교하여정렬할때, 매번비교할때마다기껏해야하나의역만을제거하는알고리즘은최악의경우에최소한 (( 의비교를수행해야하고평균적으로최소한 ( 의비교를수행해야한다. 알고리즘강의슬라이드 7 3 한번비교하는데최대한하나의역을제거하는알고리즘의하한선 증명 : 경우 : ( 최악의경우 (-/개의역을가진순열이존재한다고보이면충분하다. 왜냐하면그러한순열이있으면알고리즘이그만큼의역을제거해야하고, 따라서최소한그만큼의비교를수행해야하기때문이다. 그러한순열은 :[ [, -,,, ]. 경우 : ( 평균적으로 어떤임의의순열 P [k, k,, k ] 이있을때, 그순열을뒤집어놓으면 (traspose P T [k,, k, k ] 이된다. 이때어떤역이되는쌍 (pair (s, r 은반드시 P에속하거나, 아니면 P T 에속하게된다. 그러면 P와 P T 에는정확하게총 (-/ 개의역이존재하게된다. 따라서 P 와 P T 에존재하는역의평균개수는 (-/이된다. 여기서알고리즘이매번비교할때마다기껏해야하나의역만을제거한다고가정하였으므로, 알고리즘이모든역을제거하기위해서는최소한역의개수만큼의비교를평균적으로수행해야한다. 따라서정렬하는데도그만큼의비교를수행해야한다. 교환, 삽입, 선택정렬은한번비교할때기껏해야하나의역이상은제거할수없으 ( ( 므로시간복잡도가최악의경우, 평균적으로는보다좋을수없다. 알고리즘강의슬라이드 7 합병정렬알고리즘재검토 합병정렬 (ergesort 에서는한번비교해서하나이상의역을제거하는경우가있다. 예를들어, 두부분배열 [3,] 과 [,] 를합병해보자. 3과 을비교한후에 은배열의첫번째자리에놓게되고, 따라서두개의역인 (3, 과 (, 을동시에제거하게된다. 다음, 3과 를비교한후에 는배열의두번째자리에놓게되고, 따라서두개의역인 (3, 와 (, 를동시에제거하게된다. 키를비교하는횟수를기준으로시간복잡도를계산하면 : W ( A( Θ( lg 키를지정하는횟수를기준으로 ( 모든경우 시간복잡도를계산하면 : T ( lg 공간복잡도 : ( Θ( - 제자리정렬이아님. 알고리즘강의슬라이드 7 5 빠른정렬알고리즘재검토 키를비교하는횟수를기준으로시간복잡도를계산하면 : W ( Θ ( a A (.38( + lg 키를지정하는횟수를기준으로 ( 모든경우 시간복잡도를계산하면 : A ( ( + lg 공간복잡도 : 이알고리즘은합병정렬알고리즘과비교해서추가적인배열이필요하지않는장점이있다. 그러나합병정렬과는달리배열이정확하게반으로나누어지지않으므로, 한쪽의부분배열을정렬할때, 다른한쪽의부분배열의첫번과마지막인덱스를활성레코드 (activatio recor 스택에저장하여둘필요가있다. 따라서추가적으로필요한저장장소는최악의경우 ( Θ ( 가된다. 따라서제자리정렬알고리즘이라고할수없다. 그러나추가적으로필요한저장장소가 ( Θ(lg 가되도록알고리즘수정이가능하다. 알고리즘강의슬라이드 7 6 힙정렬 ( Heapsort 알고리즘 완전이진트리 (complete biary tree: 트리의내부에있는모든마디에두개씩자식마디가있는이진트리. 따라서모든잎의깊이 (epth 는동일하다. 실질적인완전이진트리 (essetially complete biary tree 깊이 -까지는완전이진트리이고, 깊이 의마디는왼쪽끝에서부터채워진이진트리. 힙의성질 (heap pproperty: p 어떤마디에저장된값은그마디의자식마디에저장된값보다크거나같다. 힙 (heap: 힙의성질을만족하는실질적인완전이진트리 보기 알고리즘강의슬라이드 7 7 알고리즘강의슬라이드 7 8

4 보기 : siftow 알고리즘강의슬라이드 7 9 힙정렬 알고리즘 : 힙정렬 (Heapsort voi siftow(heap& H{ oe paret, largerchil; paret root of H; largerchil paret s chil cotaiig larger key; while(key at paret is smaller tha key at largerchil{ exchage key at paret a key at largerchil; paret largerchil; largerchil paret s chil cotaiig larger key; keytype root(heap& H{ keytype keyout; keyout key at the root; move the key at the bottom oe to the root; elete the bottom oe; siftow(h; retur keyout; 알고리즘강의슬라이드 7 0 보기 : makeheap 알고리즘강의슬라이드 7 힙정렬 voi removekeys(it, heap H, keytype S[]{ iex i; for(i; i>; i-- S[i] root(h; voi makeheap(it, heap& H{ iex i; heap Hsub; for(i-; i>0; i-- for(all subtree Hsub whose roots have epth i siftow(hsub; voi heapsort(it, heap H, keytype S[]{ makeheap(,h; removekeys(,h,s; 알고리즘강의슬라이드 7 힙정렬알고리즘의공간복잡도 이알고리즘이제자리정렬알고리즘인가? 다음과같이힙을배열로구현한경우에는제자리정렬알고리즘이다. 공간복잡도 : Θ( 실질적인완전이진트리를배열로표현하는방법 : 어떤마디를인덱스 i 에넣는다면왼쪽자식마디의인덱스는 i 이다. 어떤마디를인덱스 i 에넣으면오른쪽자식마디는 i+에넣는다. 알고리즘 : 제자리 voi heapsort(it, heap& H{ makeheap(,h; removekeys(,h,h.s; 완전이진트리 배열 알고리즘강의슬라이드 7 3 알고리즘강의슬라이드 7

5 최악의경우시간복잡도분석 - 비교하는횟수를기준 : 단위연산 : siftow 프로시저에서의키의비교 입력크기 :, 총키의개수 makeheap와 removekeys 모두 siftow을부르므로따로분석을한다. makeheap 의분석 : k 라가정. 를실질적인완전이진트리의깊이라고하면, lg. 이때 의깊이를가진마디는정확히하나이고그마디는 개의조상 (acestor 을가진다. 일단깊이가 인그마디가없다고가정하고키가 sift 되는상한값 (upper bou 을구해보자. epth oe 수 0 0 키가sift되는최대횟수 3 0 알고리즘강의슬라이드 7 5 따라서키가 sift되는총횟수는 ( 를넘지않는다. 이를 0 i + i + 와 i ( + 를이용하여계산해보면, i 0 i 0 ( ( 0 여기에다깊이가 인마디하나가뿌리까지 sift되는횟수 ( 상한값 를더하면, 이된다. 그런데한번 sift될때마다 번씩비교하므로실제비교횟수는 (- 이된다. removekeys 의분석 : k 라가정. 먼저 8이고 lg 8 3인경우를생각해보자. 처음 개의키를제거하는데 sift되는횟수가 회, 다음 개의키를제거하는데 sift되는횟수가 회, 그리고마지막 개의키를제거하는데는 sift 되지않았다. 따라서총 sift 횟수는 ( + ( 3 가된다. 따라서일반적인경우는 0 0 ( + + lg + 가된다. 그런데한번 sift될때마다번씩비교하므로실제비교횟수는 lg + 이된다. 두분석의통합 : 키를비교하는총횟수는 이 k 일때(- + lg - + ( lg - + lg 을넘지않는다. 따라서최악의경우 W( Θ( lg. 일반적으로모든 에대해서도 W( Θ(( ( lg 이라고할수있는데, 왜냐하면 W( 은결국은증가함수 ( 부록B. 이기때문이다. 알고리즘강의슬라이드 7 6 Θ( lg 알고리즘의비교 알고리즘 비교횟수 지정횟수 추가저장장소사용량 합병정렬 W( A( lg T( lg Θ( 빠른정렬 W( / Θ(lg A(.38 lg A( 0.69 lg 힙정렬 W( A( lg W( A( lg 제자리정렬 알고리즘강의슬라이드 7 7 알고리즘강의슬라이드 7 8 키의비교만으로정렬하는경우하한 lg 보다더빠른정렬알고리즘을개발할수있을까? 키의비교횟수를기준으로하는한, 더빠른알고리즘은불가능하다. 정렬알고리즘에대한결정트리 3개의키를정렬하는알고리즘을생각해보자. 그 3개의키를각각 a,b,c 라고한다면다음과같은결정트리 (ecisio tree 를그릴수있다. 알고리즘 : 교환정렬 문제 : 비내림차순으로 개의키를정렬입력 : 양수, 배열 S[..] ] 출력 : 비내림차순으로정렬된배열알고리즘 : voi exchagesort (it, keytype S[] { iex i, ; for (i ; i < -; i++ for ( i+; < ; ++ if (S[] < S[i] exchage S[i] a S[]; 알고리즘강의슬라이드 7 9 알고리즘강의슬라이드 7 30

6 키의비교만으로정렬하는경우하한 개의키를정렬하기위한결정트리를생각해보자. 만약 개의키의각순열 (permutatio 에대해서, 뿌리마디로부터잎마디로이르는그순열을정렬하는경로가있는경우, 그결정트리는유효하다 (vali 고한다. 즉, 크기가 인어떤입력에대해서도정렬할수있다. 그러면 3개의입력을정렬하는교환정렬알고리즘의결정트리는어떤모양을가질까? 여기서잘살펴보면교환정렬에서는꼭하지않아도될비교를하고있다. 왜냐하면교환정렬에서는어떤시점에서비교가이루어질때, 그이전에이루어졌던비교의결과를전혀알수없기때문이다. 이러한현상은최적 (optimal 이아닌알고리즘에서주로나타난다. 가지친결정트리 (prue ecisio i tree: 일관성있는순서로결정을내림으로서뿌리마디로부터모든잎마디에도달할수있는경우. 다음에있는결정트리는가지친 (prue 결정트리이다. 보조정리 7.: 개의서로다른키를정렬하는결정적 (etermiistic 알고리즘은, 그에상응하는정확하게! 개의잎마디를가진, 유효하며가지친이진결정트리가존재한다. 알고리즘강의슬라이드 7 3 알고리즘강의슬라이드 7 3 최악의경우하한 보조정리 7: 7.: 결정트리에의해서수행된최악의경우비교횟수는그결정트리의깊이와같다. 보조정리 7.3: 이진트리 (biary tree 의잎마디의수가 m이고, 깊이가 이면, lg m 이다. 증명 : 에대하여귀납법으로증명. 우선 m임을먼저보인다. 귀납출발점 : 0: 마디의수가하나인이진트리. 따라서명백히. 귀납가정 : 깊이가 인모든이진트리에대하서, m 가성립한다고가정. 귀납절차 : 깊이가 + 인모든이진트리에대해서, m 임을보이면된다. 여기서 m 은잎마디의수이다. + m 귀납가정에의해서성립 m 각부모다디는기껏해야자식마디 개를가지므로 그러므로 m 이성립한다. 여기서양변에 lg 를씌우면, lg m 이된다. 그런데 는정수이므로, lg m 이된다. 알고리즘강의슬라이드 7 33 최악의경우하한 정리 7.: 개의서로다른키를비교함으로만정렬하는결정적알고리즘은최악의경우최소한 lg 번의비교를수행한다. 증명 : 보조정리 7.에의하면,! 개의잎마디를가진가지친, 유효한, 이진결정트리가존재한다. 다시보조정리 7.3에의하면, 그트리의깊이는 lg (! 가되고, 그러면 lg(! lg[ ( ( L ] i lg i lg x x ( l + l lg. 5 따라서보조정리 7.에의해서, 결정트리의최악의경우의비교횟수는그트리의깊이와같다. 증명끝. 알고리즘강의슬라이드 7 3 정렬알고리즘의분류 선택하여정렬하는부류의알고리즘 순서대로항목을선택하여적절한곳에위치시키는알고리즘. 교환정렬, 삽입정렬, 선택정렬, 힙정렬알고리즘이이부류에속한다. 공간복잡도는모두 Θ( ( 이다. 모두제자리정렬알고리즘자리를바꾸어서정렬하는부류의알고리즘 인접해있는항목을교환하여서 ( 자리를바꾸어서 정렬이수행되는알고리즘. 거품정렬 (Bubble Sort(Θ(, 합병정렬, 빠른정렬알고리즘이이부류에속한다. 거품정렬을제외하고는모두제자리정렬알고리즘이아니다. 알고리즘강의슬라이드 7 35 분배에의한정렬 : 기수정렬 키에대해서아무런정보가없는경우에는키들을비교하는것이외에는다른방법이없으므로 Θ( lg 보다더좋은알고리즘을만드는것은불가능하다. 그러나키에대한어느정도의정보를알고있는경우에는상황이조금달라질수있다. 가령키들이음이아닌수이고디지트 (igit 의개수가모두같다면, 첫번째디지트가같은수끼리따로모으고, 그중에서두번째디지트가같은수끼리따로모으고, 마지막디지트가지이런식으로계속모은다면, 각디지트를한번씩만조사를하면정렬을완료할수있다. 다음에예가제시되어있는데, 이런방법으로정렬하는것을 분배에의한정렬 (sortig by istributio - 기수정렬 (raix sort - 이라고한다. 알고리즘강의슬라이드 7 36

7 보기 - 기수정렬 기수정렬알고리즘 이와같이정렬하는경우항상뭉치 (pile 를구성하는개수가일정하지않으므로관리하기가쉽지않다. 이를해결하기위해서는다음예와같이끝에있는디지트부터먼저조사를시작하면된다. 알고리즘강의슬라이드 7 37 알고리즘강의슬라이드 7 38 기수정렬알고리즘의분석 단위연산 : 뭉치에수를추가하는연산입력크기 : 정렬하는정수의개수, 각정수를이루는디지트의최대개서 umigits 모든경우시간복잡도분석 : T ( umigits ( + 0 Θ( umigits 따라서 umigits가 과같으면, 시간복잡도는 Θ( 가된다. 그러나일반적으로서로다른 개의수가있을때그것을표현하는데필요한디지트의수는 lg 으로볼수있다. 예 : 주민등록번호는 3개의디지트로되어있는데, 표현할수있는개수는 0,000,000,000,000,,, 개이다. 이 0조개의번호를기수정렬하는데걸리는시간은 0,000,000,000,000 log 0 0,000,000,000,000 30조공간복잡도분석 추가적으로필요한공간은키를연결된리스트로만드는데필요한공간, 즉, Θ( 알고리즘강의슬라이드 7 39

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

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

More information

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

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

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

슬라이드 1

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

More information

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에대하여 AB=BA 1 가성립한다 2 3 (4) 이면 1 곱셈공식및변형공식성립 ± ± ( 복호동순 ), 2 지수법칙성립 (은자연수 ) < 거짓인명제 >

More information

Algorithms

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

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

정보

정보 정보 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

Ch.8 Procedures and Environments

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

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

슬라이드 1

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

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

슬라이드 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

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

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

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

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

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

Vector Differential: 벡터 미분 Yonghee Lee October 17, 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표

Vector Differential: 벡터 미분 Yonghee Lee October 17, 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표 Vector Differential: 벡터 미분 Yonhee Lee October 7, 08 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표기법을 정의하는 방법이다 보통 스칼라(scalar)에 대한 미분은 일분수 함수 f : < < 또는 다변수 함수(function

More information

PowerPoint Presentation

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

More information

1 경영학을 위한 수학 Final Exam 2015/12/12(토) 13:00-15:00 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오. 1. (각 6점) 다음 적분을 구하시오 Z 1 4 Z 1 (x + 1) dx (a) 1 (x 1)4 dx 1 Solut

1 경영학을 위한 수학 Final Exam 2015/12/12(토) 13:00-15:00 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오. 1. (각 6점) 다음 적분을 구하시오 Z 1 4 Z 1 (x + 1) dx (a) 1 (x 1)4 dx 1 Solut 경영학을 위한 수학 Fial Eam 5//(토) :-5: 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오.. (각 6점) 다음 적분을 구하시오 4 ( ) (a) ( )4 8 8 (b) d이 성립한다. d C C log log (c) 이다. 양변에 적분을 취하면 log C (d) 라 하자. 그러면 d 4이다. 9 9 4 / si (e) cos si

More information

Microsoft PowerPoint - 5장 정렬

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

More information

Chap 6: Graphs

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

More information

슬라이드 1

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

More information

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

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

More information

제 3강 역함수의 미분과 로피탈의 정리

제 3강 역함수의 미분과 로피탈의 정리 제 3 강역함수의미분과로피탈의정리 역함수의미분 : 두실수 a b 와폐구갂 [ ab, ] 에서 -이고연속인함수 f 가 ( a, b) 미분가능하다고가정하자. 만일 f '( ) 0 이면역함수 f 은실수 f( ) 에서미분가능하고 ( f )'( f ( )) 이다. f '( ) 에서 증명 : 폐구갂 [ ab, ] 에서 -이고연속인함수 f 는증가함수이거나감소함수이다 (

More information

Microsoft PowerPoint Branch-and-Bound.ppt

Microsoft PowerPoint Branch-and-Bound.ppt 알고리즘 (Algorithm) ( 분기한정 ) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) 강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming

More information

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조 - Part2- 제 2 장다차원배열이란무엇인가 학습목차 2.1 다차원배열이란 2. 2 2 차원배열의주소와값의참조 2.1 다차원배열이란 2.1 다차원배열이란 (1/14) 다차원배열 : 2 차원이상의배열을의미 1 차원배열과다차원배열의비교 1 차원배열 int array [12] 행 2 차원배열 int array [4][3] 행 열 3 차원배열 int array [2][2][3]

More information

Microsoft PowerPoint - 04알고리즘

Microsoft PowerPoint - 04알고리즘 이산수학 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

Microsoft PowerPoint - 04알고리즘

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

More information

<3235B0AD20BCF6BFADC0C720B1D8C7D120C2FC20B0C5C1FE20322E687770>

<3235B0AD20BCF6BFADC0C720B1D8C7D120C2FC20B0C5C1FE20322E687770> 25 강. 수열의극한참거짓 2 두수열 { }, {b n } 의극한에대한 < 보기 > 의설명중옳은것을모두고르면? Ⅰ. < b n 이고 lim = 이면 lim b n =이다. Ⅱ. 두수열 { }, {b n } 이수렴할때 < b n 이면 lim < lim b n 이다. Ⅲ. lim b n =0이면 lim =0또는 lim b n =0이다. Ⅰ 2Ⅱ 3Ⅲ 4Ⅰ,Ⅱ 5Ⅰ,Ⅲ

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

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

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

04 Çмú_±â¼ú±â»ç

04 Çмú_±â¼ú±â»ç 42 s p x f p (x) f (x) VOL. 46 NO. 12 2013. 12 43 p j (x) r j n c f max f min v max, j j c j (x) j f (x) v j (x) f (x) v(x) f d (x) f (x) f (x) v(x) v(x) r f 44 r f X(x) Y (x) (x, y) (x, y) f (x, y) VOL.

More information

슬라이드 1

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

More information

PowerPoint Presentation

PowerPoint Presentation 5 불대수 IT CookBook, 디지털논리회로 - 2 - 학습목표 기본논리식의표현방법을알아본다. 불대수의법칙을알아본다. 논리회로를논리식으로논리식을논리회로로표현하는방법을알아본다. 곱의합 (SOP) 과합의곱 (POS), 최소항 (minterm) 과최대항 (mxterm) 에대해알아본다. 01. 기본논리식의표현 02. 불대수법칙 03. 논리회로의논리식변환 04.

More information

입학사정관제도

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

More information

Microsoft PowerPoint Greedy Method.ppt

Microsoft PowerPoint Greedy Method.ppt 알고리즘 (Algorithm) ( 탐욕적방법 ) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 2 1 탐욕적알고리즘개요

More information

Microsoft PowerPoint - 제8장-트리.pptx

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

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

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

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

More information

이 장에서 사용되는 MATLAB 명령어들은 비교적 복잡하므로 MATLAB 창에서 명령어를 직접 입력하지 않고 확장자가 m 인 text 파일을 작성하여 실행을 한다

이 장에서 사용되는 MATLAB 명령어들은 비교적 복잡하므로 MATLAB 창에서 명령어를 직접 입력하지 않고 확장자가 m 인 text 파일을 작성하여 실행을 한다 이장에서사용되는 MATLAB 명령어들은비교적복잡하므로 MATLAB 창에서명령어를직접입력하지않고확장자가 m 인 text 파일을작성하여실행을한다. 즉, test.m 과같은 text 파일을만들어서 MATLAB 프로그램을작성한후실행을한다. 이와같이하면길고복잡한 MATLAB 프로그램을작성하여실행할수있고, 오류가발생하거나수정이필요한경우손쉽게수정하여실행할수있는장점이있으며,

More information

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>

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

More information

2/21

2/21 지주회사 LG의 설립과정 및 특징 소유구조를 중심으로 이은정_좋은기업지배구조연구소 기업정보실장 이주영_좋은기업지배구조연구소 연구원 1/21 2/21 3/21 4/21 5/21 6/21 7/21 8/21 9/21 10/21 11/21 12/21 13/21 14/21 15/21 16/21 17/21 18/21 19/21 20/21 [별첨1] 2000.12.31.현재

More information

슬라이드 1

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

More information

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

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

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

제 11 장 다원 탐색 트리

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

More information

(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 에있는사건

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

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

14장.탐색

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

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

정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [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

정렬 강의자료

정렬 강의자료 CHAP 9 : 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학을포함한모든과학기술분야에서가장기본적이고중요한알고리즘중하나 정렬은자료탐색에있어서필수적 ( 예 ) 만약영어사전에서단어들이알파벳순으로정렬되어있지않다면? 정렬의대상 일반적으로정렬시켜야될대상은레코드 (record) 레코드는다시필드 (field) 라는보다작은단위로구성 학생들의레코드

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

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

슬라이드 1

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

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

7장

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

More information

제 5강 리만적분

제 5강 리만적분 제 5 강리만적분 리만적분 정의 : 두실수, 가 을만족핚다고가정하자.. 만일 P [, ] 이고 P 가두끝점, 을모두포함하는유핚집합일때, P 을 [, ] 의분핛 (prtitio) 이라고핚다. 주로 P { x x x } 로나타낸다.. 분핛 P { x x x } 의노름을다음과같이정의핚다. P x x x. 3. [, ] 의두분핛 P 와 Q 에대하여만일 P Q이면 Q

More information

슬라이드 1

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

More information

chap x: G입력

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

More information

Sequences with Low Correlation

Sequences with Low Correlation 레일리페이딩채널에서의 DPC 부호의성능분석 * 김준성, * 신민호, * 송홍엽 00 년 7 월 1 일 * 연세대학교전기전자공학과부호및정보이론연구실 발표순서 서론 복호화방법 R-BP 알고리즘 UMP-BP 알고리즘 Normalied-BP 알고리즘 무상관레일리페이딩채널에서의표준화인수 모의실험결과및고찰 결론 Codig ad Iformatio Theory ab /15

More information

제 12강 함수수열의 평등수렴

제 12강 함수수열의 평등수렴 제 강함수수열의평등수렴 함수의수열과극한 정의 ( 점별수렴 ): 주어진집합 과각각의자연수 에대하여함수 f : 이있다고가정하자. 이때 을집합 에서로가는함수의수열이라고한다. 모든 x 에대하여 f 수열 f ( x) lim f ( x) 가성립할때함수수열 { f } 이집합 에서함수 f 로수렴한다고한다. 또 함수 f 을집합 에서의함수수열 { f } 의극한 ( 함수 ) 이라고한다.

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

최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예 4.1 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 12 +4x 13 +7x 14 +2x x 34 +8x 35 +5x 45 sub.to x 12 +x 13 +x

최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예 4.1 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 12 +4x 13 +7x 14 +2x x 34 +8x 35 +5x 45 sub.to x 12 +x 13 +x 최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예. 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 2 +x +7x +2x 25 +0x +8x 5 +5x 5 sub.to x 2 +x +x = 0, x 2 +x 25 =, x +x +x 5 = -, x x +x 5 = -, x 25 x 5 x 5 = -7, x 2 apple,

More information

본 강의에 들어가기 전

본 강의에 들어가기 전 1 2.1 대칭암호원리 제 2 장. 대칭암호와메시지기밀성 2 3 기본용어 평문 (Plaintext) - original message 암호문 (Ciphertext) - coded message 암호화 (Cipher) - algorithm for transforming plaintext to ciphertext 키 (Key) - info used in cipher

More information

슬라이드 1

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

More information

설계란 무엇인가?

설계란 무엇인가? 금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 5 강. 배열, 포인터, 참조목차 배열 포인터 C++ 메모리구조 주소연산자 포인터 포인터연산 배열과포인터 메모리동적할당 문자열 참조 1 /20 5 강. 배열, 포인터, 참조배열 배열 같은타입의변수여러개를하나의변수명으로처리 int Ary[10]; 총 10 개의변수 : Ary[0]~Ary[9]

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

체의원소를계수로가지는다항식환 Theorem 0.1. ( 나눗셈알고리듬 (Division Algorithm)) F 가체일때 F [x] 의두다항식 f(x) = a 0 + a 1 x + + a n x n, a n 0 F 와 g(x) = b 0 + b 1 x + + b m x

체의원소를계수로가지는다항식환 Theorem 0.1. ( 나눗셈알고리듬 (Division Algorithm)) F 가체일때 F [x] 의두다항식 f(x) = a 0 + a 1 x + + a n x n, a n 0 F 와 g(x) = b 0 + b 1 x + + b m x 체의원소를계수로가지는다항식환 Theorem 0.1. ( 나눗셈알고리듬 (Division Algorithm)) F 가체일때 F [x] 의두다항식 f(x) = a 0 + a 1 x + + a n x n, a n 0 F 와 g(x) = b 0 + b 1 x + + b m x m, b m 0 F, m > 0 에대해 f(x) = g(x)q(x) + r(x) 을만족하는

More information

18강.hwp

18강.hwp ------------------8강 데이터 관리------------------ **주요 키워드 ** () 레코드관리 () 정렬 () 자동필터, 고급필터 () 그룹과 윤곽설정, 텍스트나누기, 외부데이터 () 레코드관리********************************** [08/]. 다음 중 [데이터]-[레코드 관리]에 대한 설명으로 옳지 않은 것

More information

2_안드로이드UI

2_안드로이드UI 03 Layouts 레이아웃 (Layout) u ViewGroup의파생클래스로서, 포함된 View를정렬하는기능 u 종류 LinearLayout 컨테이너에포함된뷰들을수평또는수직으로일렬배치하는레이아웃 RelativeLayout 뷰를서로간의위치관계나컨테이너와의위치관계를지정하여배치하는레이아웃 TableLayout 표형식으로차일드를배치하는레이아웃 FrameLayout

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

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

08장.트리

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

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

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

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

31. 을전개한식에서 의계수는? 를전개한식이 일 때, 의값은? 을전개했을때, 의계수와상수항의합을구하면? 을전개했을때, 의 계수는? 를전개했을때, 상수항을 구하여라. 37

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. 두자연수 와 를 로나누면나머지가각각

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

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

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

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

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

Microsoft PowerPoint - chap04-연산자.pptx

Microsoft PowerPoint - chap04-연산자.pptx int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); } 1 학습목표 수식의 개념과 연산자, 피연산자에 대해서 알아본다. C의 를 알아본다. 연산자의 우선 순위와 결합 방향에

More information

Infinity(∞) Strategy

Infinity(∞) Strategy 반복제어 표월성 passwd74@cherub.sungkyul.edu 개요 for() 문 break문과 continue문 while문 do-while문 for() 문 for() 문형식 for( 표현식1; 표현식2; 표현식3) 여러문장들 ; 표현식 1 : 초기화 (1 번만수행 ) 표현식 2 : 반복문수행조건 ( 없으면무한반복 ) 표현식 3 : 반복문수행횟수 for()

More information

Microsoft PowerPoint - 제3장-배열.pptx

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

More information

< 고급 C 프로그래밍및실습 > 11 장구조체실습문제 문제에대한안내 - 특별한언급이없으면문제의조건에맞지않는입력은입력되지않는다고가정하라. - 특별한언급이없으면, 각줄의맨앞과맨뒤에는공백을출력하지않는다. - 출력예시에서 는각줄의맨앞과맨뒤에출력되는공백을의미한다. - 입출력예시

< 고급 C 프로그래밍및실습 > 11 장구조체실습문제 문제에대한안내 - 특별한언급이없으면문제의조건에맞지않는입력은입력되지않는다고가정하라. - 특별한언급이없으면, 각줄의맨앞과맨뒤에는공백을출력하지않는다. - 출력예시에서 는각줄의맨앞과맨뒤에출력되는공백을의미한다. - 입출력예시 문제에대한안내 - 특별한언급이없으면문제의조건에맞지않는입력은입력되지않는다고가정하라. - 특별한언급이없으면, 각줄의맨앞과맨뒤에는공백을출력하지않는다. - 출력예시에서 는각줄의맨앞과맨뒤에출력되는공백을의미한다. - 입출력예시에서 이후는각입력과출력에대한설명이다. 11장2절 [ 문제 1 ] 3차원벡터를저장할구조체를선언후두개의 3차원벡터 (V 1, V 2 ) 를입력받으시오.

More information

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

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

More information

Microsoft PowerPoint Backtracking.pptx

Microsoft PowerPoint Backtracking.pptx 알고리즘 (Algorithm) g( 되추적 ) 2011년봄학기 강원대학교컴퓨터과학전공문양세 되추적 (backtracking)? 갈림길에표시를해두었더라면 간단히말해서되추적은갈림길에표시를해두는기법이다. Page 2 강의순서 되추적기술 n-queens Problem Monte Carlo Technique Graph Coloring Hamiltonian Circuits

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

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

슬라이드 1

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

More information

함께공주를구할용사고르기! 램왕자가칼솜씨가뛰어나다면힘세고용감한전사보다는치료마법을가진사제나, 많은정보를가지고있는동료가함께가는것이좋다. 램왕자가용에대한정보는가지고있으나싸움을잘하지못한다면, 강력한마법사또는파괴력이있는힘센전사와함께가는것이좋다. 램왕자는자신의능력을정확히파악한후자신

함께공주를구할용사고르기! 램왕자가칼솜씨가뛰어나다면힘세고용감한전사보다는치료마법을가진사제나, 많은정보를가지고있는동료가함께가는것이좋다. 램왕자가용에대한정보는가지고있으나싸움을잘하지못한다면, 강력한마법사또는파괴력이있는힘센전사와함께가는것이좋다. 램왕자는자신의능력을정확히파악한후자신 2 문제해결절차 학습목표 알고리즘의의미를이해하고, 문제해결절차를알고리즘으로표현할수있다. 알고리즘을의사코드나순서도로작성할수있다. 자료를정렬하고탐색하는다양한방법을설명할수있다. 공주님을구하라! 메인보드나라롬공주와이웃나라램왕자의결혼식에믿을수없는일이일어났다. 온국민의축복속에결혼식이진행되던중무시무시한용이나타나공주를납치해간것이다. 범인은왕국북쪽의디스크산에살고있는바이러스용이다.

More information

슬라이드 1

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

More information