for 루프와 배열 - 정보올림피아드 문제풀이

아들의 이번 질문은 머리를 "콩"하고 쥐고 박고 싶은 문제입니다, 시간이 들지만 조금 집중하면 프로그램을 읽고 답할 수 있는 수준의 문제인데 아직 C언어 초보인 것을 감안하면서 차분하게 설명해 보겠습니다.

다음 프로그램의 출력 결과는 무엇인가?

int x[10],y[10];
int i,j;
int n = 10;
for (i = 0; i < n; i++) x[i] = i + 1;
for (i = 0; i < n; i++) {  
    for (j = 0; j < n; j++) {
        y[j] = x[(i + j) % n];
    }
    for (j = 0; j < n; j++) x[j] = y[j];
}
printf("%d %d %d\n", x[3], x[6], x[9]);

① 10 3 6 ② 7 10 3 ③ 8 1 4 ④ 9 2 5 ⑤ 3 6 9

프로그램을 설명하기에 앞서 C언어의 기본 문법을 몇가지 다루고 넘어갈 까 합니다. 

1. 변수의 선언과 영향 범위

굳이 설명을 드리는 이유는 이 부분에 있어 핵심을 놓치면 스스로 함정을 파는 격이 되기 때문입니다. C언어에서 변수는 영문 소문자, 대문자, 숫자 그리고 밑줄(_ Underscore)로 만들수 있습니다. 주의할 점은 첫 문자로 숫자가 올수 없다는 것이고 대문자와 소문자를 각기 다르게 취급한다는 특성이 있습니다(Case censitive) 예를 들어 gotoHome 이란 변수와 GotoHome은 다른 변수입니다. 예전에는 문법에 틀린 변수 선언을 골라내는 문제도 단골이었습니다.

함수 내부에 선언한 변수를 지역변수라(Local scope) 하며 해당 함수에서만 사용할 수 있습니다. 함수 바깥에 선언한 변수는 전역 변수(Global scope)라 하고 모든 함수에서 사용할 수 있는 특성이 있습니다. 그런데 전역변수로 선언한 이름과 동일한 이름을 지역변수로 선언할 수도 있는데 이런 경우 함수 내에서 해당 변수를 참조하면 전역 변수가 아닌 지역변수를 참조하게 되므로 주의해야 합니다.

변수 선언 형식은 "데이터타입 변수명=초기값;"으로 위의 코드 예제를 보면 정수형 "int" 타입으로 x, y,i, j, n 변수를 선언하고 있으며 n에는 초기값 10을 대입하고 있습니다. 만약에 초기값을 대입하지 않으면 해당 변수에는 어떤 값이 들어가 있을지 모르는 "Undefined" 상태가 이므로 되도록 초기값을 설정하는 과정을 꼭 갖도록 해야 합니다. C언의 기본 데이터형은 정수형 int, 큰정수형 long, 부동소숫점 float와 double, 문자형 char 등이 있습니다.

2. 배열

배열은 데이터형이 동일한 원소들을 모아 놓은 것으로 C언어에서 배열은 변수 선언시 변수명 옆에 대괄호[]로 배열 원소의 개수를 적는 것으로 선언할 수 있습니다. 위의 코드를 보면 x와 y를 정수형 원소를 가진 배열로 선언했습니다.

선언한 x, y를 그림으로 표현하면 위와 같습니다. 배열의 대표명으로 x, y 변수를 사용할 수 있고 내부의 특정한 원소를 참조하거나 특정한 원소에 값을 입력할 때는 x[3]과 같이 대괄호 내부에 원소의 위치(인덱스)를 지정하면 됩니다. 개별 원소의 위치는 맨 앞에 있는 것을 0으로 해서 차례로 지정하고 배열의 마지막 원소의 위치는 "원소의 개수-1"입니다. 위에서 선언한 배열을 일차원 배열이라하고 일차원배열 여러개를 묶어 것을 2차원, 또 묶으면 3차원 배열 식으로 사용할 수 있습니다. 아래의 그림은 이차원 배열 x[3][10]을 그림으로 나타낸 것입니다.

