이번 강좌에서는

• 재귀 함수에 대한 이해

• 여러가지 주요 알고리즘. (버블 정렬, 유클리드 호제법, 에라토스테네스의 체)

안녕하세요 여러분. 이전 강좌의 예제가 중요한 만큼, 예제에 좀더 쉽게 접근할 수 있는 아이디어에 관해서 짧은 힌트 형식으로 강좌를 작성하도록 하겠습니다. 물론, 언제까지나 힌트일 뿐 완전한 코드는 여러분이 완성시켜야 합니다.

생각해볼 문제 1

사용자로 부터 5 명의 학생의 수학, 국어, 영어 점수를 입력 받아서평균이 가장 높은 사람 부터 평균이 가장 낮은 사람까지 정렬되어 출력하도록 하세요. 특히, 평균을 기준으로 평균 이상인 사람옆에는 '합격', 아닌 사람은 '불합격' 을 출력하게 해보세요.

일단, 여러분이 직면했을 가장 큰 문제는 '어떻게 정렬하는 프로그램' 을 만드느냐 이였겠습니다. 정렬을 하는 방법 (보통 알고리즘 이라 표현합니다) 에는 여러가지가 있습니다. 가장 직관적으로 이해하기 쉬운 것은버블 정렬(Bubble sorting) 이라 불리는 것인데 컴퓨터가 다음과 같은 규칙을 통해 작업을 합니다.

예를 들어 5, 1, 4, 2, 8 을 정렬한다고 합시다.

( 5 1 4 2 8 ) -> ( 1 5 4 2 8 )

버블 정렬 알고리즘은 처음 두 개의 원소를 비교해 왼쪽이 크면 자리를 바꿉니다. 이 경우, 5 가 1 보다 더 크기 때문에 1 과 5 의 자리를 바꾸었습니다.

( 1 5 4 2 8 ) -> ( 1 4 5 2 8 )

그 다음 두 원소를 비교합니다. 이번에도 5 가 더 크므로 4 와 자리를 바꿉니다.

( 1 4 5 2 8 ) -> ( 1 4 2 5 8 )

그 다음 두 원소 5,2 를 비교합니다. 이번에도 5 가 더 크므로 자리를 바꿉니다.

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )

그 다음 두 원소 5,8 를 비교합니다. 이번에는 오른쪽이 더 크므로 자리를 안바꿔도 됩니다. 끝 원소 까지 비교하였다면, 가장 큰 원소가 가장 오른쪽에 위치하게 됩니다. (왜 그런지는 잘 알겠지요?)

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )

이제 다시 처음부터 두 원소를 골라 비교합니다.

( 1 4 2 5 8 ) -> ( 1 2 4 5 8 )

위와 같은 작업들을 쭉 시행합니다.

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

마지막까지 비교하였다면 다시 처음으로 갑니다.

그렇다면 이를 언제까지 반복해야 할까요? 더이상 자리가 바뀌는 원소들이 없을 때 까지 해야 하겠죠?

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

위 작업을 완료하였다면, 컴퓨터는 더이상 자리가 바뀌는 원소들이 없다는 것을 알아채고 정렬을 그만하게 됩니다. 음, 역시 정확하게 1,2,4,5,8 로 정렬이 되었군요.

일단, 위 버블 정렬 알고리즘을 C 언어에서 구현하기 위해서 저는 여러분들이 다음과 같은 함수를 만들어주기를 원합니다.

Bubble_sort(int* arr, int num_elements), swap(int* pele)

Bubble_sort 함수는 말그대로 정렬을 하는 함수 입니다. 이 때, num_elements 로 arr 이 가리키는 배열의 원소 개수를 알아야 하겠죠? 그리고 swap 함수는 pele 가 가리키는 원소와 그 다음 원소를 서로 뒤바꿔주는 함수 입니다. 따라서 Bubble_sort 함수가 pele 함수를 호출해야 되겠죠?

