제3회 아주 정보 올림피아드 필기시험		수험번호
2002년 6월 19일 오전 10:00-11:30		성 명

1. 아래의 그림에 나타난 순서대로 (1,1)에서 시작하여 각 순서쌍에 1번부터 번호를 매길 때  (7,12)의 번호는?

(1, 1)	(1, 2)	(1, 3)	(1, 4)	(1, 5)
(2, 1)	(2, 2)	(2, 3)	(2, 4)	(2, 5)
(3, 1)	(3, 2)	(3, 3)	(3, 4)	(3, 5)
(4, 1)	(4, 2)	(4, 3)	(4, 4)	(4, 5)
(5, 1)	(5, 2)	(5, 3)	(5, 4)	(5, 5)
(6, 1)	. . . .

① 138      ② 139       ③ 149       ④ 150       ⑤  84

2. 아래의 숫자 피라미드에서 맨 꼭대기에서 시작하여 바로 왼쪽 혹은 오른쪽 아래로 내려가며  바닥에 도달할 때 지나는 숫자들의 합의 최대값과 최소값의 차이는?

						5
					2		8
				4		5		6
			4		1		5		2
		7		2		7		6		4
	4		8		3		8		5		9
4		7		2		6		5		7		6

① 16      ② 19        ③ 26        ④ 30        ⑤  28

3. 여섯 개의 서로 다른 구슬을 세 난쟁이에게 나누어주는 데 적어도 하나씩은 반드시 각 난쟁이에게 할당되고 나머지 구슬은 임의로 난쟁이에게 나누어준다. 구슬을 나누어 줄 수 있는 모든 경우의 수는?

①  630      ② 360      ③ 450       ④ 270      ⑤  540

4. 다음의 프로그램에서 N이 7일 때 출력되는 값은 무엇인가? (3)

READ(N)

RESULT = 0

FOR I = 2 TO N

TEMP = 1

FOR J = 1 TO I-1

TEMP = TEMP * J

RESULT = RESULT + TEMP

PRINT(RESULT)

① 873      ② 5913      ③ 720      ④ 912     ⑤ 870

5. 어느 마을에는 계란이 1원, 우유가 2원, 치즈도 2원이다. 만약 6원의 돈을 가지고 하루에 한 개씩만 구매를 할 경우 6원의 돈을 모두 지출할 수 있는 경우의 수는 몇 가지인가?

① 11	② 31	③ 43	④ 51     ⑤  42

6. 다음과 같은 정사각형 격자가 있다고 하자.

① 42         ② 132        ③ 144      ④ 164     ⑤  154

7. 빨강, 주황, 노랑, 초록, 파랑, 남색, 보라 이렇게 일곱 색깔의 구슬을 흰색과 검은색 두  개의 상자에 세 개씩 나누어 담으려고 한다. 결과적으로 하나는 상자밖에 남게 된다. 상자 에 구슬을 담을 때 따라야 하는 규칙이 있는 데 그 규칙은 다음과 같다.

첫째, 초록 구슬을 흰색 상자에 넣으면 노란 구슬은 반드시 검은 상자에 넣어야 한다.

둘째, 빨간 구슬을 흰색 상자에 넣으면 파란 구슬은 만약 넣고 싶으면 검은 상자에 넣어야 한다.

셋째, 파란 구슬은 남색 구슬과 같은 상자에 넣을 수 없다.

넷째, 주황 구슬과 노란 구슬은 같은 상자에 넣을 수 없다.

만약 빨간 구슬을 흰색 상자에 넣었고 보라색 구슬은 아무 상자에도 넣지 않기로 결정하였다면 검은 상자에 넣을 수 없는 구슬은 어느 것인가?

① 남색 구슬   ② 노란 구슬   ③ 초록 구슬   ④ 주황 구슬    ⑤ 보라 구슬

8. 다섯 명의 환자 - A, B, C, D, E -를 월요일부터 시작해서 7일 동안 모두 치료를 마칠 수 있게 스케줄을 마련하려 한다. 단, 환자의 수술은 하루에 한 명밖에 할 수가 없으며 다음과 같은 다섯 조건을 만족해야 한다.

첫째, A는 두 번의 치료가 필요하며, 두 번째 치료는 첫 번째 치료 후 4일째 되는 날 받아야 한다.

둘째, B는 단 한번의 치료만 받으면 된다.

셋째, C도 한번의 치료만 받으면 되나, A가 첫 번째 치료를 받는 날의 하루 전이나 받은 다음 날 받아야 한다.

넷째, D도 한번의 치료를 받아야 하나, A가 두 번째 치료를 받는 날 이전에 받으면 된다.

