올림피아드 기출문제로 배우는 C언어 - 프로그램 읽기1

프로그램 소스를 대하는 학생들의 입장에서는 올림피아드 문제들이 무슨 수수께기 푸는 놀이도 아니고 머리만 아픈 이 일을 굳이 왜 해야할까? 하는 사람들이 있을지도 모르겠습니다. 그렇지만 "프로그램 읽기(Reading source code)"는 프로그래머(개발자)에게는 숙명과 같은 일 입니다. 그렇지만 개발자의 생리 자체가 자신이 구상한 것을 프로그램 코드로 일단 작성하고 나면 다시 보려하지 않는 특성이 있습니다. 프로그램을 읽는 경우는 버그를 찾아야 하거나 다른 사람이 작성한 것을 수정해야 하는 경우, 또는 조직에 프로그램 리뷰 프로세스가 있는 경우 리뷰할 목적으로 읽는 정도입니다. 

그러나, 프로그래밍 기술을 성장시키는 가장 좋은 방법 중에 하나는 잘 작성된 프로그램을 읽는 것입니다. 예를 들면 가장 널리 사용하는 웹서버인 아파치의 코드를 읽으면 가장 안정적인 서비스 대몬을 작성하는 기술을 익힐 수 있을 것이고, 오픈 소스 DBMS인 MySQL의 SQL 분석 과정을 읽으면 효율적인 SQL 질의에 대해서 자연스럽게 배우게 되는 것과 같습니다. 정보 올림피아드의 프로그램 읽기도 C언어 익히기과 다양한 알고리즘을 배우는데 매우 유용합니다.  이번 문제들은 아주 복잡하지는 않지만 C언어의 기본기를 다질 수 있는 것들입니다.

34. 다음 프로그램의 출력 결과는 무엇인가?
    int A[5] = {1, 3, 4, 7, 8};
    int B[5] = {2, 5, 6, 8, 9};
    int i = 0, j = 0;
    
    while (i < 5 || j < 5) {
        if (j >= 5 || (i < 5 && A[i] < B[j]))
            printf("%d", A[i++]);
        else
            printf("%d", B[j++]);
    }
    printf("\n");
① 123456789 ② 1347825689 ③ 2568913478 ④ 1235467889 ⑤ 1234567889

이 문제는 C언어의 논리 연산, 증감 연산자, 배열 참조를 다뤄 볼 수 있는 문제입니다. 메인 루프는 while문으로 변수 i, j 가 모두 5이상일때 루프가 끝남을 기억해야 합니다. 메인 루프를 파악했으면 그 다음으로는 주요 비교 조건을 파악해야 하는데 비교 조건을 정리해 보면 A배열 값과 B배열 값을 차례로 비교하면서 A배열 값이 작으면 A배열 값을 B배열 값이 작거나 같으면 B배열 값을 출력합니다. 값을 출력한 다음에는 해당 배열의 인덱스를 증가(++)시킵니다. 만약에 한쪽 배열을 모두 출력 했으면 다른쪽 배열을 차례대로 출력합니다. 이 로직은 오름차순으로 정렬된 두 배열을 병합(Merge)하는 알고리즘으로 두 배열을 병합하여 하나의 오름차순 출력을 나타내는 것을 찾으면 되므로 정답은 5번입니다. 

C언어의 논리 연산자는 !(NOT), &&(AND), ||(OR)로 비트 연산자인 ~(Not), &(And), |(Or), ^(Xor)와 구별할 수 있어야 합니다. 논리 연산자는 연산자 사이에서도 우선 순위가 가장 낮은 분류에 속하기 때문에 연산식이 모두 수행된 결과가 0(False)인지 0이 아닌지(True) 만을 최종적으로 판단해서  !(NOT) 참/거짓을 바꾸고, &&(AND)는 양쪽이 모두 참일때만 참, ||(OR)는 한쪽만 참이어도 참으로 결과를 도출합니다. 그래서 1 && 2의 값은 논리 AND 이므로 양쪽 모두 참이므로 결과는 1입니다. 비트 연산인 1 & 2의 경우에는 각 비트 단위에서 양쪽이 모두 1일때만 1인데 1과 2는 일치하는 비트가 없으므로 결과는 0입니다. 논리 NOT의 경우에도 !1은 참을 뒤집기 하는 것이므로 결과는 거짓인 0이지만, 비트 NOT인 ~1는 00000000 00000001을 비트 단위로 뒤집는 것이므로 11111111 11111110이 되어 결과는 -2입니다. 

위의 문제처럼 여러 조건이 섞여 있으면 NOT>AND>OR의 우선순위로 처리하므로 위의 문제에서 "(i < 5 && A[i] < B[j])" 처럼 괄호로 묶지 않아도 &&(AND) 부터 수행하지만 괄호로 묶어주어 프로그램을 읽을때 헷갈리지 않도록 배려하기도 합니다.  복잡한 조건을 해석하거나 기술하는 과정에서 도움이 될만한 팁은 복잡한 논리 연산문을 드모르간의 법칙을 사용해서 뒤집어 보는 것입니다. 예를 들어 "if (j >= 5 || (i < 5 && A[i] < B[j]))" 문장 전체 뒤집으면 부등호를 반대로 바꾸고 AND는 OR, OR는 AND로 바꾸면 "if (j < 5 && (i >= 5 || A[i] >= B[j]))" 처럼 사용할 수 있습니다.

