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

조금 큰 규모의 프로그램 읽기는 올림피아드 문제를 푸는 것과는 조금 다른 양상을 띄게 됩니다.  올림피아드 문제를 푸는 과정은 코드도 길지 않기 때문에 메인 루프를 찾고 코드의 동작 방식을 파악하면 어렵지 않게 코드의 동작 결과나 의도하는 바를 예측할 수 있습니다. 그러나, 실제 현장에서 사용하는 조금 큰 규모의 프로그램을 읽기 위해서는 해당 코드를 빌드(Build)하여 완성된 프로그램으로 실행되는지 확인할 필요가 있고 구체적인 세부 기능들을 동작시켜서 실제로 접해보는 것이  선행되어야만 합니다. 

프로그램을 동작시켜서 기능들이 실제로 어떻게 동작하는지 맛보았다면 코드를 읽는 과정에서 알고리즘의 작성 배경과 실행 결과를 예측할 수 있기 때문에 좀더 명확한 프로그램 읽기에 도움이 될 수 있습니다. 큰 규모의 프로그램 읽기도 시작점(Entry Point) 찾기, 메인 루프 찾기, 분기점 정리등 올림피아드 문제 풀기와 크게 다르지 않습니다. 순서도 그리기 처럼 그림으로 표현할 수 있다면 코드 분석을 좀더 효과적으로 수행할 수 있을 것입니다. 올림피아드 문제 풀기와는 다르게 실제 현장에서는 통합 개발 환경(IDE)이나 디버거와 같은 도구를 활용하면 보다 쉽게 코드를 분석할 수 있습니다. 디버거(Debugger)를 통해서 한 스텝, 한 스텝 코드를 실제 실행 과정을 따라 갈 수 있수 있으며 현재 시점까지의 함수 호출 과정을 콜스택(Call Stack)을 통해서 확인할수 도 있습니다. 소스 코드 차원에서 함수나 변수가 정의된 곳으로 간편하게 이동할 수도 있고 현재 함수를 호출하고 있는 모든 코드를 찾을 수도 있습니다.

43. 다음 프로그램의 출력 결과로 출력되지 않는 숫자는 무엇인가?
    int a[3][3] = {1, 2, 3, 1, 3, 2, 0, 1, 2},
    b[3][3] = {1, 3, 2, 0, 1, 1, 2, 3, 1};
    int main() {
        int k, i, j;
        for (k = 0; k < 3; k++) {
            for (i = 0; i < 3; i++) {
                int s = 0;
                for (j = 0; j < 3; j++) s += a[k][j] * b[j][i];
                printf("%d\n", s);
            }
        }
    }
① 3 ② 2 ③ 5 ④ 7 ⑤ 14

43번 문제에서 짚고 넘어갈 기본적인 C언어 문법은 배열 초기화에 관련한 사항과 배열 인덱싱과 연관된 사항입니다. 문제에서의 a[3][3], b[3][3]는 정수형 2차원 배열로 1차원 배열 a[9], b[9]로 배열을 선언한 것과 내용이 다르지 않습니다. 초기화 문장도 {{1, 2, 3}, {1, 3, 2}, {0, 1, 2}}로 하는 것이 명확하겠지만 문제처럼 쭉 기술해도 무방합니다. 

메인 루프는 인덱스 k, i로 3*3으로 총 9회 값을 출력합니다. 출력하는 값은 배열 a, b를 곱한 결과를 합산한 값입니다. 이런 루프는 2~3회 값을 따라 메모하면서 추적할 필요가 있습니다. 첫 출력은 a[0][0] * b[0][0]+a[0][1] * b[1][0]+a[0][2] * b[2][0]으로 1*1 + 2*0 + 3*2 = 7입니다. 두번째 루프는 k=0, i=1이므로 a배열에 대한 참조는 동일하고 b배열 참조만 두번째 항목으로 바뀌어 1*3 + 2*1 + 3*3 = 14입니다. 이제 루프의 동작 방식이 명확해졌으므로 나머지 과정도 풀어보면 7, 14, 5, 12, 4, 3 등의 숫자가 출력되고 2는 출력되지 않습니다. 정답은 2번 입니다.

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

프로그램은 배열 a에 초기값을 설정하고 while 루프를 통해서 배열에 대한 조정 작업을 거친후 배열 a의 내용을 출력하는 구조입니다. 메인 루프는 while문은 변수 h를 기반으로 9, 3, 1로 for문은 h부터 9까지이므로 9~9, 3~9, 1~9로 루프를 운행합니다. j변수를 기반으로한 for 루프는 기준 항목을 임시 변수(temp)에 넣고 뒤에서 앞으로 기준 항목보다 큰 값들을 이동시키고 작거나 같은 값을 찾아 기준항목을 정렬 위치에 삽입하는 방식으로 삽입 정렬(Insertion Sort)을 수행하는 로직입니다. h값이 1일때는 삽입 정렬 로직과 다르지 않습니다. 그런데  j변수를 기반으로한 for 루프의 간격이 9와 3일때는 정렬 대상이 해당 간격으로만 한정되기 때문에 전체적으로는 완전하지 않은 정렬이지만 최종 스텝인 j가 1일때는 정렬 대상이 어느 정도 정렬되어 있는 상태가 되어 삽입 정렬의 효율성을 높일 수 있습니다. 이런 정렬 알고리즘을 쉘 소트(Shell Sort)라 합니다. 큰 값을 뒤로 보내고 있으므로 최종 결과는 배열이 오름차순으로 정렬된 1번입니다. 소트 알고리즘은 정보올림피아드의 단골 메뉴입니다. 소트의 종류와 구현 알고리즘을 꼭 살펴보시길 권합니다."정렬(Sort)의 개념과 기법 - 정보올림피아드 문제풀이"참조.

47. 다음 프로그램의 출력 결과는 무엇인가?
    int i, j, tot = 0, a[21] = {1, };
    for (i = 2; i <= 20; i++) {
        if (a[i]) continue;
        for (j = i; j <= 20; j += i) a[j] += j / i;
    }
    for (i = 0; i <= 20; i++) tot += a[i];
    printf("%d\n", tot);
① 26 ② 27 ③ 93 ④ 94 ⑤ 114

47번 문제는 무슨 공식을 찾기 보다는 배열 a를 표현하는 빈칸 21개를 준비하는 것으로 분석을 시작하는 것이 좋을듯 합니다. 배열 초기화에서 "{1, }" 식으로 초기화하면 값이 기술된 부분을 제외한 나머지 부분은 0으로 초기화 됨을 "올림피아드 기출문제로 배우는 C언어 - 배열와 포인터"에서 언급한 바가 있습니다. 로직은 배열 a의 세번째 항목부터 해당 첨자 값의(i) 배수에 해당하는 항목에 첨자값/배수를 합산하는 로직입니다. i=2인 경우 2, 4, 6 ~ 18, 20 항목에 대해서 1, 2, 3 ~ 9, 10을 더합니다. i=3인 경우 3, 6, 9 ~ 15, 18 항목에 대해서 1, 2, 3 ~ 5, 6을 더합니다. 주목할 부분은 6, 12, 18에 대해서는 i=2일때에 더해서 합산된다는 것이고 i가 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20의 경우에는 i가 2,3일때 값이 0이 아닌 상태가 되므로 continue문을 만나 루프를 건너 뜁니다. 5, 7, 11, 13, 17, 19의 경우에는 루프를 정상적으로 수행해서 결과는 "1  0  1  1  2  1  5  1  4  3  7  1  10  1  9  8  8  1  15  1  14"와 같고 합산하면 정답은 4번 94입니다.