반응형

병합 정렬

: 대표적인 분할 정복 방법을 채택한 알고리즘으로 O(NlogN)의 시간 복잡도를 가지는 정렬 알고리즘

 

특징

-. 일단 반으로 정확히 나누고 나중에 합치는 방식으로, 퀵 정렬(Quick Sort)와 다르게 Pivot 값이 존재하지 않는다.

-. 기존 데이터를 담을 추가적인 배열이 필요하다는 점에서 메모리 활용은 비효율적이다.

-. 초기 단계에는 모두 원소가 1인 상태로 분할되어있으며, 한 번 병합할 때마다 2의 배수만큼 씩 병합한다.

-. 너비는 N이지만 높이는 logN이기 때문에 전체 시간 복잡도는 NlogN이다.

더보기

너비? 높이?

너비: i와 j를 비교해 더 작은 값을 k 위치에 저장

        N번의 시도 후 정렬 완료

높이: 너비 정렬을 총 logN 번 반복하면 정렬 완료

 

병합 정렬(Merge Sort) Sequence

 

코드

#include <iostream>
using namespace std;
#define number 8

int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.

void merge(int a[], int m, int middle, int n){
    // m: 정렬할 배열의 시작 지점
    // middle: 정렬할 배열의 중간 지점
    // n: 정렬할 배열의 끝 지점

    int i = m;
    int j = middle+1;
    int k = m;

    // 작은 순서대로 배열에 삽입
    while(i<=middle && j <= n){
        // i가 j보다 더 작으면 새로운 배열에 저장
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }
        // 그렇지 않으면 j 값 저장
        else{
            sorted[k] = a[j];
            j++;
        }
        k++; // 한 번 저장하면 k 증가
    }

    // 남은 데이터 삽입
    // i가 먼저 끝났다면 j 모두 새로운 배열에 저장
    if(i > middle){
        for(int t = j; t <= n; t++){
            sorted[k] = a[t];
            k++;
        }
    }
    // j가 먼저 끝났으면 i 모두 새로운 배열에 저장
    else{
        for(int t = i;t<=middle;t++){
            sorted[k] = a[t];
            k++;
        }
    }

    // 정렬된 배열을 실제 배열에 삽입
    for(int t = m; t <= n; t++){
        a[t] = sorted[t];
    }
}

void merge_sort(int a[], int m, int n){
    // 크기가 1보다 큰 경우 return
    if(m < n){
        int middle = (m+n) / 2;
        merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
        merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
        merge(a, m, middle, n); // 정렬 후 합치기
    }
}

