2005 시도예선 중고등부 문제

1. 다음과 같이 정육각형을 둘러싸고 있는 직사각형의 넓이가 60일 때 정육각형의 넓이는 얼마인가?

① 30	② 35	③ 40	④ 45	⑤ 50

2. 크기가 같은 검은색 동전과 흰색 동전이 있다. 검은색 동전 한 개를 흰 색 동전으로 둘러싸려면 아래 그림과 같이 최소 6개의 동전이 필요하다. 검은색 동전 세 개를 놓고 흰 색 동전으로 둘러싸려면 최소 몇 개의 동전이 필요할까? (단 검은색 동전 세 개를 겹치게 놓아서는 안 된다.)

① 9개	② 10개	③ 12개	④ 15개	⑤ 18개

3. A와 B가 서로 다른 숫자라고 할 때, 다음과 같이 바로 쓰나, 거꾸로 쓰나 같은 수가 되는 네 자리 자연수는 총 몇 개인가?

A B B A

① 72개	② 81개	③ 90개	④ 91개	⑤ 100개

4. 각각의 알파벳은 1부터 9까지 서로 다른 자연수를 나타낸다. I값은 얼마인가?

A	+	B	+	C	+	D	+	E	+	F	+	G	=	H	I

① 1	② 3	③ 5	④ 6	⑤ 8

5. 애완동물 가게에 가보니, 아래와 같은 8개의 칸에 각각 다른 애완동물이 놓여 있었다. 다음 말이 모두 참일 때 금붕어 옆에 있는 동물은?

― 강아지 옆 칸에는 고양이가 있다.

― 토끼 아래 칸에는 거북이가 있다.

― 다람쥐 옆 칸에는 햄스터만 있다.

― 금붕어 위에는 앵무새가 있다.

― 강아지와 거북이는 가장 멀리 떨어져 있다.

① 강아지	② 고양이	③ 토끼	④ 다람쥐	⑤ 햄스터

6. 선생님 책상에 놓여 있던 케이크가 없어졌다. 다음 다섯 명의 사람 중 한 명이 먹었고, 이들 중 단 한 명만이 진실을 이야기하고 있다면 과연 케이크를 먹은 사람은 누구일까?

영표 : 종국이가 먹었어요.

종국 : 영표가 먹었어요.

두리 : 종국이가 먹었어요.

동국 : 내가 먹었어요.

주영 : 난 먹지 않았어요.

① 영표	② 종국	③ 두리	④ 동국	⑤ 주영

7. 매시간 일정한 비율로 늘어나는 바이러스가 있다. 오전 10시에 10마리였던 바이러스가 같은 날 오후 2시에 보니 810마리로 불어 있었다. 이 바이러스는 매시간 몇 배씩 늘어나는가?

① 2배	② 3배	③ 4배	④ 10배	⑤ 200배

8. 10개의 점이 아래와 같이 놓여 있다. 점선으로 이은 두 점 사이의 거리가 모두 같다고 할 때 서로 다른 세 점을 이어 만들 수 있는 정삼각형의 개수는?

① 11개	② 12개	③ 13개	④ 14개	⑤ 15개

9. 약수의 개수가 홀수인 자연수의 집합을 A, 약수의 개수가 짝수인 자연수의 집합을 B라고 할 때 다음 중 옳은 것은?

① A의 원소와 A의 원소를 곱한 수는 항상 A의 원소이다.

② A의 원소와 A의 원소를 곱한 수는 항상 B의 원소이다.

③ A의 원소와 B의 원소를 곱한 수는 항상 A의 원소이다.

④ B의 원소와 B의 원소를 곱한 수는 항상 A의 원소이다.

⑤ B의 원소와 B의 원소를 곱한 수는 항상 B의 원소이다.

10. 어떤 일을 찬호가 하면 4시간, 병현이가 하면 6시간, 희섭이가 하면 8시간 걸린다. 셋이서 함께 일한다고 할 때 다음 중 옳은 것은?

① 함께 일하면 2시간이 채 안 걸린다.

② 함께 일하면 정확히 2시간이 걸린다.

③ 함께 일하면 2시간보다는 많이 걸리고 3시간보다는 적게 걸린다.

④ 함께 일하면 정확히 3시간이 걸린다.

⑤ 함께 일하면 3시간보다 더 걸린다.

11. A, B, C 세 사람이 OX문제 10개를 풀었다. 각 사람이 각 문제에 표시한 답과 결과 점수가 다음과 같을 때, 답이 X인 문제는?

	1	2	3	4	5	6	7	8	9	10	점수
A	O	O	X	X	O	O	X	X	O	X	70
B	O	X	X	O	O	O	O	X	X	O	80
C	O	O	X	O	X	X	X	O	O	X	50

① 1번 문제	② 3번 문제	③ 4번 문제	④ 5번 문제	⑤ 6번 문제