3. for 루프

루프(Loop)는 반복적인 작업을 지시하기 위한 제어 구조로 C언어에서는 for 루프, while 루프, do while 루프를 대표적으로 제공하고 있습니다. 문법은 아주 간단합니다. "for (초기식; 조건식; 증분식) 문장;", "while (조건) 문장;", "do 문장; while(조건);"으로 공통적으로 조건이 참(True)일 동안 문장을 반복합니다. 차이점은 do while은 문장을 먼저 실행하고 조건을 검사하지만 나머지는 조건을 먼저 검사한다는 것입니다. C언어에서 참(True), 거짓(False)의 구분은 부등호나 논리 연산의 결과로 판단하기도 하지만 0이면 거짓, 0이 아니면 참입니다. 예를 들어 "for (;;) i++;", "while (1) i++;",  "do i++; while(1);"는 모두 항상 조건이 참인 무한루프 입니다.

각 루프에서 수행하는 "문장"은 세미 콜론(;)으로 끝나는 단일 문장일 수도 있고 중괄호{}로 묶인 복합 문장일 수도 있습니다. 위의 코드 예제에서 첫번째 for 루프는 단일 문장을 반복하고 있고, 두번째 for 루프는 복합 문장을 반복하고 있습니다. 각 루프 내부에는 또다른 루프를 포함(nested loop)할 수 있습니다. 위의 코드도 for 루프 내부에 다른 루프 2개를 내장하고 있음을 확인할 수 있습니다.

for 루프는 while 루프와 다르게 초기식과 증분식을 지정할 수 있습니다. 모두 생략할 수 있으며 지정하는 경우 초기식은 for루프에 처음 도달했을때 1회 실행하고 조건식은 매 반복 전에 확인하며 증분식은 문장을 실행한 다음 또는 문장이 복합 문장일 경우 중간에 "continue"를 만났을 때 수행되고 조건식으로 넘어갑니다.

설명이 길었습니다. 그렇지만 꼭 짚고 넘어가야할 내용이므로 익숙하지 않은 부분은 반복적으로 코딩해서 눈으로 결과를 확인하셔야 합니다.

문제 풀이

이제 문제 풀이로 돌아가서 

첫번째 for 루프를 만나면 x 배열에는 첫번째 원소부터 차례로 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 초기화 됩니다.

두번째 for 루프를 n회 반복하는데 내부에 있는 두가지의 for 루프에서 x, y 배열간 이동 작업을 n회 진행합니다. 첫번째 루프는 x배열의 특정 원소를 가져오는데 그 위치를 i의 크기만큼 우측으로 이동해서 가져옵니다. 단, 우측으로 이동한 위치가 배열 범위인 n을 넘지 않도록 나머지 연산(%)으로 조정해 주었습니다. 

y[0]를 기준으로 본다면 i가 0일때 x[0]을 가져오고 9일때는 x[9]위치에 있는 값을 가져오게 됩니다. 결과적으로 i가 0일때는 y배열의 내용은 x배열의 내용과 동일한 내용이 저장되지만(0 이동) i가 1일때 부터는 위치가 우측에 있는 것을 가져오고 다음 루프에서는 이동 결과인 y배열의 값을 x배열에 저장한 다음 그 변동 된 값을 기준으로 작업하므로 결과적으로 정리해 보면 i값 만큼 우측으로 떨어진 것으로 가져오므로 "배열을 i값 만큼 좌측으로 이동시킨다"고 정리할 수 있습니다. 코드를 보면서 이렇게 정리되면 좋지만 그렇지 않은 경우에는 아래 처럼 값을 직접 대입해서 계산해 나갈 수도 있습니다. 중요한 점은 배열의 순서, 즉 처음 배열된 1 ~ 10의 값의 배열 순서는 바뀌지 않는 로직이니 모든 값을 계산할 필요는 없겠죠.

i=0: 1 2 3 4 5 6 7 8 9 10

i=1: 2 3 4 5 6 7 8 9 10 1

i=2: 4 5 6 7 8 9 10 1 2 3

