백준-1차원 배열 10818 최소, 최대

10818번: 최소, 최대 (acmicpc.net)

 

입력된 정수들의 최소, 최대값을 구하는 프로그램

두가지 방법이 존재한다.

모든 정수를 입력받은 이후 최소, 최대값을 연산할 것인지?->C풀이

입력받는 즉시 최소, 최대값을 비교하여 순회 횟수를 줄일 것인지?-> C++풀이

제약사항

• 0 < N <= 1,000,000
• -1,000,000 <= INPUT <= 1,000,000

주의 사항

첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.

C 풀이

최소, 최대_10818.c

반복문을 2번 돌기 때문에 시간낭비가 심하다. 

/**
* 백준 1차원 배열 10818 최소, 최대
* 입력된 정수들의 최소, 최대값을 구하는 프로그램
* 두가지 방법이 존재한다.
* 모든 정수를 입력받은 이후 최소, 최대값을 연산할 것인지?->C풀이
* 입력받는 즉시 최소, 최대값을 비교하여 순회 횟수를 줄일 것인지?-> C++풀이
* 
* 제한사항
*****************************************
* 0 < N <= 1,000,000                    *
* -1,000,000 <= INPUT <= 1,000,000      *
*****************************************
*
*
*
* 주의
* 첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.
*
* 풀이시간 5분
*/
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main(void)
{
    // 초기 min값은 Intiger의 최대값, 초기 min값은 최소값
    // unsigned 자료형이 아니므로 절반을 나누어 음수 처리 필요
    // <limits.h>에서 INT_MIN, INT_MAX를 통해 처리 가능
    // ex 0x7FFFFFFF = 2147483647, 0x80000000 = -2147483648
    // or 
    // MIN = 1,000,000, MAX = 1,000,000 으로 처리 가능
	int N, MIN = 0x7FFFFFFF, MAX = 0x80000000;

    scanf("%d", &N);
    int* arr = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 0; i < N; ++i)
    {
        if (arr[i] <= MIN)
        {
            MIN = arr[i];
        }
        if (arr[i] >= MAX)
        {
            MAX = arr[i];
        }
    }
    printf("%d %d", MIN, MAX);
	return 0;
}

C++ 풀이

최소, 최대_10818.cpp

두 개의 limits 모두 사용

Vector STL사용

/**
* 백준 1차원 배열 10818 최소, 최대
* 입력된 정수들의 최소, 최대값을 구하는 프로그램
* 두가지 방법이 존재한다.
* 모든 정수를 입력받은 이후 최소, 최대값을 연산할 것인지?->C풀이
* 입력받는 즉시 최소, 최대값을 비교하여 순회 횟수를 줄일 것인지?-> C++풀이
* <limits> 또는 <climits> 둘 중하나를 사용
*
* 제한사항
*****************************************
* 0 < N <= 1,000,000                    *
* -1,000,000 <= INPUT <= 1,000,000      *
*****************************************
*
*
*
* 주의
* 첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.
* 
* 풀이시간 5분
*/
#include <iostream>
#include <limits> // std::numeric_limits<자료형>::min/max();
#include <climits> // INT_MIN, INT_MAX;
#include <vector>

using namespace std;

int main(void)
{
    int N, MIN = INT_MAX;
    int MAX = std::numeric_limits<int>::min();

    cin >> N;
    vector<int> arr;
    for (int i = 0; i < N; ++i)
    {
        int INPUT;
        cin >> INPUT;
        arr.push_back(INPUT);
        if (INPUT <= MIN)
        {
            MIN = INPUT;
        }
        if (INPUT >= MAX)
        {
            MAX = INPUT;
        }
    }

    cout << MIN << " " << MAX << endl;
    return 0;
}

그런데 사실 이 코드는 최적화 되지 않았다. 

조건중에 정수입력을 저장해놓으라는 소리가 없었으므로 동적할당 자체가 필요 없다. 