12. A지점에서 B지점까지 가는 최단경로의 개수는?

A

B

① 11개	② 12개	③ 13개	④ 14개	⑤ 15개

13. 트리(tree)에서 루트(root)로 놓았을 때 트리의 높이(height)가 가장 작아지는 노드(node)를 그 트리의 중심(center)이라고 한다. 그렇다면 다음 트리의 중심은?

5

7

3

4

6

2

8

9

1

① 3	② 4	③ 5	④ 6	⑤ 7

14. 1, 2, 3 세 개의 자연수를 차례대로 스택(stack)에 넣은 다음, 두 개의 자연수를 빼낸 뒤, 다시 두 개의 자연수 4, 5를 차례대로 스택에 넣고, 스택에 있는 모든 자연수를 빼내었다. 다음 중 자연수들이 스택에서 나온 순서로 알맞은 것은?

1, 2, 3

4, 5

스택

(stack)

① 1, 2, 3, 4, 5	② 1, 2, 4, 5, 3	③ 2, 1, 5, 4, 3

④ 2, 3, 5, 4, 1	⑤ 3, 2, 5, 4, 1

15. 다음과 그래프를 정점 A부터 시작하여 너비우선탐색(BFS)으로 탐색하려고 한다. 가장 늦게 방문하게 되는 정점은?

C

A

G

B

D

E

F

① C	② D	③ E	④ F	⑤ G

16. 다음과 같은 힙(heap)에서 가장 일반적인 방법으로 세 개의 원소를 삭제하면 힙의 모양은 어떻게 되는가?

7

3

6

1

2

5

4

①	②	③

4

3

1

2

4

3

2

1

4

2

1

3

④	⑤

4

3

2

1

4

3

1

2

17. A부터 H가 적혀있는 8개의 노드로 이루어진 이진트리가 있다. 이 이진트리에서 전위 순회로 방문한 노드의 순서가 ABDECFGH, 중위 순회로 방문한 노드의 순서가 DBEAGFHC일 때 후위 순회로 방문한 노드의 순서는?

① ACFGHBDE	② ACFHGBED	③ DBEGHFCA

④ DEBGHFCA	⑤ HGFCEDBA

18. 함수 F(또는 f)가 다음과 같을 때 K(또는 k)의 값은 얼마가 되는가?

< VB >

Function F(P As Integer, Q As Integer)

F = P Mod Q

End Function

...

K = F(20, F(20, 7))

< VC++ >

int f( int p, int q )

{

return p % q;

}

...

k = f( 20, f( 20, 7 ) );

< Delphi >

function f( p, q : integer ) : integer;

begin

f := p mod q;

end;

...

k := f( 20, f( 20 , 7 ) );

① 1	② 2	③ 3	④ 4	⑤ 5

19. 다음 중 1부터 10까지 홀수의 합을 구하는 프로그램이 아닌 것은?

< VB >

①	S = 0	②	S = 0

For I = 1 To 10 Step 2	For I = 1 To 5

S = S + I	S = S + I * 2 - 1

Next I	Next I

③	S = 0	④	I = -1: S = 0

For I = 1 To 10	While I < 10

S = S + I	I = I + 2

I = I + 1	S = S + I

Next I	Wend

⑤	I = 0: J = -1: S = 0

While I < 5

I = I + 1

J = J + 2

S = S + J

Wend

< VC++ >

①	s = 0;	②	s = 0;

for ( i = 1; i <= 10; i += 2 )	for ( i = 1; i <= 5; i++ )

s = s + i;	s = s + i * 2 - 1;

③	s = 0;	④	i = -1;	s = 0;

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

{	{

s = s + i;	i = i + 2;

i = i + 1;	s = s + i;

}	}

⑤	i = 0;	j = -1;	s = 0;

while ( i < 5 )

{

i = i + 1;

j = j + 2;

s = s + j;

}

< Delphi >

①	s := 0; i := 1;	②	s := 0;

while ( i <= 10 ) do	for i := 1 to 5 do

begin	s := s + i * 2 - 1;

s := s + i;

i := i + 2;

end;

③	s := 0;	i := 1;	④	i := -1; s := 0;

repeat	while ( i < 10 ) do

s := s + i;	begin

i := i + 2;	i := i + 2;

until ( i >= 10 );	s := s + i;

end;

⑤	i := 0;	j := -1; s := 0;

while ( i < 5 ) do

begin

i = i + 1;

j = j + 2;

s = s + j;

end;

20. 다음 프로그램은 무엇을 구하는 프로그램인가?

< VB >

C = 0

For I = 1 To 99

If I Mod 3 = 0 Then C = C + 1

I = I + 1

Next I

Debug.Print C

< VC++ >

c = 0;

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

{

if ( i % 3 == 0 ) c = c + 1;

i = i + 1;

}

