올림피아드 기출문제로 배우는 C언어 - 복합 대입 연산자

복합 대입 연산자는 +=, -=, *=, /= 처럼 산술연산자(+, -, *, /, %)나 비트연산자(>>, <<, &, |, ^)에 대입 연산자(=)를 붙여서  a = a + b; 와 같이 l-value(대입 대상)가 우측 표현식(r-value)에도 등장하는 경우 a+=b;와 같이 간략하게 기술할 수 있도록 한 것입니다. 주의할 점은 우측 표현식이 아주 긴 경우라 하더라도 대입 연산자 또는 복합 대입 연산자는 우선순위가 가장 낮기 때문에 우측 표현식을 모두 수행한 다음에 처리된다는 것을 감안해야 합니다.

32. 다음 보기를 빈 칸에 넣었을 때 결과가 0인 것은 무엇인가?
    int a[5] = { _______________ };
    int i, s = 0;
    
    for (i = 0; i < 5; i++) {
        s ^= a[i];
    }
    printf("%d\n", s);
① 0, 1, 2, 3, 4 ② 1, 2, 3, 4, 4
③ 2, 3, 4, 5, 6 ④ 10, 20, 30, 40, 50
⑤ 1, 1, 1, 1, 1

위의 문제는 XOR 비트 연산자(^)와 XOR 대입 연산자(^=)를 알고 있다면 간단하게 풀수 있는 문제입니다. 비트 연산자(& - AND, | - OR, ^ - XOR)는 정수형 변수나 값에 대해서만 수행할 수 있음은 기억하면서 위의 문제를 풀때는 정수 값을 2진수로 변환해서 비트 연산을 수행하면 됩니다. XOR 연산은 동일한 비트 위치값이 서로 다를때 1이므로 변수 s의 초기값 0과 4번 보기 첫 항목 10을 예로 XOR 연산을 하면 2진수 00000000 ^ 00001010 = 00001010으로 첫 루프를 돈 다음에는 s에는 10이 대입됩니다. 두번째 루프는 10^20이므로 2진수로 하면 00001010^00010100 = 00011110으로 10진수로는 30이 됩니다. 그다음 루프에서는 30^30으로 같은 값을 XOR연산하므로 당연히 결과는 0이지만 이후 루프에서는 비트 위치가 달라지므로 결과는 0이 아닙니다. 2번 항목의 경우에는 두번째 루프에서 s에 3이 되었다가 다음 루프에서 3을 만나 0이 됩니다. 0과 XOR 연산을 하면 본래 값을 유지하므로 네번째 루프에서는 s에 4가 입력되고 마지막에 동일한 4를 만나므로 XOR 결과는 0이 됩니다.

39. 다음 프로그램의 출력 결과는 무엇인가?
    int n = 2015, i = 1, tot = 0;
    int a = 0;
    while (n > 0) {
        if (n % 10 == 2) {
            tot += (n / 10) * i + (a + 1);
        }
        else if (n % 10 > 2) {
            tot += (n / 10 + 1) * i;
        }
        else {
            tot += (n / 10) * i;
        }
        a += i * (n % 10);
        i *= 10;
        n /= 10;
    }
    printf("%d\n", tot);
① 616 ② 617 ③ 618 ④ 619 ⑤ 620

위의 문제는 정수 연산과 복합 대입 연산자를 잘 알고 있다면 어렵지 않게 풀 수 있습니다. while문의 조건이 n이 0보다 클동안이므로 n의 값이 0이거나 음수면 루프를 빠져나갑니다.  n의 값을 10으로 나누면서 루프를 수행하므로 결과적으로 n의 값이 2015, 201, 20, 2일 동안 총 4회 수행하면서 tot의 값을 더해 갑니다. 여기서 한가지 짚고 넘어갈 것은 정수형 값에 대한 나누기(/) 연산에는 반올림이나 소수점 처리는 전혀 없다는 것입니다.  10나누기 3의 몫은(/ 연산자) 3이고 나머지(% 연산자)는 1인 방식입니다. tot변수 합산 결과를 묻는 것인데 n 값에 따라 더하는 값이 달라지므로 각 루프별로 로직에 개입하는 n, a, i 변수의 값을 모두 추적해야 합니다. n을 10으로 나눈 나머지(% 연산자)가 2인 경우(n:2)는 "tot += (n / 10) * i + (a + 1)"를 나머지가 3~9일때는(n:2015) "tot += (n / 10 + 1) * i"를 나머지가 0~1일때는(n:201, 20) "tot += (n / 10) * i"를 수행하므로 각 루프를 차례대로 추적하면

• (2015/10+1) * 1 = 202, a = 5
• (201/10) * 10 = 200, a = 15 
• (20/10) * 100 = 200, a = 15
• (2/10) * 1000 + (15 + 1) = 16 

합산하면 정답은 3번 618입니다. 나머지 연산자(%)는 짝수/홀수 구별등 다양한 용도로 많이 사용하므로 익숙할 필요가 있습니다.

40. 다음 프로그램의 출력 결과는 무엇인가?
    int n = 2015, c = 0;
    while (n > 0) {
        c += (n & 3);
        n = n & (n - 1);
    }
    printf("%d\n", c);
① 0 ② 2 ③ 4 ④ 5 ⑤ 8

