최댓값 최솟값 구하기

여러 수가 주어질 때 그 수의 최댓값 및 최솟값을 구하는 알고리즘이다.

 

        

예)  입력 : 5

       1 2 3 4 5 

   

       출력 : 1 5

범위는

 

입력 할 수 있는 개수

1 <= n <= 1000000

그 수의 값의 범위

-1000000 <= num <= 1000000

이라고 가정한다.

<Case 1>

#include <stdio.h>
 
int main() 
{
    int N;
    int max = 0, min = 0, temp = 0;
    int i;
 
    scanf("%d",&N);
    scanf("%d",&temp);
 
    max = min = temp;
 
    for (i = 0; i < N - 1; i++)
    {
        scanf("%d",&temp);
 
        if (temp > max)
            max = temp;
        else if (temp < min)
            min = temp;    
    }
    printf("%d %d",min,max);
 
 return 0;
 
}

<Case 2>

#include <stdio.h>
 
 int a[2000002] = {0,}; // -1000000 ~ 1000000 값 대입을 위한 배열
 
int main()
{   
 int i,n,num;
 
 scanf("%d", &n);
 
 for(i = 0 ; i < n ; i ++)
 {
  scanf("%d", &num);
  a[num+1000000] = num; // -값들을 배열에 넣을 수 없으니 -1000000을 0으로 본다.
 }
 
 
 for(i = 0; i <= 2000000; i ++)
 {
  if(a[i] != 0) // 즉, 처음 배열에 null값이 아닌 수가 나오는 것이 최솟값
  {
   printf("%d ",a[i]); // 만약 -1000000이 최솟값이면 a[0]에 있을 것이고 a[0]를 출력하면 -1000000이 나온다.
   break; // 탈출
  }
 }
 
 for(i = 2000000 ; i >= 0 ; i--) // 위와 반대로 시행(최댓값 찾기)
 {
  if(a[i] != 0)
  {
   printf("%d",a[i]);
   break;    
  }     
 }
    return 0;
}
 

case 1과 case 2의 차이는 무엇일까?

시간 복잡도와 공간 복잡도의 차이이다.

case 1은 확실히 메모리 사용량이 적다는 것을 시각적으로 확인이 가능하다.

하지만, 최악의 경우 100만개의 수를 다 입력하면

O(n)은 1000000이 될 것이다.

아래의 경우는 어떠한가?

case 2는 공간적인 낭비가 심하다. 즉 공간 복잡도가 크다.

하지만 시간 복잡도를 따져본다면

최악의 경우

100만개의 수를 입력 받으면 a[1000000] = -1000000,  a[1000001] = 1000000이 온다면

O(n) = 2000000이 될 것이다.

하지만, 상황에 따라 Case 1보다 Case 2가 시간복잡도에서 유리한 경우들이 많이 있다.

ex ) 입력받은 값이 1 2 3 4 5면

case 1 O(n) = 5

case 2 O(n) = 2

즉, 상황에 따라 어느 알고리즘을 쓰는 것은 코더의 코드에 달려있다.

하지만 보편적으로 본다면 case 1의 코드가 좋은 것은 자명한듯 하다.