<C 프로그래밍 #1-1> 순환으로 최대값 최소값 구하기

/* 잘못된 알고리즘의 예를 접한 후, 개선된 알고리즘을 접해보자. */

2017/06/10 - [C 언어] - : 순환을 이용한 프로그램

* 기존의 게시물 (바로 윗 줄 링크)의 순환 알고리즘 문제점 파악 및 개선

#1 최대값 최소값 구하기의 문제점

 기존의 게시물의 핵심 알고리즘은 이렇다. findMax() 함수와 findMin() 함수가 재귀적으로 정의되어 있다. 매개변수로 배열과 배열의 크기(n)을 받는다. 둘 중 더 큰 값을 반환하는 macro MAX와 MIN을 활용하여 순환적으로 비교를 하며 가장 큰 값을 찾아간다. 이 코드의 문제점을 파악할 수 있겠는가? 순환적인 개념을 아주 충실히 반영 했지만 이 코드는 아주 비효율적이다.

/*************************************************
 ** MAT program comments
*************************************************/

// 필요한 헤더파일은 포함되어 있다고 가정합니다.
// 기존의 알고리즘 입니다.

#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define MIN(x,y) ((x) < (y) ? (x) : (y))

int findMax(int arr[], int n)
{
	if (n == 1)
		return MAX(arr[n], arr[n - 1]);
	return MAX(arr[n], findMax(arr, n - 1));
}

int findMin(int arr[], int n)
{
	if (n == 1)
		return MIN(arr[n], arr[n - 1]);
	return MIN(arr[n], findMin(arr, n - 1));
}

/*************************************************
 ** End Line
*************************************************/

 그 이유는 MAX 매크로에 함수호출문 (findMax(arr, n - 1))이 인자로 넘어가게 되는데, 이 때 삼항연산자의 특성상 한 번 순환이 돌 때마다 함수가 2번 호출되는 문제가 발생한다.  MAX(x,y) ((x) > (y) ? (x) : (y))  위 매크로를 보면, x든 y든 2번 출현한다는 걸 알 수 있다. 결과는 옳게 나오지만, 비효율적이라는 걸 알 수 있을 것이다. 

 그렇다면 순환적인 개념을 유지하면서 어떻게 코드를 개선할 수 있을까? 그것은 바로 순환의 결과를 저장할 변수를 따로 두는 것이다. 이렇게 하면 위의 코드처럼 함수를 호출하는 횟수가 절반으로 줄어들어 코드의 효율이 높아진다. 잘 이해가 되지 않는다면 순환의 핵심개념인 '문제의 수를 점차 줄여간다'는 점을 생각해보자.

/*************************************************
 ** MAT program comments
*************************************************/

// 필요한 헤더파일은 포함되어 있다고 가정합니다.
// 개선된 알고리즘 입니다.

int findMax(int arr[], int n)
{
       if (n == 0)
              return arr[0];
       int max = findMax(arr, n - 1); // 순환을 수행하여 도출된 가장 큰 값을 변수 max에 담아둡니다.
       arr[n] = max < arr[n] ? arr[n] : max; // 현재 인덱스에 해당하는 값과 순환으로 도출된 max와 값을 비교하여 더 큰 값을 반환합니다.
       return arr[n];
}

int findMin(int arr[], int n)
{
       if (n == 0)
              return arr[0];
       int min = findMin(arr, n - 1); // 순환을 수행하여 도출된 가장 작은 값을 변수 min에 담아둡니다.
       arr[n] = min > arr[n] ? arr[n] : min; // 현재 인덱스에 해당하는 값과 순환으로 도출된 min와 값을 비교하여 더 작은 값을 반환합니다.
       return arr[n];
}

/*************************************************
 ** End Line
*************************************************/

 문제 수를 줄여간다는 개념을 밑에 좀 자세하게 풀어보았다. 처음에는 순환이 매우 어려웠지만, 관련된 문제들을 풀면서 그에 맞는 사고를 하고 개념을 적용하면서 점차 이해하게 됐다. 밑에 그림과 설명은 이 문제에 대해 순환적 사고를 하는데 도움을 줄 것이다.

 배열의 원소의 갯수가 n개 이므로 최대 인덱스는 [n-1]이라고 가정해보자. 순환의 개념은 이렇다. arr[n-1] 과 나머지 배열 중 가장 큰 값을 비교한다. 이제 문제의 수를 더 줄여보자. arr[n-2] 과 나머지 배열 중 가장 큰 값을 비교한다. 이런 작업이 반복되다 보면 결국 arr[1] 과 arr[0] 을 비교하게 되고 여기서 순환이 종료하게 된다.

 

 결국 순환의 끝에서 max에는 arr[0]과 arr[1] 중 큰 값이 저장하게 될 것이다. 그 다음으로는 max값과 arr[2]를 비교해서 더 큰 값이 max에 저장될 것이고 이런 작업이 반복되다 보면 max에는 이 배열에서 가장 큰 값이 저장이 된다.  '문제의 수를 점차 줄여간다'는 개념이란 대략 이런 것이다.

 다음 포스팅에서는 두 번째 최대값, 두 번째 최소값을 구하는 알고리즘에 대해서 알아볼 것이다. 마찬가지로, 주인장이 기존에 작성했던 알고리즘을 대폭 수정할 것이다. 기존 게시물의 코드는 너무 조잡하고 복잡해서 알아보기 힘들기 때문이다. 좀 더 깔끔하고 이해하기 쉽게 고쳐보자.

/* 여러분의 댓글과 방문은 저에게 힘이 됩니다. */