/**
* 백준 1차원 배열 10818 최소, 최대
* 입력된 정수들의 최소, 최대값을 구하는 프로그램
* 두가지 방법이 존재한다.
* 모든 정수를 입력받은 이후 최소, 최대값을 연산할 것인지?->C풀이
* 입력받는 즉시 최소, 최대값을 비교하여 순회 횟수를 줄일 것인지?-> C++풀이
* <limits> 또는 <climits> 둘 중하나를 사용
*
* 제한사항
*****************************************
* 0 < N <= 1,000,000                    *
* -1,000,000 <= INPUT <= 1,000,000      *
*****************************************
*
*
*
* 주의
* 첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.
* 
* 풀이시간 5분
*/
#include <iostream>

using namespace std;

int main(void)
{
    int N, MIN = 0x7fffffff, MAX = 0x80000000;

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        int INPUT;
        cin >> INPUT;
        if (INPUT <= MIN)
        {
            MIN = INPUT;
        }
        if (INPUT >= MAX)
        {
            MAX = INPUT;
        }
    }

    cout << MIN << " " << MAX << endl;
    return 0;
}

그런데 이전의 C 풀이는 채점했을 때 164ms가 나왔는데 C++ 풀이는 갑자기 388ms로 풀이 시간이 확늘어났다. 왜그럴까?

이건 iostream과 stdio.h에서의 입출력 버퍼를 같이 사용하기 때문이라고 한다. 

기본적으로 C++에서의 cin과 cout 함수는 iostream에 정의되어 있는 입/출력 객체를 통해 생성되고 해제되어 버퍼에서 데이터를 읽어온다. 여기에 추가로 stdio입출력과의 동기화 작업도 포함되어 기본적으로 stdio만 사용하는 것 보다 입출력 속도가 느리다는 것이다. 

그러면 속도를 빠르게하려면 동기화를 해제하거나, 그냥 C스타일 C++코드를 작성하면 된다.

게임과 같은 성능이 중요한 업계에서 많은 C++개발자들이 이런 C Like C++코드를 작성하고 계신것으로 알고 있다. 

입출력 동기화 해제 코드는 다음을 사용하면 된다. 하지만 동기화를 해제하기 때문에 stdio와 iostream을 병행하여 코드를 작성할 경우 두 버퍼가 독립적으로 작동하여 입/출력 순서를 보장할 수 없게 되기 때문에 그냥 동기화 해제하지 말고 둘중 하나만 쓰도록 하자.

// 입출력 동기화 해제 및 성능 최적화
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

이제 백준에 문제를 채점시켜보면 실행속도가 92ms로 줄어든 것을 볼 수 있다. 

최종적으로 완성된 코드는 다음과 같다. 

최소, 최대_10818_fix.cpp

/**
* 백준 1차원 배열 10818 최소, 최대
* 입력된 정수들의 최소, 최대값을 구하는 프로그램
* 두가지 방법이 존재한다.
* 모든 정수를 입력받은 이후 최소, 최대값을 연산할 것인지?->C풀이
* 입력받는 즉시 최소, 최대값을 비교하여 순회 횟수를 줄일 것인지?-> C++풀이
* <limits> 또는 <climits> 둘 중하나를 사용
*
* 제한사항
*****************************************
* 0 < N <= 1,000,000                    *
* -1,000,000 <= INPUT <= 1,000,000      *
*****************************************
*
*
*
* 주의
* 첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.
* 
* 풀이시간 5분
*/
#include <iostream>

using namespace std;

int main(void)
{

    // 입출력 동기화 해제 및 성능 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, MIN = 0x7fffffff, MAX = 0x80000000;

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        int INPUT;
        cin >> INPUT;
        if (INPUT < MIN)
        {
            MIN = INPUT;
        }
        if (INPUT > MAX)
        {
            MAX = INPUT;
        }
    }

    cout << MIN << " " << MAX << endl;
    return 0;
}

모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/알고리듬 풀이 at main · cyphen156/Workspace · GitHub

Workspace/알고리듬 풀이 at main · cyphen156/Workspace