int main(void){
    int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
    merge_sort(arr, 0, number-1);
    for(int i=0;i<number;i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

출력

1 3 5 5 6 7 8 9

 

시간 복잡도

병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.

☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.

반응형

'Algorithm' 카테고리의 다른 글

[Algorithm] 힙 정렬(Heap Sort)  (0) 2023.04.09
[Algorithm] C++ STL sort 함수  (0) 2023.04.08
[Algorithm] 기초 정렬 문제  (0) 2023.04.08
[Algorithm] 퀵 정렬(Quick Sort)  (0) 2023.04.08
[Algorithm] 삽입 정렬(Insertion Sort)  (0) 2023.04.03
반응형

백준 사이트

초심자라면 단계별로 풀어보기, 알고리즘 분류에서 문제 풀어보는 게 좋다.

그 중에서도 단계별로 풀어보기에서 정렬해보기부터 시작하면 좋다.

 

기본적으로 1초에 1억 번 정도 연산한다고 생각하고 문제 풀면 됨.

 

1. 수 정렬하기(2750)

https://www.acmicpc.net/problem/2750

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

데이터의 개수가 최대 1,000개. N^2 = 1,000,000개

N^2 알고리즘으로 풀어도 크게 문제 없이 해결 가능하다.

#include <iostream>
using namespace std;

void Print(int *data, int N){
    for(int i=0;i<N;i++)
        cout << data[i] << endl;
}

void Selection_Sort(int *data, int N){
    int tmp, min, idx = 0;
    for(int i=0;i<N;i++){
        min = 1001;
        for(int j=i;j<N;j++){
            if(min > data[j]){
                min = data[j];
                idx = j;
            }
        }

        tmp = data[i];
        data[i] = data[idx];
        data[idx] = tmp;
    }
}

void Bubble_Sort(int *data, int N){
    int tmp = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(data[j] > data[j+1]){
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

int main(void){
    int N;
    int data[1000];

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> data[i];

    Selection_Sort(data, N);
    Bubble_Sort(data, N);
    //Insert_Sort(data, N);
    //Quick_Sort(data, N);
    Print(data, N);
    return 0;
}

 

2. 세수정렬

https://www.acmicpc.net/problem/2752

 

2752번: 세수정렬

숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다.

www.acmicpc.net

#include <iostream>
using namespace std;
#define N 3

int arr[3]={0,};

void Input(){
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << " ";
}

void Insertion_Sort(){
    int j, tmp;
    for(int i=0;i<N-1;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }
}

int main(void){

    Input();
    //Selection_Sort();
    Insertion_Sort();
    Output();

    return 0;
}

 

3. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

 

2751번: 수 정렬하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

#include <iostream>
using namespace std;

int N;
int arr[1000000+10];

void Input(){
    cin >> N;
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << "\n";
}

void Quick_Sort(int start, int end){
    
    if(start >= end)
        return;

    int mid = start;
    int i = start+1;
    int j = end;
    int tmp;

    while(i <= j){
        // 오른쪽으로 가면서 pivot값보다 큰 값 찾기
        while(arr[mid] >= arr[i]){
            i++;
        }

        // 왼쪽으로 가면서 pivot값보다 작은 값 찾기
        while(arr[mid] <= arr[j] && start < j){
            j--;
        }

        // 엇갈렸으면 pivot 값과 작은 값 변경
        if(i > j){
            tmp = arr[j];
            arr[j] = arr[mid];
            arr[mid] = tmp;
        }
        // 엇갈리지 않았으면 두 값 변경
        else{
            tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = arr[j];
        }
    }

    // start, end 다시 조정해 재귀
    Quick_Sort(start, j-1);
    Quick_Sort(j+1, end);
}

int main(void){
    Input();
    Quick_Sort(0, N-1);
    Output();
}
반응형
반응형

선택 정렬, 버블 정렬, 삽입 정렬의 한계

: O(N*N)은 데이터 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다.

2^10 = 1,000

2^20 = 1,000,000

log(2)N = (N이 1,000,000일 때) 20

 

퀵 정렬(Quick Sort)

: 대표적인 분할 정복 알고리즘으로 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 후 배열을 반으로 나누는 정렬 알고리즘

더보기

분할 정복

: 배열을 분할해서 계산하는 알고리즘

 

퀵 정렬(Quick Sort) Sequence

더보기

기준값 = 피벗(Pivot)

왼쪽에서 오른쪽으로 이동하면서 Pivot 보다 큰 값 하나 선택

오른 쪽에서 왼쪽으로 이동하면서 Pivot보다 작은 값 하나 선택

작은 값의 index < 큰 값의 index: Pivot과 작은 값 교환

작은 값의 index > 큰 값의 index: 작은 값과 큰 값 교환

 

 

Code

#include <iostream>
using namespace std;

int number = 10;
int Data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort_up(int *data, int start, int end){
    // start: 정렬을 수행하는 부분집합의 첫 번째 원소
    // end: 정렬을 수행하는 부분집합의 마지막 원소

    // 원소가 1개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot

    int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
    int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
    int tmp;

    // 엇갈리는 경우 while 탈출
    while(i <= j){
        // i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
        while(data[i] <= data[key]){
            i++;
        }

        // j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
        // index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
        while(data[j] >= data[key] && j > start){
            j--;
        }

        // 엇갈린 경우 pivot값과 현재 data 변경
        if(i > j){
            tmp = data[j];
            data[j] = data[key];
            data[key] = tmp;
        }
        // 엇갈리지 않은 경우 i와 j index의 data 변경
        else{
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }

    // 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
    quickSort_up(data, start, j-1); // 왼쪽 data
    quickSort_up(data, j+1, end); // 오른쪽 data
}

void quickSort_down(int *data, int start, int end){
    // start: 정렬을 수행하는 부분집합의 첫 번째 원소
    // end: 정렬을 수행하는 부분집합의 마지막 원소

    // 원소가 1개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot

    int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
    int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
    int tmp;

    // 엇갈리는 경우 while 탈출
    while(i <= j){
        // i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
        while(data[i] >= data[key]){
            i++;
        }

        // j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
        // index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
        while(data[j] <= data[key] && j > start){
            j--;
        }

        // 엇갈린 경우 pivot값과 현재 data 변경
        if(i > j){
            tmp = data[j];
            data[j] = data[key];
            data[key] = tmp;
        }
        // 엇갈리지 않은 경우 i와 j index의 data 변경
        else{
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }

    // 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
    quickSort_down(data, start, j-1); // 왼쪽 data
    quickSort_down(data, j+1, end); // 오른쪽 data
}

int main(void){
    quickSort_up(Data, 0, number-1); // 오름차순
    for(int i=0;i<10;i++){
        cout << Data[i] << " ";
    }
    cout << endl;
    quickSort_down(Data, 0, number-1); // 내림차순
    for(int i=0;i<10;i++){
        cout << Data[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

 

만약 아래 배열을 정렬한다면?

선택 정렬의 시간 복잡도: N^2 = 100

퀵 정렬의 시간 복잡도: 

1 2 3 4 5 => 5 * 5 = 25

6 7 8 9 10 => 5 * 5 = 25

-> 25 + 25 = 50

∴ O(NlogN)의 시간복잡도를 갖는 알고리즘을 이용하면 100만개 정도의 데이터는 어렵지 않게 정렬이 가능하다.

 

시간복잡도

평균 : N*logN

최악의 경우: N^2

 

만약 이미 오름차순 정렬되어있는 배열을 퀵정렬을 이용해 오름차순 정렬한다면?

=> 분할 정복의 이점을 사용하지 못하고 있으므로, 이런 경우에는 insertion sort를 사용하는 게 효율적이다.

 

 

반응형
반응형

버블 정렬(Bubble Sort)

: 옆에 있는 값과 비교해 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법

 

버블 정렬 Sequence

더보기
정렬 DATA
반복 1
반복 2
반복 3
반복 4
반복 5
반복 6
반복 7
반복 8
반복 9

한 번 반복이 끝났을 때 가장 큰 값이 가장 마지막 위치로 이동

 

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    for(i=0;i<10;i++){
        cout << arr[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

 

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 1) / 2

= N * (N - 1) / 2

= O(N^2)

 

실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다.
: Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다.
반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.

참고로, 정렬 알고리즘 중 가장 느린 건 Bubble Sort이다.
반응형

'Algorithm' 카테고리의 다른 글

[Algorithm] 퀵 정렬(Quick Sort)  (0) 2023.04.08
[Algorithm] 삽입 정렬(Insertion Sort)  (0) 2023.04.03
[Algorithm] 선택 정렬(Selection Sort)  (0) 2023.04.02
DFS/BFS  (0) 2022.04.07
[Algorithm] 구현(Implementation)  (0) 2022.04.06
반응형

선택 정렬(Selection sort)

: 가장 작은 것을 선택해서 가장 앞으로 보내는 알고리즘

 

1 10 5 8 7 6 4 3 2 9
1 10 5 8 7 6 4 3 2 9
1 2 5 8 7 6 4 3 10 9
1 2 3 8 7 6 4 5 10 9
1 2 3 4 7 6 8 5 10 9
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

 

코드

#include <iostream>
using namespace std;

int main(void){
    // 선택 정렬: 가장 작은 것을 선택해서 가장 앞으로 보내자
    int i, j, min, idx, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        min = 9999;
        for(j=i;j<10;j++){
            if(min > array[j]){
                min = array[j];
                idx = j;
            }
        }
        tmp = array[i];
        array[i] = array[idx];
        array[idx] = tmp;
        cout << array[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

 

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 9) / 2

=> N * (N - 1) / 2

∴ O(N^2)

반응형

'Algorithm' 카테고리의 다른 글

[Algorithm] 삽입 정렬(Insertion Sort)  (0) 2023.04.03
[Algorithm] 버블 정렬(Bubble Sort)  (0) 2023.04.02
DFS/BFS  (0) 2022.04.07
[Algorithm] 구현(Implementation)  (0) 2022.04.06
[Algorithm] Greedy  (0) 2022.04.05
반응형

약수

티어 : Bronze 1
알고리즘 분류 : 수학, 정수론


약수 짝끼리의 곱은 N이 된다는 성질을 이용했다.

e.g., 8의 약수 = {1, 2, 4, 8}

         → 1 * 8 = 8

         → 2 * 4 = 8

따라서 진짜 약수를 모두 벡터에 담은 후 벡터를 오름차순 정렬하면 벡터의 첫 번째 요소와 마지막 요소는 약수 짝이 될 것이므로 두 값을 곱한 값이 N이 된다.

Algorithm

1. 입력받은 진짜 약수를 모두 vector에 담음
2. 벡터를 오름차순 정렬해 약수끼리 짝이 맞을 수 있도록 함
3. 벡터의 첫 번째 요소와 마지막 요소를 곱함

 

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt; // N의 진짜 약수의 개수
vector <int> v; // N의 진짜 약수
int N;

void input(){
    cin >> cnt;
    for(int i=0;i<cnt;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void solution(){
    // 벡터 오름차순 정렬
    sort(v.begin(), v.end());
    // 벡터의 처음 값과 마지막 값 곱함
    N = v[0] * v[v.size()-1];
}

void output(){
    cout << N;
}

int main(void){
    input();
    solution();
    output();
    return 0;
}

메모리: 2020 KB
시간: 0 ms

반응형

'백준 > C++' 카테고리의 다른 글

[백준 4375] 1 C++  (0) 2022.12.03
[백준 10430] 나머지 C++  (0) 2022.12.02
반응형

1

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론

 

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

 

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

 

예제 입출력


우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.

처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.

num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.

#include <iostream>
#include <string>
using namespace std;

int cal_len(long long n){
    string num = to_string(n);
    return num.length();
}

long long ispossible(int n){
    // n의 길이 계산
    int len = cal_len(n);
    string num;
    // n의 길이만큼 1로만 구성된 문자열 만들기
    for(int i=0;i<len;i++){
        num += '1'; // O(n)으로 동작
    }
 
    while(true){
        // num이 n의 배수인지 확인
        if(num%n==0) return num.length();
        // num 한 자리 추가
        num += '1';
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 런타임 에러(out_of_range)로 실패 ㅠ

num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.

 

그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.

 

결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.

Algorithm

Brute Force
1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음
2. num이 n으로 나누어 떨어지는지 확인
    2-1. 나누어떨어지면 num의 길이 return
    2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산)
            → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !

 

Code

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num의 크기 줄여주기
        num%=n;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

메모리: 2020 KB
시간: 0 ms

반응형

'백준 > C++' 카테고리의 다른 글

[백준 1037] 약수 C++  (0) 2022.12.03
[백준 10430] 나머지 C++  (0) 2022.12.02
반응형

나머지

티어 : Bronze 5
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 사칙연산

 

문제

(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

 

출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

 

예제 입출력


Code

#include <iostream>
using namespace std;

int main(void){
    int A, B, C;
    cin >> A >> B >> C;
    cout << (A+B)%C << "\n";
    cout << ((A%C)+(B%C))%C << "\n";
    cout << (A*B)%C << "\n";
    cout << ((A%C)*(B%C)%C) << "\n";
    return 0;
}

메모리: 2020 KB
시간: 0 ms

반응형

'백준 > C++' 카테고리의 다른 글

[백준 1037] 약수 C++  (0) 2022.12.03
[백준 4375] 1 C++  (0) 2022.12.03

+ Recent posts