printf( "%d\n", c );

< Delphi >

c := 0;  i := 1;

while ( i < 100 ) do

begin

if i mod 3 = 0 then inc( c );

i := i + 2;

end;

writeln( c );

① 100의 약수의 개수

② 100보다 작은 3의 배수의 개수

③ 100보다 작은 3의 배수의 개수의 절반

④ 100보다 작은 3의 배수 중 홀수의 개수

⑤ 100보다 작은 3의 배수 중 짝수의 개수

21. 다음 프로그램을 실행시켰을 때 출력되는 수는 몇 개인가?

< VB >

For I = 1 To 10

W(I) = 0

Next I

For I = 1 To 10

J = I

While J <= 10

W(J) = 1 - W(J)

J = J + I

Wend

Next I

For I = 1 To 10

If W(I) = 1 Then Debug.Print I

Next I

< VC++ >

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

w[i] = 0;

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

{

j = i;

while ( j <= 10 )

{

w[j] = 1 - w[j];

j += i;

}

}

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

if ( w[i] == 1 ) printf( "%d\n", i );

< Delphi >

for i := 1 to 10 do

w[i] := 0;

for i := 1 to 10 do

begin

j := i;

while ( j <= 10 ) do

begin

w[j] := 1 - w[j];

j := j + i;

end;

end;

for i := 1 to 10 do

if w[i] = 1 then writeln( i );

① 1개	② 2개	③ 3개	④ 4개	⑤ 5개

22. 배열 P(또는 p)에는 학생 N명의 시험 점수 총점이 담겨 있다. 등수를 구하고자 할 때 빈 칸에 차례로 알맞은 것은?

< VB >

For I = 1 To N

R(I) =

For J = 1 To N

If P(I)   P(J) Then R(I) = R(I) + 1

Next J

Next I

< VC++ >

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

{

r[i] =  ;

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

if ( p[i]  p[j] ) r[i]++;

}

< Delphi >

for i := 1 to N do

begin

r[i] :=  ;

for j := 1 to N do

if ( p[i]  p[j] ) then inc( r[i] );

end;

① 0, >=	② 0, <=	③ 1, >	④ 1, <=	⑤ 1, <

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

< VB >

For I = 1 To 5

A(I) = I

Next I

For I = 1 To 5

A(I) = A(6 - I)

Next I

For I = 1 To 5

For J = 1 To A(I)

Debug.Print "*";

Next J

Debug.Print

Next I

< VC++ >

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

a[i] = i;

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

a[i] = a[6 - i];

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

{

for ( j = 1; j <= a[i]; j++ )

printf( "*" );

printf( "\n" );

}

< Delphi >

for i := 1 to 5 do

a[i] := i;

for i := 1 to 5 do

a[i] := a[6 - i];

for i := 1 to 5 do

begin

for j := 1 to a[i] do

write( '*' );

writeln;

end;

① 9개	② 11개	③ 15개	④ 19개	⑤ 21개

24. 다음 프로그램을 실행시켰을 때 출력되지 않는 문자는?

< VB >

C = Asc("A")

For I = 1 To 3

For J = 1 To 3

For K = 0 To 1

For M = 0 To 1

A(I + K, J + M) = C

C = C + 1

If (C > Asc("Z")) Then C = Asc("A")

Next M, K, J, I

For I = 1 To 4

For J = 1 To 4

Debug.Print Chr(A(I, J));

Next J

Debug.Print

Next I

< VC++ >

char c = 'A';

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

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

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

for ( m = 0; m < 2; m++ )

{

a[i + k][j + m] = c;

c = c + 1;

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

}

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

{

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

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

printf( "\n" );

}

< Delphi >

c := 'A';

for i := 1 to 3 do

for j := 1 to 3 do

for k := 0 to 1 do

for m := 0 to 1 do

begin

a[i + k, j + m] := c;

inc(c) ;

if ( c > 'Z' ) then c := 'A';

end;

for i := 1 to 4 do

begin

for j := 1 to 4 do

write( a[i, j], ' ' );

writeln;

end;

① A	② E	③ I	④ O	⑤ U

25. 다음은 A > B (또는 a > b)인 두 수 A, B (또는 a, b)의 최대공약수를 구하는 함수이다. 빈 칸에 알맞은 것은?

< VB >

Function GCD(ByVal A As Integer, ByVal B As Integer) As Integer

If A Mod B = 0 Then

GCD = B

Else

GCD =

End If

End Function

① GCD(A - B, B)	② GCD(Int(A / B), B)	③ GCD(A Mod B, B)

④ GCD(B, Int(A / B))	⑤ GCD(B, A Mod B)

< VC++ >

int GCD( int a, int b )

{

if ( a % b == 0 ) return b;

else return  ;

}