사실 버블 정렬은 매우 비효율적인 정렬 알고리즘 입니다. 하지만 구현하가 매우 단순하여 정렬해야 될 것이 작은 경우에는 이를 자주 이용하게 되지요. 정렬 알고리즘에 대해 궁금하신 분들은 여기를 클릭해서 정렬 알고리즘의 세상에 빠져보세요.

생각해볼 문제 2

유클리도 호제법을 이용해서 N 개의 수들의 최대공약수를 구하는 함수를 만들어보세요. 유클리드 호제법이 무엇인지 모르신다면, 인터넷 검색을 활용하는것을 추천합니다. (댓글을 달아도 돼요)

유클리드 호제법은 어떠한 두 수의 최대공약수를 계산하는데 쓰이는 방법입니다. 방법 자체는 간단합니다.

1. 두 수를 m 과 n 이라 하자. (m > n)

2. m 을 n 으로 나눈 나머지를 계산한다. (m % n)

3. m % n 이 0 이라면 n 값이 맨 처음 두 수의 최대공약수이다. (종료)

4. m % n 이 0 이 아니였다면, m % n 과 n 중 큰 것을 m, 작은 것을 n 이라 한 후 ① 로 돌아간다.

예를 들어서 63 와 35 의 최대공약수를 구한다고 합시다. 그렇다면 유클리드 호제법을 이용하면 아래와 같은 과정을 거칩니다.

1. m = 63, n = 35

2. 63 % 35 = 28

3. 28 이 0 이 아니므로, 28 과 35 를 비교한느데 35 가 크므로 m = 35, n = 28

4. m = 35, n = 28

5. 35 % 28 = 7

6. 7 이 0 이 아니므로, 7 과 28 을 비교, 28 이 크므로 m = 28, n = 7

7. m = 28, n = 7

8. 28 % 7 = 0

9. 0 이므로, n 값 ( 7 ) 이 맨 처음 두 수의 최대공약수. 즉, 63 과 35 의 최대공약수는 7 이다

사실, 왜 위 과정을 거치면 두 수의 최대공약수가 나오는지에 대한 증명은 간단합니다. 수학적 지식이 없다면 이해가 안갈 수 도 있지만,

$m = qn + r, (0 \le r < q), \text{gcd}(m, n) = \text{gcd}(qn + r, n) = \text{gcd}(r, n)$

때문에 그렇습니다. 유클리드 호제법은 두 개의 수의 최대공약수를 찾는데에만 사용하였지만 이를 어떻게 N 개의 수의 공통된 최대공약수를 찾는데 응용할 수 있을까요? 답은 간단합니다. 처음 두 수의 최대 공약수를 구합시다. 그리고, 그 다음수와 구한 최대공약수의 최대 공약수를 계산합니다. 그리고 이를 쭈우욱 반복합니다.

예를 들어서 18, 24, 40, 60 의 최대공약수를 구한다고 해봅시다. 18 과 24 의 최대공약수는 6 입니다. 그러면 이제 6 과 40 의 최대공약수를 계산합니다. 이는 2 입니다. 그러면 이제 2 와 60 의 최대공약수를 계산합니다. 이는 2 입니다. 따라서, 이 4 개의 수의 공통된 최대공약수는 2 가 됩니다.

여기에도 수학적 원리가 있지만 간단하기 때문에 넘어가도록 하겠습니다. 여러분이 생각해보세요~

생각해볼 문제 4

자기 자신을 호출하는 함수를 이용해서 1 부터 특정한 수까지의 곱을 구하는 프로그램을 만들어보세요.

여러분은 '자기 자신을 호출한다' 에 대해서 많은 고민을 많이 하셨을 것입니다. 일단, 아래의 코드를 직접 컴파일 후 실행해보세요

#include <stdio.h>
int recursive(int n) {
  printf("난 인자가 %d 에요! \n", n);
  if (n <= 0) return 0;

  recursive(0);
}
int main() {
  recursive(3);
  return 0;
}