다섯째, E도 한번의 치료를 필요로 하나, B가 치료를 받은 삼 일째 되는 날 받아야만 한다.

만약 B가 월요일에 치료를 받을 수 있게 만든 스케줄에서 다음 중에서 이틀 인접해서 치료 스케줄에 나타날 수 없는 환자의 쌍은?

① A와 E     ② A와 B      ③ B와 C     ④ C와 D   ⑤ A와 C

9. 다음 프로그램(왼쪽은 BASIC, 오른쪽은 C로 작성되어 있음)이 출력하는 모양을 고르시오 (N또는 n은 5보다 크고 화면의 폭보다 작다고 가정한다.)

FOR I = 1 TO N	int i, j;

FOR J = I TO 1 STEP -1	for(i=1; i<=n; i++)

PRINT □ □;	{

NEXT J	for(j=i; j>=1; j--)

FOR J = I TO N	printf("%c", ' ');

PRINT □*□;	for(j=i; j<n; j++)

NEXT J	printf("%c", '*');

PRINT	printf("\n");

NEXT I	}

①    ②     ③   ④   ⑤

10. n개의 서로 다른 수로 된 배열 a1, a2, ..., an에서 최대값을 갖는 수를 찾는 문제를 다음과 세 단계를 이용해서 해결할 수 있다.

1) 배열을 가능한한 길이가 같도록(기껏해야 길이의 차이가 1이 되도록) 두개의 배열로 분할한다.

2) 왼쪽 부분의 배열에서 가장 큰 값을 찾고(max1이라고하자), 오른쪽 부분의 배열에서 큰값을 찾는다(max2라고 하자).

3) max1 과 max2를 비교하여 최대값을 계산한다.

단계 2)의 부분배열의 최대값도 위와 같은 방식으로 계산한다.

위 방법을 사용하여 10,000개의 원소를 가진 배열의 최대값을 찾을 경우, 두개의 값을 비교하는 횟수는 얼마인가?

① 10,000번     ② 9,999번       ③ 100번       ④ 20,000번      ⑤ 1,000번

11. A, B, C 3종의 컴퓨터가 각각 3대씩 9대의 컴퓨터가 수리를 받기 위해 대기하고 있다. 이들 컴퓨터에 1번부터 9번까지 한 개씩의 번호가 부여되어, 부여된 번호순대로 수리가 진행된다고 한다. A, B, C 중 어느 두 가지 종류만이 6번부터 9번까지의 번호가 부여될 확률은?

① 5/14	②  5/42	③  3/7        ④ 1/3          ⑤  2/7

12. 문법은 문장을 생성할 수 있는 규칙들의 집합과 문장을 구성할 수 있는 문자의 집합으로 이루어진다. 규칙은 Left -> Right로 이루어지는데 이는 Left부분은 Right부분으로 교체될 수 있을을 의미한다. 가령 규칙, T-> S V O에서 T는 S V O로 교체될 수 있음을 의미한다. S, V, 또는 O는 다시 자신의 규칙에 의해 교체될 수 있다. 이렇게 교체될 수 있는 기호를 비단말기호라고 하고 더이상 교체될 수 없는 기호를 단말기호라고 한다. 하나의 특정 비단말기호(시작기호)로부터 출발하여 규칙들을 적용하여 더 이상 비단말노드를 포함하지 않는 문자열을 만들면 이것이 바로 그 문법이 생성할 수 있는 문장이다.

비단말기호는 하나의 영문대문자로 나타내고 단말기호는 하나의 영문소문자로 나타낸다.

문법규칙이 아래와 같을 때 이 문법으로 생성될 수 없는 문장을 보기에서 고르시오.

시작기호: A,  문자집합 = {a, b, c}

문법규칙:

A -> aaA

A -> bBc

B -> bCc

B -> cb

C -> bbC

C -> bb

① bbbbbbbbcc    ② aabbbbcc    ③ aaaabbbbbbcc     ④ aaaabbbcbc    ⑤ aabcbc

13. 하나의 그래프는 정점(으로 표현된 부분)과 두 정점을 연결하는 에지(선으로 표현된 부분)로 구성된다.  그래프는 아래의 두 가지 규칙을 이용하여 변형이 가능하다.

1) 에지는 같은 정점을 가진 채로 원하는 모양으로 마음대로 구부리거나 펼 수 있다.

2) 정점은 원하는 위치에 이동할 수 있다.

하나의 그래프를 위 두 가지 규칙으로 적절하게 모양을 변형하여 다른 그래프를 만들 수 있다면 이 두 그래프를 동형이라고 말한다. 다음 각 그래프의 쌍들 중 동형이 아닌 것을 고르시오.