① GCD( a - b, b )	② GCD( a / b, b )	③ GCD( a % b, b )

④ GCD( b, a / b )	⑤ GCD( b, a % b )

< Delphi >

function GCD( a, b : integer ) : integer;

begin

if a mod b = 0 then GCD := b

else GCD :=  ;

end;

① GCD( a - b, b )	② GCD( a div b, b )	③ GCD( a mod b, b )

④ GCD( b, a div b )	⑤ GCD( b, a mod b )

26. N개의 정점으로 이루어진 가중치 그래프가 있다. i번 정점과 j번 정점을 잇는 간선의 가중치를 d(i, j)라고 하자.(d(i, i) = 0이며, i번 정점과 j번 정점을 잇는 간선이 없다면 d(i, j)는 무한대이다.) 다음은 이러한 그래프에서 모든 정점 사이의 최단 거리를 구하는 프로그램의 일부이다. 빈 칸에 차례로 알맞은 것은?

< VB >

For I = 1 To N

For J = 1 To N

For K = 1 To N

If ( <  ) Then

(1)

(2)

=

(2)

(1)

End If

Next K, J, I

① D(I, J) + D(J, K), D(I, K)	② D(I, K) + D(K, J), D(I, J)

③ D(J, I) + D(I, K), D(J, K)	④ D(J, K) + D(K, I), D(J, I)

⑤ D(K, J) + D(J, I), D(K, I)

< VC++ >

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

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

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

if (  <  )

(1)

(2)

=  ;

(2)

(1)

① d[i][j] + d[j][k], d[i][k]	② d[i][k] + d[k][j], d[i][j]

③ d[j][i] + d[i][k], d[j][k]	④ d[j][k] + d[k][i], d[j][i]

⑤ d[k][j] + d[j][i], d[k][i]

< Delphi >

for i := 1 to N do

for j := 1 to N do

for k := 1 to N do

if (  <  ) then

(1)

(2)

:=  ;

(2)

(1)

① d[i, j] + d[j, k], d[i, k]	② d[i, k] + d[k, j], d[i, j]

③ d[j, i] + d[i, k], d[j, k]	④ d[j, k] + d[k, i], d[j, i]

⑤ d[k, j] + d[j, i], d[k, i]

27. 배열 A(또는 a)에는 N개의 자연수가, 배열 B(또는 b)에는 M개의 자연수가 오름차순으로 정렬되어 들어있다. 이 둘을 합쳐 오름차순으로 정렬된 결과를 배열 C(또는 c)에 담는 프로그램을 작성하려 한다. 다음 빈 칸에 알맞은 것은?

< VB >

PA = 1: PB = 1: PC = 0

While (PA <= N And PB <= M)

If A(PA) < B(PB) Then

PC = PC + 1

C(PC) = A(PA)

PA = PA + 1

Else

PC = PC + 1

C(PC) = B(PB)

PB = PB + 1

End If

Wend

If  Then

For I = PA To N

PC = PC + 1: C(PC) = A(I)

Next I

Else

For I = PB To M

PC = PC + 1: C(PC) = B(I)

Next I

End If

① PA <= N	② PA < N	③ PA = N	④ PA > N	⑤ PA >= N

< VC++ >

pa = pb = pc = 0;

while ( pa < N && pb < M )

{

if ( a[pa] < b[pb] )

{

c[pc] = a[pa];

pc++;	pa++;

}

else

{

c[pc] = b[pb];

pc++;	pb++;

}

}

if (  )

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

c[pc++] = a[i];

else

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

c[pc++] = b[i];

① pa < N	② pa <= N	③ pa == N	④ pa >= N	⑤ pa > N

< Delphi >

pa := 1;  pb := 1;  pc := 0;

while ( pa <= N ) and ( pb <= M ) do

begin

if ( a[pa] < b[pb] ) then

begin

inc( pc );

c[pc] := a[pa];

inc( pa );

end

else

begin

inc( pc );

c[pc] := b[pb];

inc( pb );

end;

end;

if (  ) then

for i := pa to N do

begin

inc( pc );

c[pc] := a[i];

end

else

for i := pb to M do

begin

inc( pc );

c[pc] := b[i];

end;

① pa <= N	② pa < N	③ pa = N	④ pa > N	⑤ pa >= N

28. 다음은 무엇을 구하는 프로그램인가?

< VB >

C = N - 1

For I = 2 To N

For J = 2 To I - 1

If (I Mod J = 0) Then

C = C - 1

Exit For

End If

Next J, I

Debug.Print C

< VC++ >

c = N - 1;

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

for ( j = 2; j < i; j++ )

if ( i % j == 0 )

{

c--;

break;

}

printf( "%d\n", c );

< Delphi >

c := N - 1;

for i := 2 to N do

for j := 2 to i - 1 do

if i mod j = 0 then

begin

dec( c );

break;

end;

