2019

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

Problem: 다음 추상 클래스 LoopAdder가 있다. 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 class LoopAdder { // 추상 클래스 string name; // 루프의 이름 int x, y, sum; // x에서 y까지의 합은 sum void read(); // x, y 값을 읽어 들이는 함수 void write(); // sum을 출력하는 함수 protected: LoopAdder(string name="") { // 루프의 이름을 받는다. 초깃값은 "" this->name = name; } int getX() { return x; } int getY() { return y; } virtual int calculate() = 0; // 순수 가상 함수. 루프를 돌며 합을 구하는 함수 public: void run(); // 연산을 진행하는 함수 }; void LoopAdder::read() { // x, y 입력 cout << name << ":" << endl; cout << "처음 수에서 두번째 수까지 더한다. 두 수를 입력하세요 >> "; cin >> x >> y; } void LoopAdder::write() { // 결과 sum 출력 cout << x << "에서 " << y << "까지의 합 = " << sum << " 입니다" << endl; } void LoopAdder::run() { read(); // x, y를 읽는다 sum = calculate(); // 루프를 돌면서 계산한다. write(); // 결과 sum을 출력한다. } Write a 다음 main() 함수와 Execution Result처럼 되도록 ForLoopAdder class that inherits from the LoopAdder class. ForLoopAdder 클래스의 calculate() 함수는 for 문을 이용하여 합을 구한다. ...

Problem: The following is an abstract class Converter that converts units. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Converter { protected: double ratio; virtual double convert(double src)=0; // src를 다른 단위로 변환한다. virtual string getSourceString()=0; // src 단위 명칭 virtual string getDestString()=0; // dest 단위 명칭 public: Converter(double ratio) { this->ratio = ratio; } void run(){ double src; cout << getSourceString() << "을 " << getDestString() << "로 바꿉니다. "; cout << getSourceString() << "을 입력하세요>> "; cin >> src; cout << "변환 결과 : " << convert(src) << getDestString() << endl; } }; Write a km를 mile(마일)로 변환하는 KmToMile class that inherits from the Converter class. The main() function and execution result are as follows. ...