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

Size: px
Start display at page:

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

Transcription

1 Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레드 블랙 트리를 구현하고자 한다 트리와 동등한 레드 블랙 트리 2-3트리와 동등한 레드 블랙 트리에서는, 교과서의 그림 13-24처럼, 2-노드와 3-노 드에 대응되는 레드브랙트리만 허용하고 4-노드는 허용하지 않는다. 따라서 다음그 림과 같이 4-노드에 해당되는 연결된 빨강링크를 갖는, 3가지 경우가 모두 허용되지 않는다. 그리고, 3-노드의 경우에는 빨강 링크가 어느방향으로 기울어지느냐에 따라 두 가지 경우가 존재하나, 본 문제에서는 빨강 링크가 왼쪽으로 기울어진 (lean left) 경우로만 한정한다 정리하면, 2-3트리와 등가인 레드 블랙 트리의 특징은 다음과 같다. 1

2 빨강 링크는 왼쪽으로 기울어진 좌측 경사의 경우만 허용한다 (lean left) 두 개이상의 연결된 빨강 링크는 허용하지 않는다. 검정 링크들은 완전 균형을 이룬다. 즉, 트리의 루트에서 모든 리프 노드에 이 르는 경로들의 검정 링크의 수는 모두 같다. 리프 노드에 이르는 검정 링크의 수를 black height라 한다 트리와 동등한 레드 블랙 트리: 삽입 및 삭제 알고리즘 2-3트리와 동등한 레드 블랙 트리상에서 삽입 및 삭제 알고리즘을 제시하고 각 경우에 대한 예제를 기술하시오 트리와 동등한 레드 블랙 트리: 삽입 및 삭제 알고리즘 구현 트리 노드를 위해 다음 자료구조를 가정하고, 위에서 설계한 삽입 및 삭제 알고리 즘을 구현하시오 (RBtree.cpp코드 작성). #define RED true #define BLACK false typedef struct treerecord int key; struct treerecord * LChild; struct treerecord * RChild; bool color; }node; typedef node* Nptr; 트리와 동등한 레드 블랙 트리: 삽입 및 삭제 알고리즘 테스트 위의 구현된 내용을 테스트하기 위해 2-3트리와 동일한 레드블랙트리인지를 검사 하는 테스트 함수 RBVerify를 작성하시오 (필요하면 위의 자료구조를 확장해도 좋다 (black height등)). bool RBVerify(Nptr node); (위의 세 가지 특징을 검증해야 함) 또한, 다음을 테스트하는 코드를 작성하고, 출력결과를 요약적으로 리포트하시 오 (RBtree test.cpp코드 작성). (화면상 출력결과를 모두 copy할 필요는 없이, 핵심만 리포트) 10,20,30,40,50,60,70,80,90,100을 삽입, 트리 출력, RBVerify로 검증, 및 black height출력 10, 20,..., 1000의 1000개의 데이터를 순서대로 삽입, RBVerify로 검 증, 및 black height출력. 랜덤하게 10,000개의 데이터 삽입 RBVerify로 검증 및 black height출력. 랜덤하게 100,000개의 데이터 삽입 RBVerify로 검증 및 black height출력. 2

3 랜덤하게 100,000개의 데이터 삽입 후 100,000 삭제, 삭제시마다 RBVerify 로 검증 및 black height출력. 그외 다른 테스트 수행 테스트시 트리를 출력하는 경우에는 다음의 코드를 사용하라. void RBPrettyPrint(const std::string& prefix, Nptr node, bool isleft) if( node!= NULL ) cout << prefix; if(node->color == RED) cout << (isleft? " " : " " ); else cout << (isleft? " " : " " ); cout << node->key ; if(node->color == RED) cout << "*"; cout << endl; RBPrettyPrint( prefix + (isleft? " " : " "), node->lchild, true); RBPrettyPrint( prefix + (isleft? " " : " "), node->rchild, false); } } //RBPrettyPrint("", root, false); when calling it with the root node. 예를 들어, 다음은 10,20,30,40,50,60,70,80,90,100을 삽입후 위 코드를 이용한 출력 결과이다 * * 트리와 동등한 레드 블랙 트리 2-3-4트리와 동등한 레드 블랙 트리에 대한 내용은 교과서 13장 5절을 참조하라 트리와 동등한 레드 블랙 트리: 삽입 및 삭제 알고리즘 (2-3트리의 문항에서처럼) 2-3-4트리와 동등한 레드 블랙 트리상에서 삽입 및 삭제 알고리즘을 제시하고 각 경우에 대한 예제를 기술하시오. 3

4 트리와 동등한 레드 블랙 트리: 삽입 및 삭제 알고리즘 구현 (2-3트리의 문항에서처럼) 앞 문항의 treerecord를 사용하여 위에서 설계한 삽입 및 삭제 알고리즘을 구현하시오 (RBtree 234.cpp코드 작성) 트리와 동등한 레드 블랙 트리: 삽입 및 삭제 알고리즘 테스트 2-3트리의 문항에서처럼, 2-3-4트리와 동일한 레드블랙트리인지를 검사하는 테스 트 함수 RBVerify를 작성하시오). 또한, 2-3트리의 문항에서 주어진 각 경우에 대해 테스트하는 코드를 작성하고, 출력결과를 요약적으로 리포트하시오 (RBtree 234 test.cpp코드 작성). (마찬가 지로 화면상 출력결과를 모두 copy할 필요는 없이, 핵심만 리포트) 2 트라이 (Trie) 본 절에서는 영문 소문자 알파벳을 radix단위로 하는 트라이(trie)를 구현하는 것이 목표이다. 다음은 by, bye, byte, data, day, done, do, did를 순서대로 삽입한 트라이의 구조이다. (값은 순서대로 0, 1,, 7까지 부여되었다고 가정) 본 절에서는 트라이 각 노드 표현을 위해 다음 자료구조를 사용한다. #define NUM_ALPHABET 26 typedef struct trierecord int val; struct trierecord **nodes; } node; typedef node* Nptr; Nptr CreateTrieNode() Nptr p = new node; 4

