Posts

Problem: 배열을 이용하여 이원 탐색 트리를 만들고 탐색하는 프로그램을 작성하라. 입력 : 정렬이 되지 않은 숫자들 프로그램 : 2.1 입력된 숫자들을 하나씩 읽으면서 이원 탐색 트리 배열 만들기 2.2 숫자 하나를 입력하면 이원탐색트리 알고리즘을 적용하여 해당하는 배열의 첨자를 출력하기 (이 때 출력은 배열 원소들을 차례대로 출력하고 해당하는 배열 첨자를 출력) Execution Result: Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include using namespace std; void newBinarySearchTree(int *num_arr, int size, int *new_num_arr) { for(int i=0; i<size+20; i++){ // 이원탐색트리 배열 -1로 초기화 new_num_arr[i] = -1; } new_num_arr[0] = num_arr[0]; for(int i=1; i<size; i++){ int index=0; // 새로 들어올 숫자가 이원탐색트리 배열의 루트보다 작으면 왼쪽으로 이동 if(new_num_arr[0] > num_arr[i]) { for(int j=2*index+1;;) { if(new_num_arr[j] != -1){ //삽입하려는 이원탐색트리 배열공간이 NULL이 아니면 비교 if(new_num_arr[j] < num_arr[i]) j=2*j+2; // 삽입하고자 하는 숫자가 더 크면 2j+2 else if(new_num_arr[j] > num_arr[i]) j=2*j+1; // 삽입하고자 하는 숫자가 더 작으면 2j+1 z else { //같은 숫자가 나오면 오류메시지 출력 후 프로그램 비정상 종료 cout << "same data error...\n"; exit(1); } } else if(new_num_arr[j] == -1) { // 삽입하려는 이원탐색트리 배열 공간이 NULL이면 바로 삽입 new_num_arr[j] = num_arr[i]; break; } } } // 새로 들어올 숫자가 이원탐색트리 배열의 루트보다 크면 오른쪽으로 이동 else if(new_num_arr[0] < num_arr[i]) { for(int j=2*index+2;;) { if(new_num_arr[j] != -1){ // 삽입하려는 이원탐색트리 배열공간이 NULL이 아니면 비교 if(new_num_arr[j] < num_arr[i]) j=2*j+2; else if(new_num_arr[j] > num_arr[i]) j=2*j+1; else { cout << "same data error...\n"; exit(1); } } else if(new_num_arr[j] == -1) { new_num_arr[j] = num_arr[i]; break; } } } else continue; } } void find(int *new_num_arr, int size) { int x, flag; cout << "찾고자 하는 숫자 입력 : "; cin >> x; for(int i=0; i<size; i++) // 이원탐색트리 배열의 모든 원소 출력 cout << "arr[" << i << "] : " << new_num_arr[i] << endl; for(int i=0; i<size; i++){ if(new_num_arr[i] == x) { cout << "index : " << i; flag = true; break; } else flag = false; } if(!flag) // flag가 false이면 찾고자 하는 숫자가 없다고 출력 cout << "찾고자 하는 숫자 없음\n"; } int main() { int num_arr[] = {50, 40, 55, 30, 45, 54, 53, 1, 60, 301, 2}; int num_arr_size = sizeof(num_arr)/sizeof(num_arr[0]); int *new_num_arr = new int [num_arr_size + 20]; // 이원탐색트리 배열 공간 생성 newBinarySearchTree(num_arr, num_arr_size, new_num_arr); find(new_num_arr, num_arr_size + 20); } Explanation: ...

Problem: 지금까지의 프로젝트를 참고하여 2 pass assembler를 만들면 됩니다. 먼저 어셈블러(Assembler)란? 하드웨어가 직접 이해하여 실행하는 기계어는 일반적으로 비트 열 또는 16진수로 표현되기 때문에 인간이 이해하기 어렵다. 그래서 인간이 이해하기 쉽도록 기계어와 거의 일대일로 대응하는 기호로 표현된 언어로 어셈블러 언어가 있으며, 어셈블러 언어를 기계어로 번역하는 프로그램을 어셈블러, 번역하는 것을 어셈블이라고 합니다. 어셈블러의 역할을 그림으로 간단하게 나타내 보면 다음과 같습니다. 이 글에서 구현 할 2 패스 어셈블러의 알고리즘을 보겠습니다. pass 1 : ...

합병 정렬(Merge Sort)이란? 분할 정복 알고리즘(=Divide and conquer algorithm 즉, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘입니다.)의 하나로 O(n log n)의 시간 복잡도를 가지고 있습니다. 합병 정렬의 작동 알고리즘은 아래와 같습니다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 이해가 잘 안간다면 아래 애니메이션을 통해 작동 원리를 쉽게 이해할 수 있습니다. ...

삽입 정렬(Insertion Sort)이란? 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다. 삽입 정렬의 시간 복잡도는 O(n2)이며 안정 정렬입니다. 또한 배열이 길어질수록 효율이 매우 떨어지지만 구현이 간단하다는 장점이 있습니다. 삽입 정렬의 예 삽입 정렬의 애니메이션 -Simpsons contributor- 삽입 정렬 알고리즘을 구현하기 전에 의사코드(Pseudocode)로 먼저 이해를 하고 코드를 작성하는 것이 더 쉽게 작성할 수 있을 것입니다. Pseudocode : 1 2 3 4 5 6 7 8 9 //InsertionSort pseudo code InsertionSort(A,n) // sort A[1...n] for j <- 2 to n do key <- A[j] i <- j-1 while i>0 and A[i]>key do A[i+1] <- A[i] i <- i-1 A[i+1] <- key CCode: ...

Problem: vector<Shape*> v;를 이용하여 간단한 그래픽 편집기를 콘솔 바탕으로 만들어보자. 생성된 도형 객체를 v에 삽입하고 관리하라. 9장 Exercise Problem 10번의 힌트를 참고하라. Shape과 Circle, Line, Rect 클래스는 다음과 같다. Execution Result: Objective & Hints: vector를 활용하는 종합 응용 Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 #include #include using namespace std; class Shape { protected: virtual void draw() = 0; public: void paint() { draw(); } }; class Circle : public Shape { protected: virtual void draw(){ cout << "Circle" << endl; } }; class Rect : public Shape { protected: virtual void draw() { cout << "Rectangle" << endl; } }; class Line : public Shape { protected: virtual void draw() { cout << "Line" << endl; } }; class UI { public: static int seleteMenu() { int n; cout << "삽입:1, 삭제:2, 모두보기:3, 종료:4 >> "; cin >> n; return n; } static int seleteShape() { int n; cout << "선:1, 원:2, 사각형:3 >> "; cin >> n; return n; } static int seleteDelIndex() { int n; cout << "삭제하고자 하는 도형의 인덱스 >> "; cin >> n; return n; } static void showAll(vector<Shape*> &v, vector<Shape*>::iterator &it) { int i=0; for(it = v.begin();it!=v.end(); it++, i++){ // vector v의 첫 원소부터 끝 원소까지 탐색 및 출력 cout << i << ": "; v.at(i)->paint(); } } }; class GraphicEditor { vector<Shape*> v; vector<Shape*>::iterator it; public: GraphicEditor() { cout << "그래픽 에디터입니다.\n"; start(); } void start() { while(true){ int n; n = UI::seleteMenu(); switch(n){ case 1: //삽입을 선택한 경우 n = UI::seleteShape(); switch(n){ case 1: //선을 선택한 경우 v.push_back(new Line()); break; case 2: //원을 선택한 경우 v.push_back(new Circle()); break; case 3: //사각형을 선택한 경우 v.push_back(new Rect()); break; default: cout << "잘못 선택하셨습니다.\n"; break; } break; case 2:{ //삭제를 선택한 경우 n = UI::seleteDelIndex(); if(n >= v.size()

Problem: vector를 이용하여 아래 Circle 클래스의 객체를 삽입하고 삭제하는 프로그램을 작성하라. 삭제 시에는 이름이 같은 모든 원을 삭제한다. 1 2 3 4 5 6 7 8 9 10 class Circle { string name; // 이름 int radius; // 반지름 public: Circle(int radius, string name) { this->radius = radius; this->name = name; } double getArea() { return 3.14*radius*radius; } string getName() { return name; } }; Execution Result: ...

Problem: 암호 관리 응용프로그램을 map을 이용하여 작성하라. 실행 과정은 다음과 같다. Execution Result: Objective & Hints: map 컨테이너에 삽입 및 조회 응용 이름과 점수를 쌍으로 저장할 맵 컨테이너로 map<string, string>을 이용하면 됩니다. 아래 링크에 있는 Exercise Problem 10장 13번을 참고하세요. Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include using namespace std; void insert(map<string, string> &pwManager){ string name, pw; cout << "이름 암호>> "; cin >> name >> pw; pwManager.insert(make_pair(name, pw)); } void checkNamePw(map<string, string> &pwManager){ string name, pw; cout << "이름? "; cin >> name; while(true){ cout << "암호? "; cin >> pw; if(pwManager[name] == pw){ cout << "통과!!\n"; break; } else cout << "실패~~\n"; // 틀리면 출력 후 다시 암호 질문 } } int main() { map<string, string> pwManager; cout << "***** 암호 관리 프로그램 WHO를 시작합니다 *****\n"; while(true){ cout << "삽입:1, 검사:2, 종료3>> "; int n; cin >> n; switch(n){ case 1: insert(pwManager); break; case 2: checkNamePw(pwManager); break; case 3: cout << "프로그램을 종료합니다..."; return 0; } } } Explanation: ...

Problem: map 컨테이너를 이용하여 (이름, 성적)을 저장하고 이름으로 성적을 조회하는 점수 관리 프로그램을 만들어라. 이름은 빈칸 없이 입력하는 것을 원칙으로 한다. Execution Result: Objective & Hints: map 컨테이너 활용 이름과 점수를 쌍으로 저장할 맵 컨테이너로 map<string, int>를 이용하면 된다. Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #include #include using namespace std; int main() { map<string, int> Score; // map 컨테이너 생성. 키는 한글 이름, 값은 정수 점수 cout << "***** 점수관리 프로그램 HIGH SCORE을 시작합니다 *****\n"; while(true){ int num; int score; string name; cout << "입력:1, 조회:2, 종료:3 >> "; cin >> num; switch (num){ case 1: cout << "이름과 점수>> "; cin >> name >> score; Score.insert(make_pair(name, score)); // map에 저장 break; case 2: cout << "이름 >> "; cin >> name; if(Score.find(name) == Score.end()) // name '키'를 끝까지 찾았는데 없음 cout << "없음" << endl; else cout << name << "의 점수는 " <<Score[name] << endl; // Score에서 name의 값을 찾아 출력 break; case 3: cout << "프로그램을 종료합니다...\n"; return 0; default : cout << "제대로 입력해\n"; break; } } } Explanation: ...

Problem: Open Challenge를 수정하여 사용자가 어휘를 삽입할 수 있도록 기능을 추가하라. Execution Result는 다음과 같다. Execution Result: Objective & Hints: vector 컨테이너의 종합 응용 연습 랜덤 정수를 방생시키기 위해 다음 두 라인의 코드가 필요하며, 과 를 include 해야 합니다. 1 2 srand((unsigned)time(0)); // 시작할 때마다, 다른 랜덤수를 발생시키기 위한 seed 설정 int n = rand(); // 0에서 RAND_MAX(32767) 사이의 랜덤한 정수가 n에 발생 Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 #include #include #include #include using namespace std; class Word { string engWord, korWord; public: Word(string engWord=0, string korWord=0){ this->engWord = engWord; this->korWord = korWord; } void inputWord(string engWord, string korWord){ this->engWord = engWord; this->korWord = korWord; } string getEngWord(){ return engWord; } string getKorWord(){ return korWord; } }; void inputWord(vector &v) { cout << "영어 단어에 exit을 입력하면 입력 끝\n"; string engWord, korWord; while(true){ cout << "영어 >>"; cin >> engWord; if(engWord == "exit") break; cout << "한글 >>"; cin >> korWord; v.push_back(Word(engWord, korWord)); } } void gameStart(vector &v) { srand((unsigned)time(0)); int num; cout << "영어 어휘 테스트를 시작합니다. 1~4 외 다른 입력시 종료.\n"; while(true){ int randNum = rand()%v.size(); cout << v.at(randNum).getEngWord() << "?\n"; string ex[4] = " "; int tmp = rand()%4; ex[tmp] = v.at(randNum).getKorWord(); for(int i=0; i<4; i++){ if(tmp == i) continue; while(true){ // 중복되는 숫자가 없게 처리 int numChosen = rand()%v.size(); if(ex[0]!=v.at(numChosen).getKorWord() && ex[1]!=v.at(numChosen).getKorWord() && ex[2]!=v.at(numChosen).getKorWord() && ex[3]!=v.at(numChosen).getKorWord()){ ex[i] = v.at(numChosen).getKorWord(); break; } } } for(int i=0; i<4; i++) cout << "(" << i+1 << ") " << ex[i] << ' '; cout << ":>"; cin >> num; // 숫자만 입력 if(num == -1

Problem: 책의 년도, 책이름, 저자 이름을 담은 Book 클래스를 만들고, vector v;로 생성한 벡터를 이용하여 책을 입고하고, 저자와 년도로 검색하는 프로그램을 작성하라. Execution Result: Objective & Hints: vector에 객체의 삽입, 검색 응용 연습 Code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include #include #include using namespace std; class Book{ int year; string b_name; string p_name; public: void set(int year, string b_name, string p_name){ this->year = year; this->b_name = b_name; this->p_name = p_name; } string getP(){ return p_name; } int getY(){ return year; } void show(){ cout << year << "년도, " << b_name << ", " << p_name << endl; } }; int main() { vector v; Book b; int year; string b_name; string p_name; cout << "입고할 책을 입력하세요. 년도에 -1을 입력하면 입고를 종료합니다.\n"; while(true){ cout << "년도>>"; cin >> year; if(year==-1) break; fflush(stdin); cout << "책이름>>"; getline(cin, b_name); cout << "저자>>"; getline(cin, p_name); b.set(year, b_name, p_name); v.push_back(b); } cout << "총 입고된 책은 " << v.size() << "권 입니다.\n"; cout << "검색하고자 하는 저자 이름을 입력하세요>>"; fflush(stdin); getline(cin, p_name); for(int i=0; i<v.size(); i++){ if(v[i].getP() == p_name) v[i].show(); } cout << "검색하고자 하는 년도를 입력하세요>>"; cin >> year; for(int i=0; i<v.size(); i++){ if(v[i].getY() == year) v[i].show(); } } Explanation: ...