성공적으로 컴파일 했다면

실행 결과

난 인자가 3 에요! 
난 인자가 0 에요! 

흠. 어느 정도 예측 가능했던 결과입니다. 그렇다면, 아래의 코드는 어떨까요?

#include <stdio.h>
int recursive(int n) {
  printf("난 인자가 %d 에요! \n", n);
  if (n <= 0) return 0;

  recursive(n - 1);

  return 0;
}
int main() {
  recursive(3);
  return 0;
}

성공적으로 컴파일 했다면

실행 결과

난 인자가 3 에요! 
난 인자가 2 에요! 
난 인자가 1 에요! 
난 인자가 0 에요! 

일단, 컴퓨터 상에서 위 코드는 아래의 순서로 실행됩니다.

1. main 함수에서 recursive(3) 을 호출함

2. recursive 에서 n = 3 '난 인자가 3 이에요' 를 출력

3. n 이 0 이하가 아니므로 넘어감

4. recursive(n-1) 즉 recursive(2) 를 호출

5. recursive 에서 n = 2 '난 ~ 2 ~ ' 를 출력 (~ 는 생략)

6. n 이 0 이하가 아니므로 넘어감

7. recursive(n-1) 즉 recursive(1) 을 호출

8. recursive 에서 n = 1, ' ~ 1 ~ ' 를 출력

9. n 이 0 이하가 아니므로 넘어감

10. recursive(n-1) 즉 recursive(0) 을 호출

11. recursisve 에서 n = 0, '~ 0 ~' 을 출력

12. n 이 0 이하이므로 return 0;

13. n = 1 이였던 recursive 에서 return 0;

14. n = 2 이였던 recursive 에서 return 0;

15. n = 3 이였던 recursive 에서 return 0;

16. main 함수로 돌아감.

사실, 위 작업이 이해가 잘 안되는 수도 있습니다만.. 나중에 변수의 정의 범위에 대해 배우게 된다면 좀더 쉽게 이해할 수 있으실 것입니다. 아무튼 위 사실을 활용해서 1 부터 n 까지 곱하는 재귀 함수를 만들어보세요 (위와 같이 자기 자신을 호출하는 함수를 재귀함수, 영어로 recursive function 이라 합니다.)

생각해볼 문제 4

계산기를 만들어보세요. 사용자가 1 을 누르면 +, 2 를 누르면 - 와 같은 방식으로 해서 만들면 됩니다. 물론 이전의 계산 결과는 계속 누적되어야 하고, 지우기 기능도 있어야 합니다. (물론하나의 함수에 구현하는 것이 아니라 여러개의 함수로 분할해서 만들어야겠죠?)

이 문제는 그다지 어려운 아이디어 같은 것이 필요한 것이 아니므로 생략하도록 하겠습니다. 사실, 난이도는 중하 정도 됩니다.

생각해볼 문제 5

N 진법에서 M 진법으로 변환하는 프로그램을 만들어보세요. (난이도 : 中)

사실 이 문제는 잘못낸 문제입니다. 물론 아이디어는 충분히 구현할 수 있지만 여러분은 아직 '문자열'에 대한 개념이 없기 때문에 정확하게 구현할 수 는 없지만 생각 정도는 할 수 있습니다. 일단 위 프로그램을 어떻게 만들 것인지에 대해 생각해 놓은 것을 보세요. 나중에 필요한 개념을 다 배우고 나면 하실 수 있을 것입니다. (참고적으로 문제에 조건 하나가 빠졌는데 N,M 은 모두 36 이하 입니다. 왜냐하면 숫자를 이용시 0,1,...,9,A,B,.. 로 사용하는데 알파벳이 26 개이므로 총 36 진수 까지 나타낼 수 있거든요)

• 사용자로 부터 무슨 진법에서 무슨 진법으로 변환할 지 입력받습니다. (N,M 입력)