i=3: 7 8 9 10 1 2 3 4 5 6

i=4: 1 2 3 4 5 6 7 8 9 10

i=5: 6 7 8 9 10 1 2 3 4 5

i=6: 2 3 4 5 6 7 8 9 10 1

i=7: 9 10 1 2 3 4 5 6 7 8

i=8: 7 8 9 10 1 2 3 4 5 6

i=9: 6 7 8 9 10 1 2 3 4 5

결론적으로 y[0]의 값을 보면 0 1 2 3 4 5 6 7 8 9 만큼 증가되는 결과를 가져왔습니다. 답은 x[3]=9, x[6]=2, x[9]=5로 4번이 정답입니다.

루프와 배열을 사용하는 다른 문제들을 풀어보시면 많은 도움이 될 것입니다. 그런데 머리는 조금 아플 겁니다. 메모하시면서 규칙을 찾으세요. 그것이 시작입니다.

1. 다음 프로그램을 실행시켰을 때 출력되는 값은?

#define N 100

bool door[N+1];
int count;

void main()
{
 int i, j; 

 for (i=1; i<=N; i++)
 {
  j = i;
  do {
   door[j] = !door[j];
   j += i;
  } while (j<=N);
 }

 for (i=1; i<=N; i++)
  if (door[i]) count++;

 printf("%d\n", count);
}

(1) 10 (2) 11 (3) 12 (4) 13 (5) 14

2. 다음 프로그램을 실행시켰을 때 출력되는 ‘*’의 개수는?

#define N 5

void main()
{
 int i, j;

 for (i=1; i<=N; i++)
 {
  for (j=1; j<=N-i; j++)
   printf(" ");
  for (j=N-i+1; j<=N; j++)
   printf("* ");
  printf("\n");
 }

 for (i=N-1; i>=1; i--)
 {
  for (j=1; j<=N-i; j++)
   printf(" ");
  for (j=N-i+1; j<=N; j++)
   printf("* ");
  printf("\n");
 }
}

(1) 9 (2) 15 (3) 16 (4) 25 (5) 34

3. 다음 프로그램을 실행시켰을 때 출력되는 값은?

#define N 7

void main()

{

 int a[N][N];

 char c;

 int x, y;

 int i, j, k;

 c = 'A';

 x = N/2; y = 0;

 for (i=N/2; i>0; i--)

 {

  for (j=0; j<4; j++)

   for (k=0; k<i; k++)

   {

    a[y][x] = c;

    c++; if (c > 'Z') c = 'A';

    switch (j) 

    {

     case 0 : x--; y++; break;

     case 1 : x++; y++; break;

     case 2 : x++; y--; break;

     case 3 : x--; y--; break;

    }  

   }

  y++;

 }

 a[y][x] = c;

 printf("%c\n", a[3][3]);

}

(1) G (2) M (3) Q (4) U (5) Y

4. 아래 프로그램의 실행한 결과 출력되는 1의 개수는?

#define M 10

#define N 3

int a[N+2][N+2], b[N+2][N+2];

void main()

{

 int i, j, k;

 int count;

 a[1][1] = 1; a[1][2] = 1; a[2][2] = 1;

 a[2][3] = 1; a[3][3] = 1;

 for (i=0; i<M; i++)

 {

  for (j=1; j<=N; j++)

   for (k=1; k<=N; k++)

   {

    count = a[j-1][k-1] + a[j-1][k] + a[j-1][k+1] +

            a[j][k-1] + a[j][k+1] +

            a[j+1][k-1] + a[j+1][k] + a[j+1][k+1];

    if (count == 3) b[j][k] = 1;

    else if (count >= 4 || count <= 1) b[j][k] = 0;

    else b[j][k] = a[j][k];

   }

  for (j=1; j<=N; j++)

   for (k=1; k<=N; k++)

    a[j][k] = b[j][k];

 }

 for (i=1; i<=N; i++)

 {

  for (j=1; j<=N; j++)

   printf("%d ", a[i][j]);

  printf("\n");

 }

}

(1) 3개 (2) 4개 (3) 5개 (4) 6개 (5) 7개