[C언어 백준 풀이][Silver V] 2609번 : 최대공약수와 최소공배수 / 2571번 : 수 정렬하기 2 / 10814번 : 나이순 정렬 / 11650번 : 좌표 정렬하기

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge에 수록되어 있는 문제들 중 Solved.ac 기준 클래스 2+ 에센셜에 해당하는 문제들을 풀이해보도록 하겠습니다.

 

 

풀어볼 문제의 목록은 2609번 최대공약수와 최소공배수, 2571번 수 정렬하기 2, 10814번 나이순 정렬, 11650번 좌표 정렬하기의 4문제입니다.

 

 

2609번 : 최대공약수와 최소공배수

 

두 자연수를 입력으로 받아 그 최대공약수와 최소공배수를 구하는 기본적인 문제입니다.

최대공약수와 최소공배수를 구하는 방법만 알면 풀 수 있습니다.

 

#include<stdio.h>

int main() {
    int a, b, temp, max = 1;
    scanf("%d %d", &a, &b);
    if(a > b) {
        temp = a;
        a = b;
        b = temp;
    }
    for(int i=2; i<=a; i++) if(a%i == 0 && b%i == 0) max = i;
    printf("%d\n%d", max, a*b/max);
}

 

우선 두 수 중 작은 수와 큰 수를 구분하는 과정이 필요합니다.

저의 경우에는 a<=b가 되도록 정렬하였습니다.

그 다음 i=2부터 a까지 두 수를 계속 나눠보며 나누어떨어지는 최댓값을 찾았습니다. (= 최대공약수)

최소공배수는 a/max * b/max * max 이므로 결국 a*b/max로 계산할 수 있습니다.

 

두 수가 서로소인 경우 최대공약수는 1이 되므로, max의 초깃값은 반드시 1로 설정해야 합니다.

 

 

2751번 : 수 정렬하기 2

 

N개의 수가 입력되면 그 수들을 오름차순으로 정렬하는 문제입니다.

다만 데이터의 수가 최대 100만개이므로 O(N^2) 정렬 알고리즘을 사용하면 시간 초과가 발생하게 됩니다.

따라서 O(N log N) 정렬 알고리즘인 merge sort나 quick sort를 사용해야 합니다.

 

#include<stdio.h>

int N, arr[1000005], arrCopy[1000005];

void merge(int arr[], int left, int mid, int right) {
    int i = left, j = mid+1, k = left;
    while(i<=mid && j<=right) {
        if(arr[i] <= arr[j]) arrCopy[k++] = arr[i++];
        else arrCopy[k++] = arr[j++];
    }
    while(i<=mid) arrCopy[k++] = arr[i++];
    while(j<=right) arrCopy[k++] = arr[j++];
    for(int a=left; a<=right; a++) arr[a] = arrCopy[a];
}

void mergeSort(int arr[], int left, int right) {
    int mid;
    if(left < right) {
        mid = (left+right)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d", &arr[i]);
    mergeSort(arr, 0, N-1);
    for(int i=0; i<N; i++) printf("%d\n", arr[i]);
}

 

저의 경우에는 Merge Sort가 여러모로 용이해서 병합 정렬을 사용하였습니다.

N개의 데이터를 입력받은 뒤 배열에 저장하고, merge 함수에서 이들을 분리한 뒤 다시 합치는 과정에서 크기 순서대로 정렬을 하게 되는 알고리즘입니다.

 

C언어 모든 정렬 알고리즘 가장 간단한 코드 정리 (순차, 버블, 삽입, 선택, 병합, 퀵 정렬)

 

해당 알고리즘은 위의 포스트에도 제가 정리해두었습니다.

(병합 정렬을 포함한 6가지 정렬 알고리즘을 바로 사용할 수 있게 작성해두었으니 참고해보시는 것도 좋습니다.)

 

 

10814번 : 나이순 정렬

 

위의 수 정렬하기 문제에서 약간 업그레이드 되어 이름까지 같이 입출력을 해야하는 문제입니다.

사실 구조체를 이용하면 편하지만, 위의 merge Sort를 최대한 그대로 활용하여 문제를 풀이해보겠습니다.

문제에서 주목할 점은 나이가 같은 경우 이름 순으로 정렬하는 것이 아닌, 먼저 가입한 사람이 그대로 위로 오도록 출력해야 한다는 것입니다.

따라서 이름 자체는 문자열의 정렬을 해줄 필요가 없습니다.

 

#include<stdio.h>
#include<string.h>

int N, arr[100005], arrCopy[100005];
char name[100005][105], nameCopy[100005][105];

void merge(int left, int mid, int right) {
    int i = left, j = mid+1, k = left;
    while(i<=mid && j<=right) {
        if(arr[i] <= arr[j]) arrCopy[k] = arr[i], strcpy(nameCopy[k++], name[i++]);
        else arrCopy[k] = arr[j], strcpy(nameCopy[k++], name[j++]);
    }
    while(i<=mid) arrCopy[k] = arr[i], strcpy(nameCopy[k++], name[i++]);
    while(j<=right) arrCopy[k] = arr[j], strcpy(nameCopy[k++], name[j++]);
    for(int a=left; a<=right; a++) arr[a] = arrCopy[a], strcpy(name[a], nameCopy[a]);
}

void mergeSort(int left, int right) {
    int mid;
    if(left < right) {
        mid = (left+right)/2;
        mergeSort(left, mid);
        mergeSort(mid+1, right);
        merge(left, mid, right);
    }
}

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d %s", &arr[i], name[i]);
    mergeSort(0, N-1);
    for(int i=0; i<N; i++) printf("%d %s\n", arr[i], name[i]);
}

 