35. 다음 프로그램의 출력 결과는 무엇인가?
    int g(int x) {
        if (x < 10) return x;
        else return g(x / 10) + (x % 10);
    }
    
    int main() {
        int i, s = 0;
        
        for (i = 1; i <= 100; i++) s += g(i);
        printf("%d\n", s);
        return 0;
    }
① 899 ② 900 ③ 901 ④ 902 ⑤ 903

위의 문제는 재귀 함수(Recursive function)를 이해하고 수열의 합("올림피아드 기출문제로 배우는 C언어 - 수열의 합" 참조) 공식을 활용하면 시간을 절약할 수 있습니다. 메인 루프는 1부터 100까지 g()함수를 호출하는 for문이지만 for문은 단순 합산이므로 분석의 핵심은 10이상일때 스스로를 재귀 호출하는 g(int x) 함수입니다.  파라미터 x 값에 따른 함수 g()의 리턴값을 주요 포인트를 기준으로 계산하면 아래와 같습니다.

•  1 ~ 10 :  1~ 9,  1
• 11 ~ 20 : 2 ~ 10, 2
• 21 ~ 30 : 3 ~ 11, 3
• ......
• 81 ~ 90 : 9 ~ 17, 9
• 91 ~ 100 : 10 ~ 18, 1

잘 관찰해 보면 g(x) 함수는 파라미터 x로 전달된 값 x의 숫자를 더하는 함수 역할을 합니다. 예를 들면 34는 3+4=7로 2345는 2+3+4+5=14의 결과를 냅니다. 실제로 이런 함수는 큰 범위의 키 값을 좁은 범위로 수렴시키면서도 적절하게 분산시키는 해시 함수(Hash function)로 활용할 수 있습니다. 해시 함수도 좋고 특정 값의 숫자들의 합을 구하는 함수도 좋지만 문제는 합계를 내는 것인데, 저의 경우 아직까지 이런 값을 한번에 구하는 공식은 찾지 못했습니다. 할수 있는 것은 위에서 분석된 규칙성과 등차수열의 합 공식을 사용하는 것인데 아래와 같이 공식화 할 수 있겠습니다.

항간의 간격이 1일때 등차수열의 합을

를 통해서 각각의 합계를 구할수도 있지만 위의 공식을 보면 각 항마다 9씩 증가하는 것을 확인할 수 있습니다. 첫 항인 1~9까지의 합산인 

를 첫항으로 해서  공차 d는 9, 항의 개수 n은 10 첫항 a에 45를 대입하면 

인데 1~9합산이 하나 더있고 +1을 감안하면 정답은 901입니다. 관찰과 응용이 이번 문제를 푸는 키가 될것 같네요.

36. 다음 프로그램의 출력 결과는 무엇인가?
    int a = 2, b = 4;
    while (a + b < 110) {
        int c = b + a;
        a = b;
        b = c;
    }
    printf("%d %d\n", a, b);
① 42 68 ② 68 110 ③ 110 178 ④ 32 64 ⑤ 64 128

이런 문제를 대하는 첫 자세는 펜을 들고 메모하면서 루프를 따라 도는 것입니다. 3회 정도 루프를 따라 돌면서 각 변수의 변화를 관찰합니다.

• a, b, c

• 2, 4, __

• 4, 6, 6

• 6, 10, 10

a, b변수의 변화를 살펴보면 현재항은 n-1항 + n-2항으로 생성되는 수열을 만들어 냅니다. 결과적으로 2, 4, 6, 10, 16, 26, 42, 68, 110 ...과 같은 수열이 만들어 지는데 while 루프의 수행 조건이 두변수의 합이 110 작을때까지 이므로 a, b가 각각 42, 68일때 루프가 종료되므로 정답은 1번입니다.

37. 다음 프로그램은 두 자연수 a, b의 최대공약수를 구하는 함수이다. 빈 칸에 들어갈 코드는 무엇인가?
    int gcd(int a, int b) {
        if (b == 0) return a;
        return ___________;
    }
① gcd(b % a, a) ② gcd(a / b, b)
③ gcd(a % b, b) ④ gcd(b, a / b)
⑤ gcd(b, a % b)

이번 문제는 최대공약수를 구하는 기본 이론을 알면 쉽게 풀수 있는 문제입니다. 두수의 최대공약수를 구하는 방법은 소인수 분해를 통한 방법과 유클리드 호제법이 있는데 37번 문제는 유클리드 호제법을 C의 재귀 함수를 통해 구현한 것입니다. a와 b의 최대공약수를 유클리드 호제법로 구하는 방법은 a를 b로 나눈 나머지가 0이 될때까지 나머지가 0이 아니면 a에 b값을 넣고 b에는 나머지를 반영해서 나머지가 0인지를 검사합니다. 나머지가 0이면 그 시점의 b를 최대공약수로 인식하는 것입니다. 

위의 문제는 재귀 호출을 이용하고 나머지 확인에 b를 사용하므로 a를 b로 나눈 나머지를 파라미터 b로넘기는 보기는 5번이 유일합니다. 그리고 5번 보기는 나머지가 0이 아닐때 b의 값을 파라미터 a위치에 전달하여 자연스럽게 나머지가 다음 스텝에서 나누는 대상이 되도록 합니다. 이런 알고리즘은 자주 대하는 방법이 왕도입니다.