writeln( c );

① N의 약수의 개수	② N이하인 소수의 개수	③ N이하인 홀수의 개수

④ N이하인 짝수의 개수	⑤ N이하인 합성수의 개수

29. 다음 프로그램의 출력 결과는?

< VB >

For I = 1 To 10

A(I) = 0

Next I

For I = 1 To 9

For J = 1 To 9

K = I * J

If K <= 10 Then A(K) = A(K) + 1

Next J, I

Max = A(1): P = 1

For I = 2 To 10

If A(I) >= Max Then

Max = A(I)

P = I

End If

Next I

Debug.Print P

< VC++ >

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

a[i] = 0;

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

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

{

k = i * j;

if ( k <= 10 ) a[k]++;

}

max = a[1];	p = 1;

for ( i = 2; i <= 10; i++ )

if ( a[i] >= max )

{

max = a[i];

p = i;

}

printf( "%d\n", p );

< Delphi >

for i := 1 to 10 do

a[i] := 0;

for i := 1 to 9 do

for j := 1 to 9 do

begin

k := i * j;

if ( k <= 10 ) then inc( a[k] );

end;

max := a[1];  p := 1;

for i := 2 to 10 do

if ( a[i] >= max ) then

begin

max := a[i];

p := i;

end;

writeln( p );

① 2	② 4	③ 6	④ 8	⑤ 10

30-31. 아래와 같은 문제를 해결하기 위해 프로그램을 작성하였다. 빈 칸의 내용으로 알맞은 것은?

문제

신종 바이러스인 윔 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 윔 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 윔 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 < 그림 1 >과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 윔 바이러스에 걸리면 윔 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 윔 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

1

2

3

4

5

6

7

< 그림 1 >

어느 날 1번 컴퓨터가 윔 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 윔 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 1번 컴퓨터가 윔 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 윔 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

입력과 출력의 예

입력(INPUT.TXT)	출력(OUTPUT.TXT)

7

6

1 2

2 3

1 5

5 2

5 6

4 7

4

< VB >

Const MAX_N As Integer = 100

Dim N, M As Integer

Dim List(MAX_N, MAX_N) As Integer

Dim Degree(MAX_N) As Integer

Dim Visited(MAX_N) As Boolean

Dim Count As Integer

Sub InputFile()

Open "input.txt" For Input As #1

Input #1, N

Input #1, M

For I = 1 To M

Input #1, p, q

Degree(p) = Degree(p) + 1: List(p, Degree(p)) = q

Degree(q) = Degree(q) + 1: List(q, Degree(q)) = p

Next I

Close #1

End Sub

Sub DFS(V As Integer)

Visited(V) = True

Count = Count + 1

For I = 1 To Degree(V)

If Not Visited( ) Then DFS ( )

(1)

(1)

Next I

End Sub

Sub Output()

Open "output.txt" For Output As #1

Print #1,

(2)

Close #1

End Sub

Sub Main()

Call InputFile

Call DFS(1)

Call Output

End Sub

30. 빈 칸 (1)에 알맞은 내용은?

① I	② V	③ List(V, I)	④ List(I, V)	⑤ List(Count, I)

31. 빈 칸 (2)에 알맞은 내용은?

① Count - 2	② Count - 1	③ Count	④ Count + 1	⑤ Count + 2

< VC++ >

#include <stdio.h>

#define MAX_N	100

int  n, m;

int  list[MAX_N + 1][MAX_N];

int  degree[MAX_N + 1];

bool visited[MAX_N + 1];

int  count;

void Input ()

{

FILE *f = fopen ( "input.txt", "rt" );

int i;

int p, q;

fscanf( f, "%d", &n );

fscanf( f, "%d", &m );

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

{

fscanf( f, "%d %d", &p, &q );

list[p][degree[p]++] = q;

list[q][degree[q]++] = p;

}

fclose( f );

}

void DFS (int v)

{

visited[v] = true;

count++;

for ( int i = 0; i < degree[v]; i++)

if (!visited[  ]) DFS(  );

(1)

(1)

}

void Output ()

{

FILE *f = fopen ( "output.txt", "wt" );

fprintf( f, "%d\n",  );

(2)

fclose( f );

}

void main ()

{

Input();

DFS( 1 );

Output();

}

30. 빈 칸 (1)에 알맞은 내용은?

① i	② v	③ list[v][i]	④ list[i][v]	⑤ list[count][i]

31. 빈 칸 (2)에 알맞은 내용은?

① count - 2	② count - 1	③ count	④ count + 1	⑤ count + 2

< Delphi >

program M30;

{$APPTYPE CONSOLE}

uses

SysUtils;

const

MAX_N = 100 ;

var

n, m    : integer;

list    : array[1..MAX_N, 1..MAX_N] of integer;

degree  : array[1..MAX_N] of integer;

