올림피아드 기출문제로 배우는 C언어 - 모듈화

이번 글에서는 함수가 코드의 핵심 역할을 하는 문제들을 골라 보았습니다. C언어를 기반으로 프로젝트를 수행하다보면 개인적으로 자주 적용하는 프로그래밍 기법 중에 하나가 바로 모듈화 프로그래밍입니다. 모듈화 프로그래밍은 기능 단위로 코드를 나누어 작성하는 것으로 개별 기능을 함수 단위로 나눌 수도 있고 소스 코드 자체를 분할 할 수도 있습니다. C++과 같은 OOP(객체지향프로그래밍) 언어에서는 클래스를 사용해서 기능과 데이터등도 분리하여 묶을 수 있지만 C언어 에서는 데이터를 바라보는 범위(Scope)가 함수 내부인가 외부인가로 단순하게 나누어 지고 함수 외부의 경우 같은 소스인가 아닌가 정도로 나뉘어 지므로 C언어에서의 모듈화는 함수로 기능 나누기가 그 시작이 될 수 있습니다. 실제로 프로그램 작성 과정에서 함수의 기능이 완료되지 않았더라도 함수의 리턴 타입과 파라미터 정의등만 존재하고 내용은 없는 Stub 함수를 작성해 두면 빠른 프로그램 개발과 테스트, 협업등에 도움이 됩니다.

42. 다음 프로그램의 두 번째 출력 결과는 001011이다. 일곱 번째 출력 결과는 무엇인가?
    int F(int *A, int n) {
        int i, prev = 0, cnt1 = 0;
        for (i = n - 1; i >= 0; i--) {
            if (A[i] < prev) {
                A[i++] = 1;
                A[i++] = 0;
                for (; i < n; i++) A[i] = (--cnt1 > 0);
                return 1;
            }
            if (A[i] == 1) cnt1++;
            prev = A[i];
        }
        return 0;
    }
    int main() {
        int A[6] = {0, 0, 0, 1, 1, 1};
        do{
            int i;
            for (i = 0; i < 6; i++) printf("%d", A[i]);
            printf("\n");
        } while (F(A, 6));
        return 0;
    }

① 000000 ② 111111 ③ 010110 ④ 011001 ⑤ 011100

이번 문제의 메인 루프는 "do {  } while(조건);" 문장으로 do 다음의 단문 또는 복문({})을 일단 수행한 이후 while 다음의 조건을 검사해서 참(True)일 경우 루프를 다시 수행하고 거짓(False)이면 루프를 빠집니다. while문의 조건은 F()함수의 리턴 값이 참인지에 따르지만 F() 함수의 리턴 타입이 int 형임을 주목해야 할 필요가 있습니다. 다시 한번 강조하지만 C언어에서는 0은 거짓, 0이 아니면 참으로 처리합니다. 메인 루프에서 하는 작업은 배열 A를 단순히 출력하는 것이고 실제 핵심 작업은 함수 F()에서 이루어지고 함수 F()는 전달된 배열 A의 내용을 조정하고 메인 루프에서는 그 결과를 단순히 출력하는 방식입니다. 그러므로 첫출력은 A배열의 초기값 000111이고 F()가 하는 작업을 알아야 일곱번째 출력 결과를 유추할 수 있을 것입니다.

F()함수의 첫 파라미터를 "int *A"로 해서 포인터를 요구했지만 메인 루프에서는 "F(A, 6)"과 같이 & 연산자를 통한 주소 추출이 아니라 배열 대표명을 기술했는데 이 과정에 대한 이해도 필요합니다. main 함수의 로컬 변수 A는 정수 배열이지만, F 함수의 로컬 변수 A는 정수 포인터로 두 변수는 완전히 다른 변수임을 이해해야 합니다. "올림피아드 기출문제로 배우는 C언어 - 배열와 포인터"에서도 언급했듯이 배열의 대표명은 배열 첫 원소의 주소값으로 사용할 수 있습니다.  "F(A, 6)"는 "F(&A[0], 6)"와 같다는 의미입니다.

F()함수를 본격적으로 분석해 보죠. 우선 함수 F()의 메인 루프인 for문이 배열 끝부터 앞쪽으로 거꾸로 검색한다는 것이 중요합니다. 그리고 함수 F()가 참으로 리턴하는 분기점의 조건이 배열의 현재값보다 직전 항목의 값이 클때이므로 가능한 경우는 배열에서 뒤가 1이고 앞이 0인 지점입니다. 초기 배열에서는 세번째 항목 값이 0이고 네번째가 1일 때입니다. 위치를 찾으면 해당 위치에 '1', 다음 위치에 '0'을 저장하고 검색 지점까지 찾았던 '1'의 개수 만큼 저장하고 그 나머지는 '0'으로 채웁니다. "A[i] = (--cnt1 > 0);" 문장이 헷갈릴 수도 있는데 --연산자가 변수 앞에 붙었으므로 카운트 변수를 감소시킨 결과가 0보다 크면 1을 0보다 작으면 0을 저장하게 됩니다.  정리해 보면 F() 함수는 배열을 비트열 처럼 간주해서 배열의 뒤에서 앞쪽으로 '0 1'인 조합을 찾아서 '1 0'을 바꾸는 작업을 합니다. 일곱번째 까자의 결과를 정리해 보면 다음과 같습니다. 정답은 5번입니다.