①	②

③	④

⑤

14. 잠이 오지 않는 밤, 철수는 잠을 이루기 위해 숫자를 세기로 했다. 단, 4자리 숫자로서 첫 번째 숫자와 네 번째 숫자의 차이가 2가 나야 하고, 네 숫자는 모두 달라야 한다. (예: 3721, 5087, 8926 등). 이런 숫자 중 가장 작은 1023부터 세기 시작할 때, 500번째로 세게 되는 숫자는 얼마인가?

① 5983        ② 5987       ③  5697       ④ 5967      ⑤ 5963

15. 갑과 을이 오전 [eqn: 12]부터 [eqn: 12]시 [eqn: 30]분 사이에 만나기로 약속을 하였다. 누가 먼저 도착하더라도 10분 이상은 기다리지 않기로 할 때, 두 사람이 만나게 될 확률은?

① 1/3        ② 1/4        ③ 2/7        ④ 4/9        ⑤ 5/9

16. 다음 표는 서울시 7군데의 주요 전화 기지국간의 거리(km, 직선거리가 아니고 실제 전화선로의 거리를 의미함)를 나타낸 표이다. 모든 기지국이 연결되는 전화선을 설치하려고 한다. 전화선의 설치비용은 1km에 100만원이며 지역에 상관없이 거리에만 비례한다.  최소비용은 얼마인가? (단위, 100만원)

	A	B	C	D	E	F	G
A	-	7	5	6	17	9	13
B		-	6	10	11	8	9
C			-	7	15	12	11
D				-	15	4	22
E					-	18	10
F						-	14
G							-

① 38       ② 40      ③  43      ④ 45      ⑤  47

17. 세 친구가 2인승 자전거를 타고 20km를 같이 가기로 했다. 자전거가 2인승이기 때문에 다른 두 사람이 자전거를 타는 동안 나머지 한 사람은 걸어야 한다. 그래서 이 세 친구는 이렇게 하기로 했다.

(1) 영희와 순이가 자전거를 타고 떠나고, 철수는 걸어온다.

(2) 어떤 지점에 이르르면 영희가 순이를 내려 놓아 걸어가게 하고 영희는 뒤따라 오는 철수를 데리러 간다.

(3) 영희와 철수는 자전거를 타고, 그리고 순이는 걸어서 거의 같은 시각에 목적지에 도착한다.

자전거는 항상 시속 25km로 여행한다고 하고, 사람은 항상 시속 5km로 움직인다고 할 때, 이들은 출발 시간 후 얼마만에 목적지에 도착할까?

① 1시간 2분  ② 1시간 16분  ③ 1시간 28분  ④ 1시간 36분  ⑤ 1시간 38분

18. 전화번호부에 이름의 가나다 순으로 이름과 전화번호가 정렬되어 있다고 가정할 때 어떻게 원하는 사람의 전화번호를 찾는 것이 일반적으로 가장 빠르겠는가?

① 처음부터 순서대로 찾는다.

② 중간을 찾은 후, 원하는 사람이 앞에 있으면 앞부분의 중간을, 뒤에 있으면 뒷부분의 중간을 찾는다. 이와 같은 방법을 반복한다.

③ 적당한 간격을 두고 찾아 원하는 사람이 있는 범위를 알아내고 그 범위를 순서대로 찾는다.

④ 이름을 보고 있을 만한 위치를 찾는다. 예를 들면 가씨의 경우 앞부분을, 허씨의 경우 뒷부분을, 성씨의 경우 중간부분을 찾는다. 그리고 이와 같은 방법을 반복한다.

⑤ 무작위로 찾는다.

19. 유원지에서 X라는 놀이시설, Y라는 놀이시설, 그리고 Z라는 놀이시설에 대한 안내를 반복하여 방송하고 있다. X라는 놀이시설을 안내하는 데 걸리는 시간은 Z라는 놀이 시설을 안내하는 것 보다 4배의 시간을 차지하고, X와 Y의 안내시간은 동일하다. X, Y, Z 놀이 시설을 이용하는 인원은 동일하고 놀이 시설 이용 시 원하는 놀이 시설의 안내방송을 처음부터 들어야 하고 놓치면 다음 해당 방송이 시작 때까지 기다려야 한다. 다음 방법 중에서 어떠한 순서로 안내방송을 반복하는 것이 해당 놀이시설의 안내 방송을 시작할 때까지 기다리는 평균 시간을 최소화 할 수 있는가?