5 p->nodes = new node*[num_alphabet]; for(int i=0;i<num_alphabet;i++) p->nodes[i] = NULL; return p; } 2.1 트라이 클래스 구현 주어진 트라이 노드에 대한 자료구조에 기반하여, 영문 소문자 알파벳으로 구성된 문자열에 대해 트라이 클래스 class의 Insert, Update, Delete, Save, Open을 완성하시오. (Trie.h, Trie.cpp). class Trie public: int size; Nptr *root; public: void Create(); int Insert(const char *key, int val); Nptr Search(const char *key); void Delete(const char *key); void Save(const char *filename); void Open(const char *filename); ; } 각 함수에 대한 정의는 다음과 같다. Create: 트라이를 새롭게 생성한다. Insert: 주어진 key에 대해 값이 val인 노드를 트라이에 삽입한다. 만약 이미 동일한 key가 존재하면, val로 값을 변경한다. Search: 주어진 key에 대한 트라이 노드를 리턴한다. 만약 key가 존재하지 않으면 NULL을 리턴한다. Delete: 주어진 key에 대한 트라이 노드를 삭제한다. Save: 트라이를 binary또는 text파일로 저장한다. 차후 빠르게 loading할수 있도록 파일 포맷을 잘 설계해야 한다. Open: 저장한 트라이 파일을 읽어들여 메모리상으로 loading한다 트라이를 이용한 Word count계산 및 사용자 테스트 트라이를 이용하여 주어진 텍스트 파일에 있는 각 단어의 word count를 계산하고, 계산된 결과를 해쉬 파일로 저장하는 Trie word count.cpp를 작성하시오. (word count를 1씩 증가시키기 위해 트라이 클래스상의 새로운 함수 Update를 추가해도 된다. 그렇지 않으면 Search후에 Insert하는 방식으로 word count를 계산하라.) 구동 테스트를 위해 다음 두 가지 입력 파일에 대해 테스트를 수행하고, 트 라이의 내용을 각각 The-Road-Not-Taken.trie, Dickens Oliver 1839.trie에 저장하시오.. 5

6 Oliver 1839.tokens.txt 추가로, 저장된 트라이 파일 The-Road-Not-Taken.trie, Dickens Oliver trie를 로딩하여 트라이를 메모리에 올린후, 사용자로부터 단어를 입력단어 Search 를 수행하여 해당 단어가 있으면 count를 그러지 않으면 Not found를 출력하는 코드 Trie word count test.cpp를 작성하시오 트라이와 해시 및 이진탐색트리 효율 비교 과제2에서 구현된 해시와 이진탐색 효율 비교를 위해, Dickens Oliver tokens.txt상에서 N 개의 랜덤 key에 대해 Search를 호출할 때 트라이와 해시 그리고 이진탐색트리간의 소요시간을 비교하시오 (N = 이상). (본 절에서 는 트라이의 소요시간파악이 핵심 주제이다) 3 네비게이터 본 절에서는 임의의 랜덤 도로 맵에서 시작위치에서 끝 위치까지 최단 경로를 탐 색하는 네비게이터 (navigator)를 구현하는 것을 목표로 한다. 네비게이터는 의 맵 프레임과 1) 랜덤 로드 생성, 2) 최단 경로 탐색, 3) MST 탐색 의 세 개의 버튼으로 구성된다. 다음은 구현하고자 하는 네이게이터 GUI의 개략도이다. 네이게이터 구동을 요약하면 다음과 같다. 먼저 맵 프레임상에서 N 개의 도로(road)를 랜덤하게 생성한 후에 도로들의 교차점을 계산한 후, 해당 교차점을 정점으로 하고, 인접된 두 교차점마다 간선을 형성하고, 두 교차점간의 도로상 직선 거리를 간선의 가중치로 하는 교차점 그래프 (가중치 그래프)를 만든다. 다음, 네비게이션 모드에서는, 사용자의 시작지점과 도착지점을 마우스로 입력 받은 후, 시작지점에서 가장 가까운 교차점을 시작교차점으로 도착지점에서 가장 가까운 교차점을 끝교차점 으로 하여 시작교차점에서 끝교차점까지의 최단경로를 6