• 000111
• 001011
• 001101
• 001110
• 010110
• 011010
• 011100

44. 다음 프로그램의 출력 결과는 무엇인가?
    void f(int t, int mat[2][2]) {
        int i, j;
        int tmp[2][2];
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                if (t % 2 == 0) {
                    tmp[i][j] = mat[1 - i][j];
                }
                else {
                    tmp[i][j] = mat[i][1 - j];
                }
            }
        }
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                mat[i][j] = tmp[i][j];
            }
        }
    }
    int main() {
        int mat[2][2] = { {2, 0}, {1, 5} };
        int i, j;
        for (i = 0; i < 2015; i++) {
            f(i, mat);
        }
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                printf("%d ", mat[i][j]);
            }
            printf("\n");
        }
        return 0;
    }

① 2 0 ② 0 2 ③ 1 5 ④ 5 1 ⑤ 5 1
  1 5   5 1   2 0   2 0   0 2

이번 문제는 다차원 배열에 대한 명확한 이해가 선행되어야만 합니다. 메인루프 구조는 2차원 배열 mat에 대해서 총 2015회 함수 f()를 호출하고 배열 mat를 두줄로 출력하는 것입니다. "int mat[2][2] = { {2, 0}, {1, 5} };"로 2차원 배열에 초기화한 상태에 대해서 각 항목을 확인해 보면 mat[0][0]=2; mat[0][1]=0; mat[1][0]=1; mat[1][1]=5; 입니다. 

함수 f()의 구조를 보면 첫 루프에서는 파라미터로 전달된 t값의 짝수/홀수 여부에 따라 임시 배열 tmp에 mat 배열의 값을 위치를 변경해서 저장하고 루번째 루프에서는 임시 배열 tmp의 값을 mat배열에 복사하는 단순한 구조입니다. t값이 짝수일 때는 2차원 배열의 앞쪽 첨자를 "1-i"로 뒤집고 홀수면 뒤쪽 첨자를 "1-j"로 뒤집으므로 초기 배열은 1번 보기 상태에서 t가 0일때는 3번 보기처럼되고 t가 1이면 홀수이므로 3번 보기 상태에서 5번 보기 상태로 바뀝니다. 그런데, t가 2, 3을 거치면 원상태로 돌아오므로 t값을 4로 나눈 나머지 값에 따라서 그 시점의 최종 상태를 확인할 수 있을 것입니다. t의 최종 값은 2014이고 나머지는 2이므로 t가 2일때의 상태인 2번이 정답입니다. 핵심을 찾아서 실험하고 단서를 찾아가는 노력을 지속해야 합니다.

46. 다음 프로그램의 출력 결과는 무엇인가?
    char a[7][7] =
    {"001001",
        "111111",
        "110110",
        "011011",
        "001110",
        "111011"};
    int tot = 0;
    void f(int n, int m, int c) {
        if (n < 0 || m < 0 || n >= 6 || m >= 6) return;
        if (a[n][m] == '0') return;
        tot += c;
        a[n][m] = '0';
        f(n - 1, m, c + 1);
        f(n + 1, m, c + 1);
        f(n, m - 1, c + 1);
        f(n, m + 1, c + 1);
    }
    int main() {
        int i, j;
        for (i = 0; i < 6; i++) {
            for (j = 0; j < 6; j++) {
                if (a[i][j] == '1') {
                    f(i, j, 1);
                }
            }
        }
        printf("%d\n", tot);
        return 0;
    }
① 24 ② 144 ③ 180 ④ 196 ⑤ 202

C언어의 문자열은 "올림피아드 기출문제로 배우는 C언어 - C 문자열"에서 언급한 것과 같이 char 또는 unsigned char 타입의 배열로 처리됩니다. C언어의 문자열에서는 널(\0, Null) 문자 처리가 매우 중요한데 위의 예제처럼 "001001"처럼 초기화 하면 배열 맨 마지막에 널 문자를 삽입합니다.

메인 루프의 구조는 2차원 char 배열인 a를 검색하면서 값이 '1'인 경우 함수 f()를 호출하여  전역변수인 tot 값을 설정하고 그 결과를 출력하는 구조입니다. 2차원 배열 a와 합산 변수 tot 모두 전역 변수이기 때문에 함수 파라미터로 전달하지 않음을 주목할 필요가 있습니다. 전역변수를 많이 사용할 수록 코드 재사용성이 떨어지고 심각한 오류에 대한 피해가 크다는 단점이 있지만 속도나 효율성이 중요한 요소일 경우에는 도움이 될 수 있습니다.