• N 진법의 수를 입력받습니다.

• 그 수를 각 자리로 분해해 int 배열에 값을 넣습니다. 이 때, 값은 십진수로 넣습니다. 예를 들어서 16 진법으로 7AE 를 입력받았다면 digit[0] = 14, digit[1] = 10, digit[2] = 7 로 넣으면 됩니다. 참고로, 올바르지 않은 숫자가 사용되면 종료합니다. (예를 들어서 2 진법인데 3 이란 숫자를 사용함)

• 이 수를 십진수로 변환합니다. (NtoDec 함수 제작 요망)

• 이 십진수를 다시 M 진법의 수로 변환합니다. (DectoM 함수 제작 요망)

물론, 이 문제는 꼭 안푸셔도 됩니다. 나중에 개념을 좀더 배우다 보면 풀 수 있는 스킬들을 습득하실 것입니다.

생각해볼 문제 6

에라토스테네스의 체를 이용해서 1 부터 N 까지의 소수를 구하는 프로그램을 만들어보세요. (난이도 : 中)

에라토스테네스의 체.. 이름이 참 어렵군요. 사실 이는 간단합니다. 말그대로 숫자들만 걸러내는 체(sieve) 인데, 아래와 같은 방식으로 숫자를 걸러내어 소수들을 찾습니다.

• 수들을 쭉 쓴다.

• 2 의 배수들을 다 지운다.

• 2 에서 가장 가까운 안지워진 수를 찾는다. 아마도 3 일 것이다. (소수 찾았다!)

• 3 의 배수들을 다 지운다.

• 3 에서 가장 가까운 안지워진 수를 찾는다. 아마도 5 일 것이다. (소수 찾았다!)

• 5 의 배수들을 다 지운다.

• 5 에서 가장 가까운 안지워진 수를 찾는다. 아마도 7 일 것이다. (소수 찾았다!)

• 7 의 배수들을 다 지운다.

• 그 뒤로 쭈우욱 같은 작업을 실시

위키피디아에서 이 과정을 알기 싶게 애니메이션으로 나타낸 자료가 있으니 보시기 바랍니다.

생각해볼 문제 7

1000 자리의 수들의 덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 프로그램을 만들어보세요. 나눗셈의 경우 소수 부분을잘라버리세요. 물론, 소수 부도 1000 자리로 구현해도 됩니다. 1000 자리 수들의 연산 수행 시간은 1 초 미만이여야합니다. (난이도 : 上)

int 자료형은 대략 42 억, 그러니까 10 자리 정도의 수 밖에 사용할 수 없었습니다. 그런데 문제에서 요구하는 것은 무려 1000 자리나! 이걸 도대체 어떻게 하라는 말일까요. 사실, 간단합니다. 크기가 1000 인 char 배열을 만들어서 배열의 한 원소를 수의 한 자리라고 생각하면 되죠. 이게 도대체 무슨 말이냐고요?

예를 들어서 char BigNum[1000]; 을 정의하였다고 할 때, 사용자가 만일 123456 을 입력하였다면 BigNum[999] = 6, BigNum[998] = 5, ... BigNum[994] = 1 로 하면 되죠. 이러한 형식의 두 수를 더하는 연산을 하기 위해서는 각 원소를 더한 뒤, 받아올림이 있으면 그 다음 원소에 더해주고 하는 방식으로 쭉 나가면 됩니다. 어때요? 간단하죠.

곱셈은 쉽게 하면 덧셈을 여러번 반복해서 호출하는 것으로 해결될 수 있지만 연산 속도가 느리므로 인간이 곱셈하는 방식으로 하는 것을 권합니다. 그렇다면 문제는 나눗셈인데 나눗셈 역시 뺄셈을 반복하는 것으로 해결 될 수 있지만 역시 느리므로, 인간이 나눗셈 하는 방식으로 계산하는 함수를 만들어보세요. 그럼. 행운을 빕니다.