7 다익스트라(Dijkstra)알고리즘을 통해 계산하고, 탐색된 최단 경로를 맵 프레임상 에서 출력한다. 사용자가 지정한 시작/도착지점별로 가까운 교차점까지 이동하는 경로도 출력에 포함되어야 한다. 다음은 최단 경로 출력 예를 보여준다. 이외에 교차점 그래프상에서 모든 교차점을 연결하는 최소신장트리를 구하여 화면에 출력한다. 네비게이터 GUI관련 요구사항을 정리하면 다음과 같다. 맵 프레임: 크기의 프레임으로 초기에 랜덤으로 생성된 도로 (Road)를 보여준다. 각 도로는 프레임의 경계에서 시작하고 끝나야 하며, 모든 도로의 교차점은 보다 큰 원으로 표시하여 구분되어야 한다. Generate Random Roads 버튼: 맵을 다시 새롭게 생성하는 버튼이다. 이전 맵은 지우고, 랜덤하게 N 개의 로드를 생성하여 화면에 출력한다. Find Shortest Path 버튼: 사용자 마우스로부터 시작지점와 도착지점를 입력받은 후에 해당 버튼을 클릭하면 다익스트라알고리즘을 통해 최단 경 로를 탐색한다. 탐색결과의 최단 경로상의 도로들은 별도의 색상으로 다른 도로들과는 구분해서 보여주어야 한다. 만약 사용자로부터 아직 시작위치와 끝 위치를 입력받지 못한 경우에는 시작지점와 끝지점의 위치를 마우스로 클릭하시오 라는 대화상자를 제시한다. 최단경로의 최종 거리도 화면상 출 력하라 (시작지점 시작교차점 끝교차점 끝지점에 이르는 거리) Get MST 버튼: 프림알고리즘 (Prim s algorithm) 또는 크루스칼 알고리 즘 (Kruskal s algoirthm)을 적용하여 모든 교차점을 연결하는 Minimum Spanning Tree(MST)를 찾아, 화면에 출력한다. 마찬가지로, MST상의 로드 들은 별도의 색상으로 다른 도로들과 구분해서 보여주어야 한다. 최소신장 트리의 Cost도 화면상 출력하라. 마우스 입력: 시작/끝 지점 설정: 사용자의 마우스 왼쪽 버튼 클릭시에 위치 를 시작지점으로, 오른쪽 버튼 클릭시 위치를 도착지점으로 한다. 7

8 3.1 네비게이터 구현 (java로 작성) 네이게이터 GUI 요구사항이 모두 충족되도록 해당 코드를 java로 구현한다 (Navigator. java포함 각종 클래스 구현 파일). 구현할 내용의 핵심들은 다음과 같다. 랜덤 도로 생성 도로간 교차점 계산 교차점 그래프 생성 최단 경로 탐색 알고리즘 최소 신장 트리 계산 알고리즘 화면에 출력하는 GUI 코드 본 과제는 알고리즘 구현외에도, GUI환경에서 테스트가 될 수 있도록 GUI 입출력부분도 함께 정교하게 구현되어야함을 유의해야 한다. 3.2 네비게이터 테스트 콘솔모드 테스트와 GUI모드 테스트 모두 지원되도록 하고, 랜덤 도로의 갯수 N 을 7, 20, 50, 100을 포함하여 4개이상 시작지점와 끝지점을 달리하면서 다양하게 테스트하라. 보고서에는 N = 50인 경우의 콘솔모드 및 GUI출력 결과를 1) 랜덤도로생성, 2) 최단경로탐색결과, 3) MST계산결과 로 정리해서 제시하라. 콘솔모드의 경우 테스트 요구사항은 다음과 같다. 교차점 그래프 정보 출력: 콘솔모드의 경우에는 랜덤 로드 생성후, 다음과 같이 교차점 그래프 정보가 출력되도록 하라. 교차점 갯수, 간선 수 각 교차점 정보: 교차점의 위치 (x, y좌표)와 인덱스, 해당 교차점과 연 결된 교차점 인덱스와 거리의 리스트) 랜덤 입력 가정: 시작지점과 끝지점은 사용자 입력을 받는대신 랜덤으로 입 력되도록 하고, 이에 최단경로탐색을 수행한다. 출력 방법: 최단경로는 경로상의 교차점 인덱스들의 리스트를, MST는 간 선 및 간선의 가중치를 출력하여 표현하라. (간선은 (u, v)로 교차점 인덱스 쌍으로 출력) GUI모드의 경우에 1) 랜덤도로생성, 2) 최단경로탐색결과, 3) MST계산결 과 각 단계별로 출력되는 GUI화면을 캡처하여 제시하라. 콘솔모드는 대량의 랜덤 입력 테스트가 목적이며, GUI화면상의 인터페이스가 완벽하게 구동되는것이 본 절에서의 메인테스트임을 유의하라. 8

9 4 제출 내용 및 평가 방식 코드는 c++ (특별한 요구사항이 있을 경우 java)로 작성하도록 하고, c++프로 그램의 경우 구동os환경은 ubuntu LTS 이상을 원칙으로 한다. 본 과제 결과물로 필수적으로 제출해야 내용들은 다음과 같다. java프로그램은 windows 10또는 ubuntu LTS에서 동작되도록 하면 되며, 보고서에 구동 환경을 명확히 명시 (java버전 등도 함께 기술 )하라. 코드 전체 테스트 결과: 각 내용별 테스트 코드 및 해당 로그 파일 결과보고서: 구현 방법 및 실행 결과를 요약한 보고서 본 과제의 평가항목 및 배점은 다음과 같다. 각 세부내용의 구현 정확성 및 완결성 (80점) 코드의 Readability 및 쳬계성 (10점) 결과 보고서의 구체성 및 완결성 (10점) 9

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

(실제 구현은 더욱 단순하다). 다음은 배열의 길이 n과 간격비 K의 서로 다른 셋팅에 대한 셸 정렬의 진행 순서에 대한 예이다. 1. n = 150, K = 3인 경우, Eq. (2)에 따라 m = 5이다. 즉, 셀 정렬은 총 5 단계를 거치며 (m = 5), 121

