2019

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

문제 : 다음 추상 클래스 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을 출력한다. } LoopAdder 클래스를 상속받아 다음 main() 함수와 실행 결과처럼 되도록 ForLoopAdder 클래스를 작성하라. ForLoopAdder 클래스의 calculate() 함수는 for 문을 이용하여 합을 구한다. ...

문제 : 다음은 단위를 변환하는 추상 클래스 Converter이다. 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; } }; Converter 클래스를 상속받아 km를 mile(마일)로 변환하는 KmToMile 클래스를 작성하라. main() 함수와 실행 결과는 다음과 같다. ...