visited : array[1..MAX_N] of boolean;

count   : integer;

procedure Input ;

var

f	: text;

i, p, q	: integer;

begin

assign( f, 'input.txt' );

reset( f );

read( f, n );

read( f, m );

for i := 1 to m do

begin

read( f, p, q );

inc( degree[p] );	list[p, degree[p]] := q;

inc( degree[q] );	list[q, degree[q]] := p;

end;

close( f );

end;

procedure DFS(v : integer);

var

i    : integer;

begin

visited[v] := true;

inc( count );

for i := 1 to degree[v] do

if not visited[ ] then DFS(   );

(1)

(1)

end;

procedure Output;

var

f : text;

begin

assign( f, 'output.txt' );

rewrite( f );

write( f,   );

(2)

close( f );

end;

begin

Input;

DFS( 1 );

Output;

end.

30. 빈 칸 (1)에 알맞은 내용은?

① i	② v	③ list[v, i]	④ list[i, v]	⑤ list[count, i]

31. 빈 칸 (2)에 알맞은 내용은?

① count - 2	② count - 1	③ count	④ count + 1	⑤ count + 2

32-33. 아래와 같은 문제를 해결하기 위해 프로그램을 작성하였다. 빈 칸의 내용으로 알맞은 것은?

문제

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

조건 1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.

조건 2. 같은 문자는 같은 개수만큼 있다.

예를 들어 'DOG'와 'GOD'은 둘 다 D, G, O 세 종류의 문자로 이루어져 있으며 양쪽 모두 D, G, O가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 'GOD'과 'GOOD'의 경우 'GOD'에는 O가 하나, 'GOOD'에는 O가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 'DOG'와 'GOD'은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 'DOG'에서 O를 하나 추가하면 'GOOD'과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 'DOG'에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 'DOLL'과 같은 구성이 되지는 않으므로 'DOG'과 'DOLL'은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10이하이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 출력한다.

입력과 출력의 예

입력(INPUT.TXT)	출력(OUTPUT.TXT)

4

DOG

GOD

GOOD

DOLL

2

< VB >

Const MAX_N As Integer = 100

Dim N As Integer

Dim Word(MAX_N) As String

Dim Count(MAX_N, 26) As Integer

Dim Result As Integer

Sub InputFile()

Open "input.txt" For Input As #1

Input #1, N

For I = 1 To N

Input #1, Word(I)

Next I

Close #1

End Sub

Sub CountAlphabet()

For I = 1 To N

Length = Len(Word(I))

For J = 1 To Length

K = Asc(Mid(Word(I), J, 1)) - Asc("A") + 1

(1)

Next J

Next I

End Sub

Sub Compare()

For I = 2 To N

Similar = True

P1 = 0: P2 = 0

For J = 1 To 26

If Count(1, J) + 1 = Count(I, J) Then

P1 = P1 + 1

ElseIf Count(1, J) = Count(I, J) + 1 Then

P2 = P2 + 1

ElseIf Count(1, J) <> Count(I, J) Then

Similar = False

Exit For

End If

Next J

If   Then Similar = False

(2)

If Similar Then Result = Result + 1

Next I

End Sub

Sub Output()

Open "output.txt" For Output As #2

Print #2, Result

Close #2

End Sub

Sub Main()

Call InputFile

Call CountAlphabet

Call Compare

Call Output

End Sub

32. 빈 칸 (1)에 알맞은 내용은?

① Count(I, J) = Count(I, J) + 1	② Count(I, K) = Count(I, K) + 1

③ Count(J, K) = Count(J, K) + 1	④ Count(K, I) = Count(K, I) + 1

⑤ Count(K, J) = Count(K, J) + 1

33. 빈 칸 (2)에 알맞은 내용은?

① P1 < 1 And P2 < 1	② P1 <= 1 And P2 <= 1	③ P1 <= 1 Or P2 <= 1

④ P1 > 1 And P2 > 1	⑤ P1 > 1 Or P2 > 1

< VC++ >

#include <stdio.h>

#include <string.h>

#define MAX_N	100

#define MAX_LEN	10

int  n;

char word[MAX_N][MAX_LEN + 1];

int  count[MAX_N][26];

int  result;

void Input ()

{

FILE *f = fopen ( "input.txt", "rt" );

fscanf( f, "%d\n", &n );

for ( int i = 0; i < n; i++ )

fscanf( f, "%s", word[i] );

fclose( f );

}

void CountAlphabet ()

{

int i, j;

int len, k;

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

{

len = strlen ( word[i] );

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

{

k =  word[i][j] - 'A';

;

(1)

}

}

}

void Compare ()