(실제 구현은 더욱 단순하다). 다음은 배열의 길이 n과 간격비 K의 서로 다른 셋팅에 대한 셸 정렬의 진행 순서에 대한 예이다. 1. n = 150, K = 3인 경우, Eq. (2)에 따라 m = 5이다. 즉, 셀 정렬은 총 5 단계를 거치며 (m = 5), 121 Data structure: Assignment 2 Seung-Hoon Na November 23, 2018 1 Assignment 2 1.1 셸 정렬 (shell sort) 본 절에서는 셸 정렬을 구현하는 것을 목표로 한다. 셸 정렬 (shell sort)는 삽입 정렬(insertion sort)을 개선한 것으로, 한칸씩 원소 교환을 하는 것이 아니라, 여러

More information

Artificial Intelligence: Assignment 6 Seung-Hoon Na December 15, Sarsa와 Q-learning Windy Gridworld Windy Gridworld의 원문은 다음 Sutton 교재의 연습문제

Artificial Intelligence: Assignment 6 Seung-Hoon Na December 15, Sarsa와 Q-learning Windy Gridworld Windy Gridworld의 원문은 다음 Sutton 교재의 연습문제 Artificial Intelligence: Assignment 6 Seung-Hoon Na December 15, 2018 1 1.1 Sarsa와 Q-learning Windy Gridworld Windy Gridworld의 원문은 다음 Sutton 교재의 연습문제 6.5에서 찾아볼 수 있다. http://incompleteideas.net/book/bookdraft2017nov5.pdf

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

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

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

More information

(Microsoft Word - \301\337\260\243\260\355\273\347.docx)

(Microsoft Word - \301\337\260\243\260\355\273\347.docx) 내장형시스템공학 (NH466) 중간고사 학번 : 이름 : 문제 배점 점수 1 20 2 20 3 20 4 20 5 10 6 10 7 15 8 20 9 15 합계 150 1. (20 점 ) 다음용어에대해서설명하시오. (1) 정보은닉 (Information Hiding) (2) 캡슐화 (Encapsulation) (3) 오버로딩 (Overloading) (4) 생성자

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

Chap 6: Graphs

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

More information

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

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

More information

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

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

More information

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

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070> 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include "QuickSort.h" 7 using namespace std; 8 9 10 Node* Queue[100]; // 추가입력된데이터를저장하기위한 Queue

More information

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

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

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

C프로-3장c03逞풚

C프로-3장c03逞풚 C h a p t e r 03 C++ 3 1 9 4 3 break continue 2 110 if if else if else switch 1 if if if 3 1 1 if 2 2 3 if if 1 2 111 01 #include 02 using namespace std; 03 void main( ) 04 { 05 int x; 06 07

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

06장.리스트

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

More information

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

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

More information

Microsoft PowerPoint - chap13-입출력라이브러리.pptx

Microsoft PowerPoint - chap13-입출력라이브러리.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

Chap 6: Graphs

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

More information

Artificial Intelligence: Assignment 1 Seung-Hoon Na October 16, A* Algorithm 본 과제에서는 M N Grid world에서 장애물이 랜덤(random)하게 배치되고, 시작 지점에서 장애물을 피해 목

Artificial Intelligence: Assignment 1 Seung-Hoon Na October 16, A* Algorithm 본 과제에서는 M N Grid world에서 장애물이 랜덤(random)하게 배치되고, 시작 지점에서 장애물을 피해 목 Artificial Intelligence: Assignment 1 Seung-Hoon Na October 16, 2018 1 A* Algorithm 본 과제에서는 M N Grid world에서 장애물이 랜덤(random)하게 배치되고, 시작 지점에서 장애물을 피해 목표지점까지 도달하는 최단 경로를 찾는 A* 알고리즘을 구현하고 이를 GUI환경에서 시물레이션

