Algorithm Design - 실습(GDC_LCM, Sort)

---

GDC_LCM

최대공약수, 최소공배수를 구하는 과제이다.

#include <iostream>
using namespace std;

// 최대공약수를 계산하는 함수
int gcd(int a, int b) {
    int min, ans = 0;
    if(a>b){
        min = b;
    }
    else{
        min = a;
    }
    for (int i=1; i<=min; i++){
        if (a%i==0 && b%i==0){
            ans = i;
        }
    }
    return ans;
}
// 최소공배수를 계산하는 함수
int lcm(int a, int b) {
    int base = 0;
    if (a>b){
        base = a;
    }
    else{
        base = b;
    }
    for (int i=base; ;i++) {
        if ((i%a == 0) && (i%b == 0)) {
            return i;
        }
    }
}

int main() {
    int a, b;
    cin >> a >>b;
    cout << gcd(a, b) << " " << lcm(a, b);

    return 0;
}

특별한 내용은 없고 최대공약수를 찾을때는 공약수를 계속해서 갱신해나가며 최대공약수를 찾을때까지 ans 변수의 값을 갱신하여 결론을 찾아내는 방식을 이용했다. 최소공배수는 처음으로 찾은 공배수가 최소이므로 발견 즉시 return하는 방법을 이용했다.

---

Sort

간단한 Bubble sort를 진행해보았다.

#include <iostream>
using namespace std;
// 정렬 함수
void MySort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {     
        for (int j = 0; j < n-i-1; j++) { 
            if (arr[j] > arr[j+1]) {
                // swap
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
int main() {
    int n;
    cin >> n; // 첫 번째 줄에서 n 을 입력받음

    int* numbers = new int[n]; // 동적으로 정수 배열을 할당

    // 두 번째 줄에서 n 개의 정수를 입력받음
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    // 버블 정렬 수행
    MySort(numbers, n);
    
    // 정렬된 배열 출력
    for (int i = 0; i < n; i++) {
        cout << numbers[i] << " ";
    }
    return 0;
}

Bubble Sort는 가장 단순하지만 느린 방식의 sorting방식이다. 2중 for문을 이용하여 앞에서부터 인접한 숫자 두개씩 비교하여 앞의 숫자가 더 크면 swap을 진행하는 과정을 반복하여 숫자열을 정렬하는 것이다.

---