{

int  i, j;

bool similar;

int  p1, p2;

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

{

similar = true;

p1 = p2 = 0;

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

if ( count[0][j] + 1 == count[i][j] ) p1++;

else if ( count[0][j] == count[i][j] + 1 ) p2++;

else if ( count[0][j] != count[i][j] )

{

similar = false;

break;

}

if (    ) similar = false;

(2)

if ( similar ) result++;

}

}

void Output ()

{

FILE *f = fopen ( "output.txt", "wt" );

fprintf( f, "%d\n", result );

fclose( f );

}

void main ()

{

Input();

CountAlphabet();

Compare();

Output();

}

32. 빈 칸 (1)에 알맞은 내용은?

① count[i][j]++	② count[i][k]++	③ count[j][k]++

④ count[k][i]++	⑤ count[k][j]++

33. 빈 칸 (2)에 알맞은 내용은?

① p1 < 1 && p2 < 1	② p1 <= 1 && p2 <= 1	③ p1 <= 1 || p2 <= 1

④ p1 > 1 && p2 > 1	⑤ p1 > 1 || p2 > 1

< Delphi >

program M32;

{$APPTYPE CONSOLE}

uses

SysUtils;

const

MAX_N = 100;

var

n	: integer;

word	: array[1..MAX_N] of string ;

count	: array[1..MAX_N, 1..26] of integer;

result	: integer;

Procedure Input;

var

f : text;

i : integer;

begin

assign(f, 'input.txt');

reset(f);

readln(f, n);

for i := 1 to n do

readln(f, word[i]);

close(f);

end;

procedure CountAlphabet;

var

i, j	: integer;

len, k	: integer;

begin

for i := 1 to n do

begin

len := length(word[i]);

for j := 1 to len do

begin

k := integer(word[i, j]) - 64;

;

(1)

end;

end;

end;

procedure Compare;

var

i, j	: integer;

p1, p2	: integer;

similar	: boolean;

begin

for i := 2 to n do

begin

similar := true;

p1 := 0; p2 := 0;

for j := 1 to 26 do

if ( count[1, j] + 1 = count[i, j] ) then inc( p1 )

else if ( count[1, j] = count[i, j] + 1 ) then

inc( p2 )

else if not (count[1, j] = count[i, j]) then

begin

similar := false;

break;

end;

if  then similar := false;

(2)

if ( similar ) then inc( result );

end;

end;

procedure Output;

var

f : text;

begin

assign(f, 'output.txt');

rewrite(f);

writeln(f, result);

close(f);

end;

begin

Input;

CountAlphabet;

Compare;

Output;

end.

32. 빈 칸 (1)에 알맞은 내용은?

① inc( count[i, j] )	② inc( count[i, k] )	③ inc( count[j, k] )

④ inc( count[k, i] )	⑤ inc( count[k, j] )

33. 빈 칸 (2)에 알맞은 내용은?

① ( p1 < 1 ) and ( p2 < 1 )	② ( p1 <= 1 ) and ( p2 <= 1 )

③ ( p1 <= 1 ) or ( p2 <= 1 )	④ ( p1 > 1 ) and ( p2 > 1 )

⑤ ( p1 > 1 ) or ( p2 > 1 )

34-35. 아래와 같은 문제를 해결하기 위해 프로그램을 작성하였다. 빈 칸의 내용으로 알맞은 것은?

문제

크기가 모두 다른 직사각형 모양의 색종이가 여러 장 있다. 색종이를 하나씩 올려 놓아, 되도록 많은 장수의 색종이들을 쌓으려고 한다.

새로 한 장의 색종이를 올려 놓을 때는 지금까지 쌓아 놓은 색종이들 중 맨 위의 색종이 위에 올려 놓아야 하며 아래의 두 조건을 모두 만족해야 한다.

조건 1 : 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다. 즉, 맨 위의 색종이 밖으로 나가지 않아야 한다.

조건 2 : 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다. (색종이를 90° 돌려 놓을 수 있다.)

예를 들어, 아래의 그림 중에서 위의 두 조건을 모두 만족하는 경우는 (나) 뿐이다.

(가)

(나)

(다)

(라)

색종이는 두 변의 길이로 표현된다. (3, 5)는 두 변의 길이가 각각 3과 5인 색종이를 나타낸다. 예를 들어, 다음과 같이 7장의 색종이가 주어졌다고 하자 : (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12). 위의 두 조건을 만족하면서 가장 많이 쌓을 수 있는 색종이들의 순서는 (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2)이다.

입력으로 색종이들이 주어졌을 때, 위의 조건 1과 조건 2를 만족하면서 쌓을 수 있는 최대 색종이 장수를 구하는 프로그램을 작성하시오.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 작은 자연수이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 쌓을 수 있는 최대 색종이 장수를 출력한다.

입력과 출력의 예

입력(INPUT.TXT)	출력(OUTPUT.TXT)

7

1 2

8 7

20 10

20 20

15 12

12 14

11 12

6

< VB >