More information

Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ

Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ 알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2016년 12월15일 ( 목 ) 오전 9시40분 ~) 담당교수 : 서강대학교컴퓨터공학과임인성 < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고, 반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. function MakeSet(x) { x.parent

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

03_queue

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

More information

7장

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

More information

<4D F736F F F696E74202D20C1A63034B0AD202D20C7C1B7B9C0D3B8AEBDBAB3CABFCD20B9ABB9F6C6DBC0D4B7C2>

<4D F736F F F696E74202D20C1A63034B0AD202D20C7C1B7B9C0D3B8AEBDBAB3CABFCD20B9ABB9F6C6DBC0D4B7C2> 게임엔진 제 4 강프레임리스너와 OIS 입력시스템 이대현교수 한국산업기술대학교게임공학과 학습내용 프레임리스너의개념 프레임리스너를이용한엔터티의이동 OIS 입력시스템을이용한키보드입력의처리 게임루프 Initialization Game Logic Drawing N Exit? Y Finish 실제게임루프 오우거엔진의메인렌더링루프 Root::startRendering()

More information

쉽게 풀어쓴 C 프로그래밍

쉽게 풀어쓴 C 프로그래밍 제 5 장생성자와접근제어 1. 객체지향기법을이해한다. 2. 클래스를작성할수있다. 3. 클래스에서객체를생성할수있다. 4. 생성자를이용하여객체를초기화할수 있다. 5. 접근자와설정자를사용할수있다. 이번장에서만들어볼프로그램 생성자 생성자 (constructor) 는초기화를담당하는함수 생성자가필요한이유 #include using namespace

More information

11장 포인터

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

More information

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

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

More information

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

쉽게 풀어쓴 C 프로그래밍

쉽게 풀어쓴 C 프로그래밍 제 13 장파일처리 1. 스트림의개념을이해한다. 2. 객체지향적인방법을사용하여파일입출력을할수있다. 3. 텍스트파일과이진파일의차이점을이해한다. 4. 순차파일과임의접근파일의차이점을이해한다. 이번장에서만들어볼프로그램 스트림 (stream) 스트림 (stream) 은 순서가있는데이터의연속적인흐름 이다. 스트림은입출력을물의흐름처럼간주하는것이다. 입출력관련클래스들 파일쓰기

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 실습 1 배효철 th1g@nate.com 1 목차 조건문 반복문 System.out 구구단 모양만들기 Up & Down 2 조건문 조건문의종류 If, switch If 문 조건식결과따라중괄호 { 블록을실행할지여부결정할때사용 조건식 true 또는 false값을산출할수있는연산식 boolean 변수 조건식이 true이면블록실행하고 false 이면블록실행하지않음 3

More information

K&R2 Reference Manual 번역본

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

More information

03장.스택.key

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

More information

Microsoft PowerPoint - Java7.pptx

Microsoft PowerPoint - Java7.pptx HPC & OT Lab. 1 HPC & OT Lab. 2 실습 7 주차 Jin-Ho, Jang M.S. Hanyang Univ. HPC&OT Lab. jinhoyo@nate.com HPC & OT Lab. 3 Component Structure 객체 (object) 생성개념을이해한다. 외부클래스에대한접근방법을이해한다. 접근제어자 (public & private)

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>

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

More information

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

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

More information

Microsoft PowerPoint - 07-Data Manipulation.pptx

Microsoft PowerPoint - 07-Data Manipulation.pptx Digital 3D Anthropometry 7. Data Analysis Sungmin Kim SEOUL NATIONAL UNIVERSITY Body 기본정보표시 Introduction 스케일조절하기 단면형상추출 단면정보관리 3D 단면형상표시 2 기본정보표시및스케일조절 UI 및핸들러구성 void fastcall TMainForm::BeginNewProject1Click(TObject

More information

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms 2015-1 12. 그래프와관련알고리즘 2015 년 5 월 28 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 그래프 (Graph) 그래프의응용예 Outline 미로찾기 인터넷라우터에서의패킷 forwarding

More information

C++ Programming

C++ Programming C++ Programming 예외처리 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 예외처리 2 예외처리 예외처리 C++ 의예외처리 예외클래스와객체 3 예외처리 예외를처리하지않는프로그램 int main() int a, b; cout > a >> b; cout

More information

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

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 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

제 1 장 기본 개념

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

More information

제8장 자바 GUI 프로그래밍 II

제8장 자바 GUI 프로그래밍 II 제8장 MVC Model 8.1 MVC 모델 (1/7) MVC (Model, View, Controller) 모델 스윙은 MVC 모델에기초를두고있다. MVC란 Xerox의연구소에서 Smalltalk 언어를바탕으로사용자인터페이스를개발하기위한방법 MVC는 3개의구성요소로구성 Model : 응용프로그램의자료를표현하기위한모델 View : 자료를시각적으로 (GUI 방식으로

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

C++ Programming

C++ Programming C++ Programming 연산자다중정의 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 연산자다중정의 C++ 스타일의문자열 2 연산자다중정의 연산자다중정의 단항연산자다중정의 이항연산자다중정의 cin, cout 그리고 endl C++ 스타일의문자열 3 연산자다중정의 연산자다중정의 (Operator

More information

PowerPoint Presentation

PowerPoint Presentation Package Class 3 Heeseung Jo 목차 section 1 패키지개요와패키지의사용 section 2 java.lang 패키지의개요 section 3 Object 클래스 section 4 포장 (Wrapper) 클래스 section 5 문자열의개요 section 6 String 클래스 section 7 StringBuffer 클래스 section

More information

PowerPoint 프레젠테이션

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

More information

untitled

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

More information

BACK TO THE BASIC C++ 버그 헌팅: 버그를 예방하는 11가지 코딩 습관

BACK TO THE BASIC C++ 버그 헌팅: 버그를 예방하는 11가지 코딩 습관 Hanbit ebook Realtime 30 C++ 버그 헌팅 버그를 예방하는 11가지 코딩 습관 Safe C++ 블라디미르 쿠스퀴니르 지음 / 정원천 옮김 이 도서는 O REILLY의 Safe C++의 번역서입니다. BACK TO THE BASIC C++ 버그 헌팅 버그를 예방하는 11가지 코딩 습관 BACK TO THE BASIC C++ 버그 헌팅 버그를

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

BMP 파일 처리

BMP 파일 처리 BMP 파일처리 김성영교수 금오공과대학교 컴퓨터공학과 학습내용 영상반전프로그램제작 2 Inverting images out = 255 - in 3 /* 이프로그램은 8bit gray-scale 영상을입력으로사용하여반전한후동일포맷의영상으로저장한다. */ #include #include #define WIDTHBYTES(bytes)

More information

Frama-C/JESSIS 사용법 소개

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

More information

Run 봄 연습 Mar 18 Mar 24, 2018, Week 3 문제 1. 초코바 입력 파일: 출력 파일: 시간 제한: 메모리 제한: standard input standard output 1 seconds 128 megabytes H W 격자 모양의 초콜릿이 있다.

Run 봄 연습 Mar 18 Mar 24, 2018, Week 3 문제 1. 초코바 입력 파일: 출력 파일: 시간 제한: 메모리 제한: standard input standard output 1 seconds 128 megabytes H W 격자 모양의 초콜릿이 있다. 문제. 초코바 H W 격자 모양의 초콜릿이 있다. 이 초콜릿을 개의 직사각형으로 격자를 따라서 잘라서, 최대 넓이의 초콜릿과 최소 넓이의 초콜릿의 넓이 차이를 최소화 하고 싶다. 이 차이의 최솟값을 구하여라. 첫째 줄에 H와 W 가 공백으로 구분되어 주어진다. 초콜릿을 개의 직사각형으로 자를 때, 최대 넓이의 초콜릿과 최소 넓이의 초콜릿의 넓이 차이의 최솟값을

More information

untitled

untitled 1. void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); 2) => A / B * C * D + E () A / B * C * D + E void preorder(tree_ptr ptr) { if(ptr)

More information

슬라이드 1

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

More information

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

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

More information

11강-힙정렬.ppt

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

More information

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

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

More information

<4D F736F F F696E74202D B3E22032C7D0B1E220C0A9B5B5BFECB0D4C0D3C7C1B7CEB1D7B7A1B9D620C1A638B0AD202D20C7C1B7B9C0D320BCD3B5B5C0C720C1B6C0FD>

<4D F736F F F696E74202D B3E22032C7D0B1E220C0A9B5B5BFECB0D4C0D3C7C1B7CEB1D7B7A1B9D620C1A638B0AD202D20C7C1B7B9C0D320BCD3B5B5C0C720C1B6C0FD> 2006 년 2 학기윈도우게임프로그래밍 제 8 강프레임속도의조절 이대현 한국산업기술대학교 오늘의학습내용 프레임속도의조절 30fps 맞추기 스프라이트프레임속도의조절 프레임속도 (Frame Rate) 프레임속도란? 얼마나빨리프레임 ( 일반적으로하나의완성된화면 ) 을만들어낼수있는지를나타내는척도 일반적으로초당프레임출력횟수를많이사용한다. FPS(Frame Per Sec)

More information

Windows 8에서 BioStar 1 설치하기

Windows 8에서 BioStar 1 설치하기 / 콘텐츠 테이블... PC에 BioStar 1 설치 방법... Microsoft SQL Server 2012 Express 설치하기... Running SQL 2012 Express Studio... DBSetup.exe 설정하기... BioStar 서버와 클라이언트 시작하기... 1 1 2 2 6 7 1/11 BioStar 1, Windows 8 BioStar

More information

Microsoft PowerPoint - C++ 5 .pptx

Microsoft PowerPoint - C++ 5 .pptx C++ 언어프로그래밍 한밭대학교전자. 제어공학과이승호교수 연산자중복 (operator overloading) 이란? 2 1. 연산자중복이란? 1) 기존에미리정의되어있는연산자 (+, -, /, * 등 ) 들을프로그래머의의도에맞도록새롭게정의하여사용할수있도록지원하는기능 2) 연산자를특정한기능을수행하도록재정의하여사용하면여러가지이점을가질수있음 3) 하나의기능이프로그래머의의도에따라바뀌어동작하는다형성

More information

프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어

프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어 개나리 연구소 C 언어 노트 (tyback.egloos.com) 프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어먹고 하더라구요. 그래서,

More information

14장.탐색

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

More information

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

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

More information

1. auto_ptr 다음프로그램의문제점은무엇인가? void func(void) int *p = new int; cout << " 양수입력 : "; cin >> *p; if (*p <= 0) cout << " 양수를입력해야합니다 " << endl; return; 동적할

1. auto_ptr 다음프로그램의문제점은무엇인가? void func(void) int *p = new int; cout <<  양수입력 : ; cin >> *p; if (*p <= 0) cout <<  양수를입력해야합니다  << endl; return; 동적할 15 장기타주제들 auto_ptr 변환함수 cast 연산자에의한명시적형변환실행시간타입정보알아내기 (RTTI) C++ 프로그래밍입문 1. auto_ptr 다음프로그램의문제점은무엇인가? void func(void) int *p = new int; cout > *p; if (*p

More information

PowerPoint Presentation

PowerPoint Presentation Package Class 1 Heeseung Jo 목차 section 1 패키지개요와패키지의사용 section 2 java.lang 패키지의개요 section 3 Object 클래스 section 4 포장 (Wrapper) 클래스 section 5 문자열의개요 section 6 String 클래스 section 7 StringBuffer 클래스 section

More information

슬라이드 1

슬라이드 1 2007 년 2 학기윈도우게임프로그래밍 제 7 강프레임속도의조절 이대현 핚국산업기술대학교 학습내용 프레임속도의조절 30fps 맞추기 스프라이트프레임속도의조절 프레임속도 (Frame Rate) 프레임속도란? 얼마나빨리프레임 ( 일반적으로하나의완성된화면 ) 을만들어낼수있는지를나타내는척도 일반적으로초당프레임출력횟수를많이사용핚다. FPS(Frame Per Sec)

More information

Microsoft PowerPoint - Chap5 [호환 모드]

Microsoft PowerPoint - Chap5 [호환 모드] 데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호 Index hapter 01: asic oncepts hapter 02: rrays and Structures hapter 03: Stacks and Queues hapter 04: Lists hapter 05: Trees hapter 06: Graphs

More information

08장.트리

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

More information

1. 표준입출력 C++ : C의모든라이브러리를포함 printf, scanf 함수사용가능예 : int, double, 문자열값을입력받고출력하기 #include <cstdio> int ivar; double dvar; char str[20]; printf("int, dou

1. 표준입출력 C++ : C의모든라이브러리를포함 printf, scanf 함수사용가능예 : int, double, 문자열값을입력받고출력하기 #include <cstdio> int ivar; double dvar; char str[20]; printf(int, dou 2 장더나은 C 로서의 C++ (1) 표준입출력네임스페이스 ( 고전 C++ 와표준 C++) 함수오버로딩디폴트매개변수 new와 delete bool 자료형 C++ is not C C++ 프로그래밍입문 1. 표준입출력 C++ : C의모든라이브러리를포함 printf, scanf 함수사용가능예 : int, double, 문자열값을입력받고출력하기 #include

More information

API 매뉴얼

API 매뉴얼 PCI-DIO12 API Programming (Rev 1.0) Windows, Windows2000, Windows NT and Windows XP are trademarks of Microsoft. We acknowledge that the trademarks or service names of all other organizations mentioned

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

슬라이드 1

슬라이드 1 핚국산업기술대학교 제 14 강 GUI (III) 이대현교수 학습안내 학습목표 CEGUI 라이브러리를이용하여, 게임메뉴 UI 를구현해본다. 학습내용 CEGUI 레이아웃의로딩및렌더링. OIS 와 CEGUI 의연결. CEGUI 위젯과이벤트의연동. UI 구현 : 하드코딩방식 C++ 코드를이용하여, 코드내에서직접위젯들을생성및설정 CEGUI::PushButton* resumebutton

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

More information

02장.배열과 클래스

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 @ Lesson 3 if, if else, if else if, switch case for, while, do while break, continue : System.in, args, JOptionPane for (,, ) @ vs. logic data method variable Data Data Flow (Type), ( ) @ Member field

More information

윈도우시스템프로그래밍

윈도우시스템프로그래밍 데이터베이스및설계 MySQL 을위한 MFC 를사용한 ODBC 프로그래밍 2012.05.10. 오병우 컴퓨터공학과금오공과대학교 http://www.apmsetup.com 또는 http://www.mysql.com APM Setup 설치발표자료참조 Department of Computer Engineering 2 DB 에속한테이블보기 show tables; 에러발생

More information

The C++ Programming Language 5 장포인터, 배열, 구조체 5.9 연습문제 다음의선언문을순서대로작성해보자. 문자에대한포인터, 10개정수의배열, 10개정수의배열의참조자, 문자열의배열에대한포인터, 문자에대한포인터에대한포인터, 상수정수, 상수

The C++ Programming Language 5 장포인터, 배열, 구조체 5.9 연습문제 다음의선언문을순서대로작성해보자. 문자에대한포인터, 10개정수의배열, 10개정수의배열의참조자, 문자열의배열에대한포인터, 문자에대한포인터에대한포인터, 상수정수, 상수 The C++ Programming Language 5 장포인터, 배열, 구조체 5.9 연습문제 5.9.1 다음의선언문을순서대로작성해보자. 문자에대한포인터, 10개정수의배열, 10개정수의배열의참조자, 문자열의배열에대한포인터, 문자에대한포인터에대한포인터, 상수정수, 상수정수에대한포인터, 정수에대한상수포인터. 그리고각각의객체를초기화하자. Ex 문자에대한포인터 char

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

슬라이드 1

슬라이드 1 정적메모리할당 (Static memory allocation) 일반적으로프로그램의실행에필요한메모리 ( 변수, 배열, 객체등 ) 는컴파일과정에서결정되고, 실행파일이메모리에로드될때할당되며, 종료후에반환됨 동적메모리할당 (Dynamic memory allocation) 프로그램의실행중에필요한메모리를할당받아사용하고, 사용이끝나면반환함 - 메모리를프로그램이직접관리해야함

More information

JUNIT 실습및발표

JUNIT 실습및발표 JUNIT 실습및발표 JUNIT 접속 www.junit.org DownLoad JUnit JavaDoc API Document 를참조 JUNIT 4.8.1 다운로드 설치파일 (jar 파일 ) 을다운로드 CLASSPATH 를설정 환경변수에서설정 실행할클래스에서 import JUnit 설치하기 테스트실행주석 @Test Test 를실행할 method 앞에붙임 expected

More information

슬라이드 1

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

More information

PowerPoint Template

PowerPoint Template 16-1. 보조자료템플릿 (Template) 함수템플릿 클래스템플릿 Jong Hyuk Park 함수템플릿 Jong Hyuk Park 함수템플릿소개 함수템플릿 한번의함수정의로서로다른자료형에대해적용하는함수 예 int abs(int n) return n < 0? -n : n; double abs(double n) 함수 return n < 0? -n : n; //

More information

8 장데이터베이스 8.1 기본개념 - 데이터베이스 : 데이터를조직적으로구조화한집합 (cf. 엑셀파일 ) - 테이블 : 데이터의기록형식 (cf. 엑셀시트의첫줄 ) - 필드 : 같은종류의데이터 (cf. 엑셀시트의각칸 ) - 레코드 : 데이터내용 (cf. 엑셀시트의한줄 )

8 장데이터베이스 8.1 기본개념 - 데이터베이스 : 데이터를조직적으로구조화한집합 (cf. 엑셀파일 ) - 테이블 : 데이터의기록형식 (cf. 엑셀시트의첫줄 ) - 필드 : 같은종류의데이터 (cf. 엑셀시트의각칸 ) - 레코드 : 데이터내용 (cf. 엑셀시트의한줄 ) 8 장데이터베이스 8.1 기본개념 - 데이터베이스 : 데이터를조직적으로구조화한집합 (cf. 엑셀파일 ) - 테이블 : 데이터의기록형식 (cf. 엑셀시트의첫줄 ) - 필드 : 같은종류의데이터 (cf. 엑셀시트의각칸 ) - 레코드 : 데이터내용 (cf. 엑셀시트의한줄 ) - DDL(Data Definition Language) : show, create, drop

More information

Artificial Intelligence: Assignment 2 Seung-Hoon Na October 20, Map coloring 본 과제에서는 M N Grid world 지도상에서 각 region이 rectangle또는 polyomino유형으로 주

Artificial Intelligence: Assignment 2 Seung-Hoon Na October 20, Map coloring 본 과제에서는 M N Grid world 지도상에서 각 region이 rectangle또는 polyomino유형으로 주 Artificial Intelligence Assignment 2 Seung-Hoon Na October 20, 2018 1 Map coloring 본 과제에서는 M N Grid world 지도상에서 각 region이 rectangle또는 polyomino유형으로 주어질때, K개의 색상(color)만으로 서로 맞닿은 region들을 다른 색으로 칠하는 K-coloring

More information

(Microsoft PowerPoint - 07\300\345.ppt [\310\243\310\257 \270\360\265\345])

(Microsoft PowerPoint - 07\300\345.ppt [\310\243\310\257 \270\360\265\345]) 클래스의응용 클래스를자유자재로사용하자. 이장에서다룰내용 1 객체의치환 2 함수와클래스의상관관계 01_ 객체의치환 객체도변수와마찬가지로치환이가능하다. 기본예제 [7-1] 객체도일반변수와마찬가지로대입이가능하다. 기본예제 [7-2] 객체의치환시에는조심해야할점이있다. 복사생성자의필요성에대하여알아보자. [ 기본예제 7-1] 클래스의치환 01 #include

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 언어 강의노트

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

More information

Chapter 4. LISTS

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

More information

1. 객체의생성과대입 int 형변수 : 선언과동시에초기화하는방법 (C++) int a = 3; int a(3); // 기본타입역시클래스와같이처리가능 객체의생성 ( 복습 ) class CPoint private : int x, y; public : CPoint(int a

1. 객체의생성과대입 int 형변수 : 선언과동시에초기화하는방법 (C++) int a = 3; int a(3); // 기본타입역시클래스와같이처리가능 객체의생성 ( 복습 ) class CPoint private : int x, y; public : CPoint(int a 6 장복사생성자 객체의생성과대입객체의값에의한전달복사생성자디폴트복사생성자복사생성자의재정의객체의값에의한반환임시객체 C++ 프로그래밍입문 1. 객체의생성과대입 int 형변수 : 선언과동시에초기화하는방법 (C++) int a = 3; int a(3); // 기본타입역시클래스와같이처리가능 객체의생성 ( 복습 ) class CPoint private : int x, y;

More information

아이콘의 정의 본 사용자 설명서에서는 다음 아이콘을 사용합니다. 참고 참고는 발생할 수 있는 상황에 대처하는 방법을 알려 주거나 다른 기능과 함께 작동하는 방법에 대한 요령을 제공합니다. 상표 Brother 로고는 Brother Industries, Ltd.의 등록 상

아이콘의 정의 본 사용자 설명서에서는 다음 아이콘을 사용합니다. 참고 참고는 발생할 수 있는 상황에 대처하는 방법을 알려 주거나 다른 기능과 함께 작동하는 방법에 대한 요령을 제공합니다. 상표 Brother 로고는 Brother Industries, Ltd.의 등록 상 Android 용 Brother Image Viewer 설명서 버전 0 KOR 아이콘의 정의 본 사용자 설명서에서는 다음 아이콘을 사용합니다. 참고 참고는 발생할 수 있는 상황에 대처하는 방법을 알려 주거나 다른 기능과 함께 작동하는 방법에 대한 요령을 제공합니다. 상표 Brother 로고는 Brother Industries, Ltd.의 등록 상표입니다. Android는

More information

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

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

More information

슬라이드 1

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

More information

(define (domain blocksworld (:requirements :strips :typing (:types block (:predicates (on?x - block?y - block (ontable?x - block (clear?x - block (hol

(define (domain blocksworld (:requirements :strips :typing (:types block (:predicates (on?x - block?y - block (ontable?x - block (clear?x - block (hol Artificial Intelligence: Assignment 4 Seung-Hoon Na October 24, 2018 1 Planning with Certainty STRIPS은 Planning을 위한 action-centric 표현 방식으로, 한 action마다 precondition과 effect로 구성된다. Precondition: 주어진 action이

More information

PowerPoint Presentation

PowerPoint Presentation 객체지향프로그래밍 클래스, 객체, 메소드 ( 실습 ) 손시운 ssw5176@kangwon.ac.kr 예제 1. 필드만있는클래스 텔레비젼 2 예제 1. 필드만있는클래스 3 예제 2. 여러개의객체생성하기 4 5 예제 3. 메소드가추가된클래스 public class Television { int channel; // 채널번호 int volume; // 볼륨 boolean

More information

슬라이드 제목 없음

슬라이드 제목 없음 Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each

More information

UI TASK & KEY EVENT

UI TASK & KEY EVENT 2007. 2. 5 PLATFORM TEAM 정용학 차례 CONTAINER & WIDGET SPECIAL WIDGET 질의응답및토의 2 Container LCD에보여지는화면한개 1개이상의 Widget을가짐 3 Container 초기화과정 ui_init UMP_F_CONTAINERMGR_Initialize UMP_H_CONTAINERMGR_Initialize

More information

Microsoft PowerPoint - Chapter 6.ppt

Microsoft PowerPoint - Chapter 6.ppt 6.Static 멤버와 const 멤버 클래스와 const 클래스와 static 연결리스트프로그램예 Jong Hyuk Park 클래스와 const Jong Hyuk Park C 의 const (1) const double PI=3.14; PI=3.1415; // 컴파일오류 const int val; val=20; // 컴파일오류 3 C 의 const (1)

More information