올림피아드 기출문제로 배우는 C언어 - for 루프

이번 문제는 간단하지만 얕보다가 당할 수 있는 그러한 문제입니다. for문의 동작 원리를 아주 명쾌하게 습득 할 필요가 있습니다.

17. 다음 프로그램이 출력하는 값은?
    int t, i;
    t = 0;
    for (i = 0; i < 10; i++) {
        t++;
    }
    printf("%d %d\n", t, i);
① 10 10 ② 9 11 ③ 10 9 ④ 9 10 ⑤ 11 9

for (시작 표현식; 비교 표현식; 증분표현식) 문장 

for 문법에 대해서는 "올림피아드 기출문제로 배우는 C언어 - 기본 문장"에서 많은 부분을 언급했으므로 언급하지 않은 부분, 유의할 부분을 다루겠습니다. 위의 문제에서 루프 반복 여부 검사에 사용하는 변수는 i이고 t 변수를 통해서 루프의 수행 회수를 카운트 하고 있습니다. 앞서 다룬것 처럼 for문의 표현식 수행 순서는 "시작 표현식" -> "비교 표현식" -> "문장" -> "증분 표현식" -> "비교 표현식" -> "문장" -> ...... ->"증분 표현식" -> "비교 표현식" ->루프 종료이므로 for 루프가 종료한 시점의 i 값은 증분 표현식을 수행한 다음이고 비교 표현식이 False일 때이므로 10입니다. 

루프가 몇번이나 수행되었는지를 나타내는 변수 t의 값은 위의 문제의 경우는 간단하지만 값이 커지거나 시작 값이 0이 아니거나 종료 조건이 다르게 되면 시간을 조금 잡아먹거나 헤매일 가능성이 높습니다. 답을 도출해도 확신을 갖지 못하는 상황에 빠질 수 있습니다. for문을 포함해서 while등 루프의 수행 회수를 묻는 문제의 경우 수학의 등차수열(等差數列)과 관련한 몇가지 원리를 응용하면 빠르고 정확한 값을 구할 수 있습니다. 

등차 수열은 "1, 2, 3, 4, 5" 나 "4, 6, 8, 10"과 같이 시작값(초항)으로 시작하여 일정한 값(등차)을 순서대로 더해서 이루어진 수열을 말합니다. 초항이 a, 등차가 d인 수열은 아래와 같은 식으로 표현할 수 있습니다.

n번째 항의 값을 구하고 싶다면 위의 공식에 대입하면 간단하게 항의 값을 구할 수 있습니다. "1, 2, 3, 4, 5" 수열의 경우 항이 5개인 등차 수열로 a가 1, d도 1이므로 다섯번 째 항의 값은 "1 + (5 - 1)1" 이므로 결과 값은 "5"가 맞습니다. "4, 6, 8, 10" 수열의 경우 항의 개수가 4인 등차수열로 a는 4, d는 2입니다. 이 수열의 3번째 항의 값을 구하려면 "4 + (3 - 1)2"에 적용하면 "8"이 맞습니다. 초항과 등차, 끝항의 값을 알고 있을때 이 등차 수열의 항의 개수는 다음과 같은 공식을 사용하여 간편하게 구할 수 있습니다. 끝항을 z라 정의하고 z의 값은 a보다 크다는 가정입니다.

"1, 2, 3, 4, 5" 수열의 경우 (5 - 1)/1 + 1 = 5가 맞고 "4, 6, 8, 10" 수열의 경우 (10 - 4)/2 + 1와 같이 공식에 대입하면 항의 개수  "4"가 맞습니다. for나 while 루프에 대하여 루프가 수행된 횟수를 구하거나 n번째 값을 구할 경우 위의 공식을 활용하면 많은 도움을 받을 수 있습니다. 중요한 점은 초항(시작 값, a), 등차(증분, d)와 함께 끝항(종료 값, z)을 정확하게 구해야 합니다. 위의 문제의 경우 초항은 0, 등차는 1, 끝항은 9이므로 루프가 수행된 회수, 즉 등차 수열의 항의 개수는 (9-0) / 1 + 1 이므로 10입니다. for문 수행이후의 값도 10이므로 1번이 정답입니다. 몇가지 응용 사례를 살펴 보겠습니다.

for (i=1; i<=10; i++) t++;

위의 예제에서는 끝항에 주의해야 합니다. 조건이 "i가 10보다 작거나 같을 동안"이므로 a = 1, z = 10, d = 1입니다. t++가 수행된 회수 즉, 항의 개수는 (10 - 1) / 1 + 1 = 10입니다.

for (j = 2; j < 100; j+=3) t++;

위의 예제에서는 끝항과 등차에 주의해야 합니다. ++ 연산자를 사용했다면 등차가 1이겠지만 대입연산자 j+=3을 사용했으므로 등차는 3이어서 j의 값은 "2, 5, 8"과 같은 값을 가지게 됩니다. 실수할 수 있는 부분이 끝항을 구하는 것입니다. "j < 100"이라고 해서 끝항이 무조건 99는 아니라는 것입니다. 이런 경우 항의 값을 구하는 공식을 활용하면 좋습니다. 100보다 작은 항의 값은 2 + (33 - 1)3 = 98 로 33번째 항의 값이 98로 끝항입니다. 결과적으로 a = 2, z = 98, d = 3이므로 항의 개수는 (98 - 2) / 3 + 1 = 33 맞습니다.

for (k = 85; k > 0; k -= 4) t++;

위의 예제는 값이 거꾸로 진행하는 경우이지만 다를 것은 없습니다. 초항(85)과 등차(-4)가 있으므로 등차수열 공식에 따라 0보다 큰 n번째 항의 값을 찾으면 됩니다. 85 + (22 - 1) -4 = 1 로 22번째 항의 값인 1이 끝항입니다. 항의 개수는 (85 - 1) / 4 + 1 = 22 맞습니다.