40번 문제는 AND 비트 연산과 복합 대입 연산자를 알고 있다면 어렵지 않게 풀수 있습니다. 우선 루프의 핵심인 변수 n의 변화를 파악하는 것이 관건입니다. "n = n & (n - 1)"는 복합 대입 연산자를 활용해서 "n &= n - 1"로도 사용할 수 있습니다. 문제는 비트 연산이므로 정수값을 2진수로 변환해야 합니다. 2015는 0111 1101 1111이므로 첫 루프에서는 0111 1101 1111 & 0111 1101 1110이고 AND는 두 비트 위치가 모두 1일때 1이므로 결과는 0111 1101 1110(2014)가 됩니다. 다음 루프 에서는 0111 1101 1110 ^ 0111 1101 1101 = 0111 1101 1100으로 결과 값은 2012가 됩니다. 주목할 점은 n - 1과 AND연산을 수행하면 맨 우측에 1인 비트가 지워지는 결과라는 것입니다.

• 0111 1101 1111(2015)
• 0111 1101 1111 & 0111 1101 1110 = 0111 1101 1110(2014)
• 0111 1101 1110 & 0111 1101 1101 = 0111 1101 1100(2012)
• 0111 1101 1100 & 0111 1101 1011 = 0111 1101 1000(2008)
• 0111 1101 1000 & 0111 1101 0111 = 0111 1101 0000(2000)
• 0111 1101 0000 & 0111 1100 1111 = 0111 1100 0000(1984)
• 0111 1100 0000 & 0111 1011 1111 = 0111 1000 0000(1920)
• 0111 1000 0000 & 0111 0111 1111 = 0111 0000 0000(1792)
• 0111 0000 0000 & 0110 1111 1111 = 0110 0000 0000(1536)
• 0110 0000 0000 & 0101 1111 1111 = 0100 0000 0000(1024)
• 0100 0000 0000 & 0011 1111 1111 = 0000 0000 0000(0)

실제로 위의 n의 변화 과정을 보면 맨 우측의 1부터 차례로 지워지는 것을 확인할 수 있습니다. 그런데, 문제는 c의 결과를 묻는 것인데 c에 합산하는 값은 n의 맨 우측 두 비트 값을 추출한 결과입니다. AND 연산자로 특정 비트 값을 추출하는 과정을 비트 마스킹(Masking)이라 하며 플래그를 저장하고 검사하는등 다양한 용도로 많이 사용하므로 반드시 숙지해야 합니다. 그런데 n의 값이 맨끝 비트 부터 차례로 지워지므로 처음 두 루프인 2015, 2014 때만 각각 마스킹 결과인 3과 2가 더해져 결과는 5입니다. 나머지 루프는 마스킹 결과가 항상 0이므로 c값에는 아무런 영향을 미치지 않습니다.

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

위의 문제는 나머지 연산(%)을 활용한 배열 인덱싱 기법을 배울만한 코드입니다. 기본 루프는 변수 i에 기반하므로 for문에 있는대로 변수 i를 0~7까지 수행합니다. 총 8회 동안 배열을 참조해서 단순히 합산하는 로직이지만 배열 인덱싱의 규칙을 이해하면 보다 효과적으로 프로그램을 분석할 수 있습니다. 배열 참조를 위해서 변수 i에 상수값을 더한 결과를 배열 크기 로 나누어 그 나머지 값을 첨자로 사용하면 시작 지점부터 차례대로 참조하고 다시 처음으로 돌아가서 차례대로 참조하는 환형(circular) 참조를 수행합니다. 예를 들어 "(i + 1) % 4"는 1부터 시작해서 1, 2, 3, 0, 1, 2, 3, 0로 배열을 참조하고 "i%4"는 0부터, "(i + 3) % 4"는 3부터 시작하는 방식입니다. 특이한 수식이 있는데 "(i * 3) % 4"는 0부터 시작해서 0, 3, 2, 1, 0, 3, 2, 1 처럼 배열을 역방향으로 검색합니다. 추후에 활용하려면 "(i * (배열크기 -1)) % 배열크기"로 사용하면 배열을 역방향으로 환형 참조할 수 있습니다. 이제 배열 참조를 위한 인덱스의 시작 위치만 알면 차례대로 값을 참조하면 되므로 표현식에 맞추어 값을 적어서 산수만 하면 됩니다. 문제에서는 3문장에 걸쳐서 tot에 합산 했지만 아래와 같이 변형할 수 있을 것입니다.

tot += (a[(i + 1) % 4] * b[(i + 3) % 4]) - (b[(i * 3) % 4] * c[(i + 2) % 4]) + (a[i % 4] * c[i % 4]);

• (2 * 9) - (9 * 6) + (0 * 1) = -36
• (3 * 9) - (9 * 0) + (2 * 3) = 33
• (1 * 1) - (3 * 1) + (3 * 6) = 16
• (0 * 3) - (1 * 3) + (1 * 0) =-3
• (2 * 9) - (9 * 6) + (0 * 1) =-36
• (3 * 9) - (9 * 0) + (2 * 3) =33
• (1 * 1) - (3 * 1) + (3 * 6) =16
• (0 * 3) - (1 * 3) + (1 * 0) =-3

합산하면 정답은 20입니다. 그런데, 만약 i의 값이 8이 아니라 40이라면 40회 모두를 위와 같은 방식으로 계산해야 할까요? 그렇지 않습니다. 배열의 개수가 모두 동일하고, 역방향이든 순방향이든 모두 환형 참조를 하고 있기 때문에 위의 순행 결과를 보듯이 배열의 크기 만큼 반복되고 있음을 확인할 수 있습니다. 결과적으로 첫 4회까지의 결과만 추출하면 나머지는 반복될 것이므로 4회 루프까지의 합계인 10 * 2로 위의 문제를 풀수도 있을 것입니다.

집중과 단서 찾기, 핵심을 찾으며 불필요한 것 가지치기, 작은 것도 소홀하지 않는 통합 사고력이 프로그램 분석의 열쇠입니다. 물론, C언어에 대한 기본기는 충실해야 겠지요?