개선하여 풀이한 코드는 위와 같습니다.

단순히 수 정렬을 하는 과정에 문자열 배열까지 같이 해주면 됩니다.

사실 여기에서 이름을 알파벳 순으로 정렬하는 조건까지 있었어도, 조건문 한 줄만 추가해주면 되기 때문에 그렇게 어렵지 않습니다.

(10행의 if(arr[i] <= arr[j]) 부분을 if(arr[i] <= arr[j] || (arr[i] == arr[j] && strcmp(name[i], name[j]) < 0))으로 바꾸어주면 됨)

 

병합 정렬은 stable한 정렬이기 때문에, 정렬하는 과정에서 동률인 데이터들의 순서가 뒤바뀌지 않습니다.

따라서 다른 조치를 취하지 않고 그대로 번호만 정렬해줘도 문제 없습니다.

 

 

11650번 : 좌표 정렬하기

 

위의 문제에 해당하는 '나이순 정렬' 문제보다 조금 더 업그레이드 된 정렬 문제입니다.

x 좌표를 오름차순으로 배열하고, 이 때 x 좌표가 동률일 경우 y 좌표를 오름차순으로 배열하는 조건입니다.

구조체나 2차원 배열을 써도 되지만 저는 그냥 2개의 별개의 배열을 사용하여 정렬을 해보겠습니다.

 

#include<stdio.h>

int N, x[100005], xCopy[100005], y[100005], yCopy[100005];

void merge(int left, int mid, int right) {
    int i = left, j = mid+1, k = left;
    while(i<=mid && j<=right) {
        if(x[i] < x[j] || (x[i] == x[j] && y[i] < y[j])) xCopy[k] = x[i], yCopy[k++] = y[i++];
        else xCopy[k] = x[j], yCopy[k++] = y[j++];
    }
    while(i<=mid) xCopy[k] = x[i], yCopy[k++] = y[i++];
    while(j<=right) xCopy[k] = x[j], yCopy[k++] = y[j++];
    for(int a=left; a<=right; a++) x[a] = xCopy[a], y[a] = yCopy[a];
}

void mergeSort(int left, int right) {
    int mid;
    if(left < right) {
        mid = (left+right)/2;
        mergeSort(left, mid);
        mergeSort(mid+1, right);
        merge(left, mid, right);
    }
}

int main() {
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d %d", &x[i], &y[i]);
    mergeSort(0, N-1);
    for(int i=0; i<N; i++) printf("%d %d\n", x[i], y[i]);
}

 

위의 문제 풀이와 마찬가지로 병합 정렬을 사용하여 정렬을 수행한 코드입니다.

정렬 기준이 2개일 경우 어려워 보일 수 있지만, 그냥 두 배열이 이동하는 것을 똑같이 수행하되 조건식만 바꿔주면 됩니다.

위의 코드에서는 x좌표는 x 배열에, y좌표는 y 배열에 저장하였으며 copy 배열은 merge sort 과정에서 임시로 사용하는 배열의 이름입니다.