① XYZ를 반복   ② XZYZ를 반복  ③ XZZYZZ를 반복  ④  XYXYZ를 반복

⑤ 모두 같다

20. 유전자는 A, T, C, G 등 네 가지 종류의 분자 서열로 이루어져 있다. 유전자의 유사성을 비교하기 위하여 A, T, C, G 들로 구성된 분자들의 서열을 비교하되 전체 서열을 그대로 비교하지 않고 연속적인 일부분만 비교할 수 있다. 되도록 연속적으로 일치하는 부분이 많도록 비교하지만 필요에 따라 한쪽 서열에 공란(gap)을 삽입할 수도 있고 중간에 일치하지 않는 부분도 허용하지만 유사성 점수에서 감점을 한다. 즉, 서열을 비교하여 유사성 점수를 계산할 때 동일한 분자마다 2점을 주고, 다르거나 공란을 삽입하면 이 때마다 1점을 감점한다. 예를 들면 두 개의 서열 ATCGACT와 TAGCT를 비교할 때 가장 높은 유사성 점수를 주는 방법은 첫 번째 서열 ATCGACT에서 첫 번째 분자 A를 제외한 연속적인 부분인 TCGACT 만을 비교대상으로 삼고 두 번째 서열 TAGCT은 전체의 연속적인 서열을 모두 비교하되 G와 C사이에 공란(-)을 삽입한 TAG-CT 상태로 비교를 하면 (즉, TCGACT와 TAG-CT를 비교하면) 일치하는 분자수가 4개이므로 4*2=8점이고 불일치와 공란이 각각 1개씩 있으므로 2점을 감한다. 결과적으로 최대의 유사성 점수는 8-2=6이 된다. 두 가지 서열 ATCTCGTATGATG 와 GTCTATCAC를 비교할 때 최대의 유사성 점수는 얼마인가?

① 7           ②  8           ③  9             ④  10         ⑤ 11

21. 장기 일기 예보를 하는 프로그램을 수행하기 위하여 10일간 계속하여 컴퓨터 연산 작업을 해야한다. 그런데 컴퓨터에 가끔 에러가 발생하는데 이때에는 처음부터 프로그램을 다시 시작해야 한다. 만일 9일째 연산작업을 하다가 컴퓨터에 에러가 발생하면 9일동안 작업한 내용이 쓸모없게 되고 처음부터 10일간 작업을 다시 시작해야 한다. 이를 방지하기 위하여 중간 연산 결과를 하드디스크에 저장하면 컴퓨터에 에러 발생시에 처음부터 다시 시작할 필요없이 하드디스크에 저장된 중간 연산 결과를 이용하여 다시 시작할 수 있다. 즉 8일째 중간 연산 결과를 하드디스크에 저장하였다면 9일째에 컴퓨터에 에러가 발생할 경우 하드디스크에 저장된 8일째 중간 연산 결과를 이용하여 9일째 연산을 계속할 수 있다. 그러나 중간 연산 결과 데이터가 방대하여 하드디스크에 저장하는데 30분이나 걸린다. 컴퓨터의 에러 발생률은 시간당 0.01일 때 (정상적인 컴퓨터가 한 시간 이내에 에러를 발생시킬 가능성은 0.01 정도임) 다음 중 어느 간격으로 중간 연산 결과를 하드디스크에 저장하는 것이 가장 좋은가? 즉, 예상 작업 시간을 가장 단축시킬 수 있는가?

① 30분    ②  10 시간   ③ 50시간.    ④ 120시간    ⑤ 저장하지 않고 계속 수행

22. 알파벳 a, b, c, d로 이루어진 문자열이 있다. 문자열 전체는 볼 수 없고 문자열의 일부분으로 이루어진 조각들만 볼 수 있으며 이 조각들은 서로 겹치는 부분도 있다. 예를 들면 원래의 문자열은 abcd 인데 일부분인 ab, bc, bcd 등의 조각들을 볼 수 있다. 전체 문자열의 조각이 acbad, bbba, caaadb, abac 일 때 가능한 전체의 문자열은 무엇인가?

① acbadbbbaaadb   ② bbbabacaaadb   ③ abacaaadbbba  ④ abacaaadbbbacbad

⑤ 답 없음

