올림피아드 기출문제로 배우는 C언어 - 알고리즘 찾기

프로그램을 많이 개발해본 경험자라면 정보 올림피아드의 프로그램 분석 문제가 그리 낯설지 않겠지만, 개발을 많이 하지 않은 사람이라도 다양한 알고리즘에 대한 잦은 경험은 나도 모르게 프로그래밍 실력을 향상 시킬 수 있는 좋은 기회가 됩니다. 알고리즘(Algorithm)은 단순히 "계산법"으로 정리할 수도 있지만 사전에서는 "어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법"으로 정의하고 있습니다. 알고리즘에는 입력이 있고 검증 가능한 처리 과정과 출력이 있는데 정보 올림피아드의 여러 문제들은 이러한 알고리즘의 검증 과정이라고 이해해도 크게 무리가 되지 않을것 같습니다.

이러한 프로그램 분석 과정은 보다 효율적인 프로그램을 구현하는 밑바탕이 될 것입니다. 입출력이 작고 외부 연관성이 작은 프로그램이라면 알고리즘의 효율성이 프로그램 수행 결과에 미치는 영향이 적겠지만 데이터가 많아지고 외부 연관성이 커지면 알고리즘의 효율성은 프로그램 수행 결과에 카다란 차이를 주게 됩니다. 어찌했든 다양한 알고리즘을 많이 경험해 보고 문제 해결 과정에 다양한 알고리즘을 적용해 보는 것이 "분석력"을 키우는 정도입니다. 지름길은 없습니다. 

29. 다음 프로그램의 출력 결과는 무엇인가?
    int arr[10] = {0, 1, 1, 1, 0, 0, 1, 1, 1, 1};
    int cnt = 0, i = 0;
    for (i = 1; i < 10; i++) {
        if (arr[i] == arr[i - 1]) {
            cnt = cnt + 1;
        } else {
            cnt = cnt - 1;
        }
    }
    printf("%d\n", cnt);

① 1 ② 2 ③ 3 ④ 4 ⑤ 5

프로그램 분석 과정에서는 아주 사소한 것을 놓치면 엄청난 시간을 버리는 미궁으로 빠져 버리기도 합니다. 코드를 보고 한두 문장으로 명확하게 정의하는 과정이 필요합니다. 위의 문제의 경우에는 "배열의 두번째 원소부터 마지막 원소까지 차례로 방문하면서 직전 원소와 현재 원소의 값이 같으면 +1 카운트, 다르면 -1 카운트 한다"와 같은 식으로 정리할 수 있으면 좋습니다. 

    -1  0  1  0  1  0  1  2  3
{0,  1, 1, 1, 0, 0, 1, 1, 1, 1};

알고리즘이 명확해 졌으면 펜을 들고 위와 같이 배열을 따라가 보면 답은 3입니다. 이러한 연속성 확인 알고리즘은 압축 알고리즘과 연관성이 있을 수도 있습니다. 연속성이 높을 수록 압축율이 높은 압축 알고리즘을 적용할 수 있으니까요.

30. 다음 프로그램의 출력 결과는 무엇인가?
    int i, b = 0, c = 0;
    int a[7] = {-3, -5, -6, -2, -1, -9, -4};
    for (i = 0; i < 7; i++) {
        if (b > a[i]) {
            b = a[i];
        }
        if (c < a[i]) {
            c = a[i];
        }
    }
    printf("%d\n", c - b);
① 7 ② 8 ③ 9 ④ 10 ⑤ 0

위의 문제는 최소값(MIN), 최대값(MAX)을 구하는데 많이 사용하는 알고리즘입니다. 최소값, 최대값으로 추출할 변수에 초기값을 설정하고 해당 값보다 작거나 크면 최소값, 최대값을 변경하는 방식입니다. 그런데, 위의 문제에는 함정이 있습니다. 로직을 보면 각 원소의 값이 b보다 작으면 b를 원소의 값으로 바꾸고 각 원소의 값이 c보다 크다 c를 바꾸므로 로직만 생각하면 b로 최소값을 추출하고 c로 최대값을 추출하는 것처럼 보이지만 b,c 변수가 모두 0으로 초기화 했다는 것에 주의해야 합니다. 배열에는 0보다 큰 값이 없으므로 c는 0 그대로 있고, b는 가장 작은 값인 -9가 저장되어  0 - -9 = 9입니다.  "배열의 최소값, 최대값 추출"이라는 알고리즘으로 위의 코드를 수정한다면 "b = a[0]; c=a[0];"로 초기값을 설정하고 for문을 두번째 원소부터 수행하도록 하면 정확한 결과를 도출할 수 있습니다.

31. 다음 프로그램의 출력 결과는 무엇인가?
    int a = 1, b = 0, n = 10;
    while (n--) {
        int c = b - a;
        a = b;
        b = c;
    }
    printf("%d\n", a + b);
① -2 ② -1 ③ 0 ④ 1 ⑤ 2

while문이 수행되는 조건은 괄호안의 표현식이 참(True)일 동안인데 C언어에서는 0이 아닌 값은 모두 참이라는 것은 이미 언급한 바가 있습니다("올림피아드 기출문제로 배우는 C언어 - 기본문장" 참조) 고로 n이 10부터 1씩 감소되어 값이 1일때까지 수행하다가 0이면 루프를 빠집니다. 로직은 단순해서 a는 이전 스텝의 b값이 오고 b에는 이전 스텝의 b - a 값을 저장합니다. 이전 스텝의 연산을 위해서 임시 변수 c가 사용됩니다. 

 a  b
 1  0
 0 -1
-1 -1
-1  0
 0  1
 1  1
 1  0
 0 -1
-1 -1
-1  0
 0  1

위의 과정은 변수 a, b가 변하는 과정으로 최종적인 a, b의 값은 0, 1이고 1 - 0 =1 정답은 1입니다. 이런 알고리즘은 지그재그 식으로 로드를 분배하거나 데이터량을 균일하게 배분하는 용도등에 간단하게 할용할 수 있습니다. 1 0 -1 -1 0 1 배열을 무한 반복 시킬 수 있습니다. a 가 1 0 -1 -1 0 1 배열이 반복될때 b는 한 스텝 앞서서 1 0 -1 -1 0 1 배열이 반복되는 알고리즘이므로 쭉 배열하고 루프시점에 맞게 값을 구하는 것도 문제를 간편하게 푸는 방법일 수 있습니다.