Const MAX_N As Integer = 100

Dim N As Integer

Dim A(MAX_N), B(MAX_N), C(MAX_N) As Integer

Dim Count As Integer

Sub InputFile()

Open "input.txt" For Input As #1

Input #1, N

For I = 1 To N

Input #1, A(I), B(I)

Next I

Close F

End Sub

Sub Exchange(P, Q)

Tmp = P

P = Q

Q = Tmp

End Sub

Sub Solve()

For I = 1 To N

If A(I) > B(I) Then

Call Exchange(A(I), B(I))

End If

Next I

For I = 1 To N - 1

For J = I + 1 To N

If () Then

(1)

Call Exchange(A(I), A(J))

Call Exchange(B(I), B(J))

End If

Next J, I

Count = 0

For I = 1 To N

For J = 1 To Count

If () Then Exit For

(2)

Next J

C(J) = A(I)

If J > Count Then Count = Count + 1

Next I

End Sub

Sub Output()

Open "output.txt" For Output As #2

Print #2, Count

Close #2

End Sub

Sub MAIN()

Call InputFile

Call Solve

Call Output

End Sub

34. 빈 칸 (1)에 알맞은 내용은?

① A(I) > A(J)	② A(I) < A(J)	③ B(I) > B(J)

④ B(I) < B(J)	⑤ A(I) > B(J)

35. 빈 칸 (2)에 알맞은 내용은?

① A(I) < C(J)	② A(I) > C(J)	③ B(I) < C(J)

④ B(I) > C(J)	⑤ B(J) < C(I)

< VC++ >

#include <stdio.h>

#define MAX_N	100

int n;

int a[MAX_N], b[MAX_N], c[MAX_N];

int count;

void Input ()

{

FILE *f = fopen ( "input.txt", "rt" );

fscanf( f, "%d", &n );

for ( int i = 0; i < n; i++ )

fscanf( f, "%d %d", &a[i], &b[i] );

fclose( f );

}

void Exchange( int &p, int &q )

{

int tmp;

tmp = p;

p = q;

q = tmp;

}

void Solve ()

{

int i, j;

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

if ( a[i] > b[i]) Exchange( a[i], b[i] );

for ( i = 0; i < n - 1; i++ )

for ( j = i + 1; j < n; j++ )

if (   )

(1)

{

Exchange( a[i], a[j] );

Exchange( b[i], b[j] );

}

count = 0;

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

{

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

if (   ) break;

(2)

c[j] = a[i];

if ( j == count ) count++;

}

}

void Output ()

{

FILE *f = fopen ( "output.txt", "wt" );

fprintf( f, "%d\n", count );

fclose( f );

}

void main ()

{

Input();

Solve();

Output();

}

34. 빈 칸 (1)에 알맞은 내용은?

① a[i] > a[j]	② a[i] < a[j]	③ b[i] > b[j]

④ b[i] < b[j]	⑤ a[i] < b[j]

35. 빈 칸 (2)에 알맞은 내용은?

① a[i] < c[j]	② a[i] > c[j]	③ b[i] < c[j]

④ b[i] > c[j]	⑤ b[j] < c[i]

< Delphi >

program M34;

{$APPTYPE CONSOLE}

uses

SysUtils;

const

MAX_N = 100;

var

n	: integer;

a, b, c	: array[1..MAX_N] of integer;

count	: integer;

Procedure Input;

var

f	: text;

I	: integer;

begin

assign( f, 'input.txt' );

reset( f );

readln(f, n);

for i := 1 to n do

readln(f, a[i], b[i]);

close(f);

end;

procedure Exchange(var p, q : integer);

var

tmp  : integer;

begin

tmp := p;

p := q;

q := tmp;

end;

procedure Solve;

var

i, j : integer;

begin

for i := 1 to n do

if ( a[i] > b[i] ) then Exchange (a[i], b[i]);

for i := 1 to n - 1 do

for j := i + 1 to n do

if (  ) then

(1)

begin

Exchange( a[i], a[j] );

Exchange( b[i], b[j] );

end;

count := 0;

for i := 1 to n do

begin

for j := 1 to count do

if (  ) then break;

(2)

c[j] := a[i];

if ( j > count ) then inc( count );

end;

end;

procedure Output;

var

f    : text;

begin

assign(f, 'output.txt');

rewrite(f);

writeln(f, count);

close(f);

end;

begin

Input;

Solve;

Output;

end.

34. 빈 칸 (1)에 알맞은 내용은?

① a[i] > a[j]	② a[i] < a[j]	③ b[i] > b[j]

④ b[i] < b[j]	⑤ a[i] < b[j]

35. 빈 칸 (2)에 알맞은 내용은?

① a[i] < c[j]	② a[i] > c[j]	③ b[i] < c[j]

④ b[i] > c[j]	⑤ b[j] < c[i]