23. 지도상의 위치를 기준으로 여러 장소들의 정보를 정렬하고 탐색하려고 한다. 한 장소 A를 위하여 필요한 데이터에는 A 장소의 위치(X,Y)와 해당 위치의 정보(INF)가 있고, 다른 장소들을 위한 데이터 주소(pointer)가 있는 데 A를 기준으로 북동쪽에 있으면 NE에 (이 때 바로 인접한 북동쪽에 있음을 의미하는 것이 아니라 상대적인 방향만을 나타낸다), 북서쪽에 있으면 NW에, 남동쪽에 있으면 SE에, 그리고 남서쪽에 있으면 SW에 다른 장소의 데이터 주소(pointer)를 보관한다. 즉, 한 장소를 위한 데이터는 (X,Y), INF, NE, NW, SE, SW로 구성되었다. 이와 같은 데이터 구조를 바탕으로 원하는 위치의 정보를 찾으려 한다. 예를 들면 원하는 위치 (a,b)의 정보를 얻기 위하여 다음 과정을 반복한다.

시작 장소의 데이터 중에서 위치를 (a,b)와 비교하여 일치하면 해당 정보를 얻어 끝내고위치가 일치하지 않으면

(1)  (a,b)가 시작 데이터의 위치보다 북동쪽에 있으면 NE에 있는 데이터를 시작 데이터로 설정

(2)  (a,b)가 시작 데이터의 위치보다 북서쪽에 있으면 NW에 있는 데이터를 시작 데이터로 설정

(3)  (a,b)가 시작 데이터의 위치보다 남동쪽에 있으면 SE에 있는 데이터를 시작 데이터로 설정

(4)  (a,b)가 시작 데이터의 위치보다 남서쪽에 있으면 SW에 있는 데이터를 시작 데이터로 설정

1,000,000개의 위치 데이터가 고루 분포한다고 가정하고 시작 데이터로부터 시작하여 NE, NW, SE, SW 방향으로 고루 위치 데이터가 존재할 때, 원하는 위치의 정보를 얻기 위하여 위치 비교를 평균 몇 번 수행해야 하는지 가장 가까운 답을 구하시오.

① 4          ② 6         ③ 10         ④ 20      ⑤ 500,000

24. 컴퓨터를 이용하여 세 가지 작업을 수행하려고 한다. 세 가지 작업이 끝나기 위하여 (1) A 라는 작업은 순서에 관계없이 CPU를 2초, 하드디스크를 2초 사용하고, (2) B라는 작업은 순서에 관계없이 CPU를 3초, 하드디스크를 3초 사용하며, (3) 작업 C는 CPU를 1초 사용한 이후에 하드디스크를 1초 사용한다. CPU와 하드디스크는 동시에 작동하지만, 각각 한 순간에 한가지의 작업만을 처리할 수 있다. 각 작업에서 CPU와 하드디스크를 연속적으로 사용할 필요는 없다고 가정할 때, 세 가지 작업을 모두 끝내기 위한 최소한의 시간을 구하시오.

① 5초       ②  6초          ③ 7초        ④ 12초        ⑤ 3초

25. 오름차순으로 정렬된 숫자들의 집합 N[1..n]에서 그 합이 M이 되는 모든 가능한 조합을 찾고자 한다. 이를 위해 제일 작은 숫자부터 시작하여 차례대로 각 숫자를 포함시키거나 제외시키면서 모든 가능한 조합을 고려하되 불필요한 검색은 피하고자 한다. 아래의 FUNC 알고리즘은 이러한 조합을 찾기 위한 코드를 보여준다. FUNC(S, k, R)에서는 첫번째부터 k-1번째까지의 숫자에 대한 조합이 이미 고려된 상태에서 k번째 숫자 N[k]와 나머지 숫자들에 대해 고려한다. S는 이미 조합에 포함된 숫자의 합이고, R은 k번째부터 마지막까지 숫자의 합이다.

procedure FUNC (S, k, R)

begin

// N[k]를 조합에 포함시키는 경우

if ( S + N[k] = M )

then   found <- found + 1 ;

else   if ( S + N[k] + N[k+1] ) <= M )

nodeCnt <- nodeCnt + 1 ;

call FUNC ( S + N[k], k + 1, R - N[k] )

endif

endif

// N[k]를 조합에 포함시키지 않는 경우

if ( S + R - N[k] >= M and S + N[k+1] <= M )

then nodeCnt <- nodeCnt + 1 ;

call FUNC ( S, k + 1, R - N[k] )

endif

end FUNC

만약 N[] = (5, 10, 12, 13, 15, 18) 이고 M = 30이고 nodeCnt와 found의 초기값이 0일 경우 M의 값을 갖는 숫자들의 조합을 구하기 위한 함수 호출 FUNC (0, 1, 73)를 수행하였을 때 nodeCnt와 found의 값은 얼마이겠는가?

① 22, 2      ②  22, 3       ③ 23, 2        ④ 23, 3        ⑤ 32, 3