f()함수가 복잡해 보이지만 한문장씩 차분히 읽어가면 그리 어렵지 않습니다. f() 함수의 if 문장 두개는 첨자가 배열을 벗어나거나 지목된 곳의 값이 '0'이면 함수를 종료합니다. tot에 값을 카운트한 다음 지목한 곳을 '0'으로 설정하고 2차원 배열을 매트릭스로 간주하여 상하좌우 방향으로 재귀호출하는데 카운트 값이 +1되므로 처음 찾아진 곳은 1이 더해지지만 그 주변에 있는 1은 2가 더해지고 그 다음은 3으로 더해지는 방식입니다. 마치 폭탄이 터지듯 연결 고리를 찾아서 문제지에 숫자를 마킹한 다음 전체를 더하면 답을 얻을 수 있습니다. 주의할 점은 매트릭스에서 '0'을 만나거나 배열 끝에 도달할 때 까지 상-하-좌-우 순서로 찾는 다는 것입니다. 

0 0 1 0 0 1
1 1 1 1 1 1
1 1 0 1 1 0
0 1 1 0 1 1
0 0 1 1 1 0
1 1 1 0 1 1

매트릭스에서 첫번째 1은 첫줄의 세번째 '1'일 것입니다.  tot에 1을 더한 상태에서 위쪽으로의 재귀 호출은 배열 바깥이므로 그냥 리턴합니다. 아래쪽으로의 재귀 호출은("f(n + 1, m, c + 1);") '1'이 있으므로 tot에 2가 더해집니다. 이 상태에서 다시 위쪽으로는 이전 스텝에서 이미 '0'으로 설정되었으므로 그냥 리턴하고 아래쪽으로도 '0'이므로 리턴합니다. 좌측 재귀호출은 '1'이므로 3을 더합니다. 이런 방식으로 추적하면 메인 루프에서는 함수 f()를 한번 호출해서 모든 '1'을 찾게 됩니다.

00 00 01 00 00 14
06 03 02 13 12 13
05 04 00 14 11 00
00 05 06 00 10 11
00 00 07 08 09 00
10 09 08 00 10 11

경로를 찾으면서 더한 숫자는 위의 내용과 같습니다. 모든 숫자를 더하면 값은 202입니다. 미로 찾기나 경로 찾기에 활용할 수 있는 로직이므로 이런 알고리즘은 잘 활용하는 것이 좋겠지요!

48. ccw(0, 0, 1, 0, 1, 1)의 결과는 1이다. 다음 프로그램의 출력 결과는 무엇인가?
    #include 
    int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    }
    int main() {
        int A[5] = {0, 3, 1, 2, 2};
        int B[5];
        int i, cnt = 0;
        for (i = 0; i < 5; i++) {
            while (cnt >= 2 && ccw(B[cnt - 2], A[B[cnt - 2]],
            B[cnt - 1], A[B[cnt - 1]], i, A[i]) >= 0)
            cnt--;
            B[cnt++] = i;
        }
        for (i = 0; i < cnt; i++) printf("%d", B[i]);
        printf("\n");
        return 0;
    }
① 01234 ② 01 ③ 0134 ④ 014 ⑤ 02341

ccw 함수의 "(x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)"는 점 세개의 방향성을 확인하는데 공식처럼 사용되는 알고리즘으로 음수면 삼각형이 시계 방향의 방향성을 갖고 0이면 세점이 일직선에 있음을 의미하고 양수면 삼각형이 반시계의 방향성을 의미합니다. 주목할 점은 ccw호출을 위하여 최소한 세개의 점 위치를 만들기 위해서 while 문에서 cnt가 2이상 일때로 한정하고 있고 y1, y2, y3로 넘기는 값은 모두 A배열의 값이라는 것입니다. 로직 분석이 애매할 경우에는 직접 따라가는 것이 중요합니다. 이번 문제에서 결과에 직접적인 영향을 미치는 부분은 결국 ccw()를 호출하는 부분이므로 ccw() 호출 부분을 직접 따라할 필요가 있습니다.

좌측 그림은 i=0일때의 ccw()를 호출한 (x1, y1), (x2, y2), (x3, y3)를 가지고 점 3개 p1, p2, p3를 좌표로 표시한 것입니다. 삼각형이 시계 방향임을 알수 있습니다. 실제로 ccw의 리턴값은 -5입니다. while문의 조건이 ccw() 리턴값이 0보다 크거나 같으면 cnt를 뒤로 후진 시키므로 결과적으로 비교 대상인 세점의 방향성이 시계 방향이 아니면 무시하고 시계 방향인 점들을 찾는 알고리즘입니다. 위의 좌측 그림은 시계 방향이므로 다음 점을 찾아 전진하고, 우측 그림은 반시계 방향성으로 이 경우는 cnt--문을 통해서 뒤로 후퇴하여 좌측 그림 상태에서 p3를 A배열의 다음 항목을 적용하는 방식으로 진행합니다. 

ccw에 전달할 값을 그래프로 그려보면 리턴값을 계산하지 않더라도 결과를 확인할 수 있습니다. 결과적으로 A배열의 마지막 원소인 2와 마지막 i값 4로 p3가 교체된 좌측 그림이 최종 상태인 4번이 정답입니다.