센터소개

행복한 미래 새로운 중랑을 향한 미래세대
교육의 웅대한 비상

자료실

중랑구 방정환교육지원센터에서 운영하는 다양한
행사와 교육지원 프로그램의 사진입니다.

한국외대 수시 소프트웨어특기자 면접 기출문제

  • 작성일 2019-08-08

  • 조회67

2019학년도 소프트웨어특기자 면접고사 기출문항입니다.



::기출문항1::

경우의 수, 조건과 진리집합

81마리의 말이 경기장에 모였다. 이 경기장에서는 한 번의 경주에 최대 9마리까지만 참가할 수 있다. 경주에 참가한 말의 기록을 잴 수 있는 시계가 설치되어 있지 않아, 한 번의 경주가 끝나면, 경주에 참여한 말들의 등수만 알 수 있다. (단, 같은 등수는 없다고 가정한다. 즉, 한 번의 경주가 끝나면 일등부터 꼴등까지 모두 다른 등수를 갖게 된다.) 전체 81마리의 말 중에서 가장 빠른 4마리의 말을 여러 번의 경주를 통해 알려고 한다. 최소 몇 번의 경주면 가장 빠른 4마리의 말을 알 수 있을까?

[채점기준]

a. 방법 1은 9마리를 묶어 경주를 하고, 1등부터 4등까지를 골라낸 후, 경주에 참여하지 않은 말들 중에서 5마리

를 추가하여 경주를 해서 다시 4등까지 골라내는 방식으로 진행하면 16번 만에 할 수 있음.

b. 방법 2는 9개의 그룹으로 나눈 후, 토너먼트 방식으로 진행하면 방법 1과 같은 16번 만에 할 수 있음.

c. 방법 3은 9개 그룹으로 나눈 후, 9번 경주를 하여 그룹별 1등을 고른다. 각 그룹에서 1등만 모아 한 번 더 경주한다. 여기서 1등한 말이 속한 그룹을 그룹1, 2등한 말이 속한 그룹을 그룹2 등으로 그룹9까지 구별한다. 그러면 그룹1에서는 1등부터 4등까지, 그룹2에서는 1등부터 3등까지, 그룹3에서는 1등부터 2등까지, 그룹4에서는 1등이 전체 4등 이내에 포함될 수 있고, 나머지 그룹의 말들은 해당되지 않는다. 전체 1등을 뺀 이 9마리의 말을 모아 경주를 한 번 더 하면 된다. 총 11번의 경주면 충분하다.

[예시답안]

방법 1: 9마리를 묶어 경주를 하고, 1등부터 4등까지를 골라낸 후, 경주에 참여하지 않은 말들 중에서 5마리를 추가하여 경주를 해서 다시 4등까지 골라내는 방식으로 진행. 생각할 수 있는 가장 단순한 방법으로 16번의 경주면 충분.

방법 2: 9개의 그룹으로 나눈 후, 토너먼트 방식으로 진행한다. 첫 라운드에서는 9번의 경주를 통해, 각 그룹에서 4등까지 골라낸다. 그룹 1의 4등까지와 그룹 2의 4등까지의 8마리와 그룹 9의 1등을 묶어 9마리를 만든다. 같은 방식으로, 그룹 3, 그룹 4의 각 4등까지와 그룹 9의 2등을 묶어 9마리를 만든다. 이렇게 (그룹 5, 그룹 6), (그룹 7, 그룹 8)에 대해, 각각 9마리를 만든다. 그러면 총 9마리 그룹이 4개 만들어지고, 그룹별로 경주를 한다. 이 4번의 경주가 두 번째 라운드이다. 4개의 그룹에서 다시 4등까지를 각각 골라 8마리로 구성된 2개의 그룹을 만들어 세 번째 라운드 경주를 한다. 세 번째 라운드에서 경주한 두 그룹에서 4등까지 모아 최종 8마리를 대상으로 마지막 라운드의 경주를 한 번 한다. 이 마지막 경주에서 4등까지의 말이 답이다. 총 경주 수는 첫 라운드부터 차례대로 9+4+2+1=16번으로 방법 1과 같은 횟수이다.

방법 3: (정해로 11번의 경주면 충분) 9개 그룹으로 나눈 후 경주한다. 총 9번 경주 필요. 각 그룹에서1등만 모아 한 번 더 경주한다. 이 경주가 10번째 경주이다. 여기서 1등한 말이 속한 그룹을 그룹1, 2등한 말이 속한 그룹을 그룹2 등으로 그룹9까지 구별한다.

(가) 10번째 경주에서 1등한 말이 전체 1등이 됨을 알 수 있다. 따라서 이후의 경주에는 참여할 필요가 없다.

(나) 1등을 제외한 가장 빠른 3마리 말은 그룹5, 그룹6, 그룹7, 그룹8, 그룹9에는 절대 존재하지 않는다. 따라서 이 다섯 그룹의 말들은 더 이상 고려하지 않는다.

(다) 가장 빠른 4마리 말에 포함될 수 있는 후보 말들은 다음과 같다.

1) 그룹1의 1, 2, 3, 4등

2) 그룹1의 1등과 그룹2의 1, 2, 3등

3) 그룹1의 1등, 그룹2의 1등, 그룹3의 1, 2등

4) 그룹1의 1등, 그룹2의 1등, 그룹3의 1등, 그룹4의 1등

결국, 그룹1의 2, 3, 4등, 그룹2의 1, 2, 3등, 그룹3의 1, 2등, 그룹4의 1등 중에서만 전체 2, 3, 4등이 나올 수 있다. 이 말들은 4+3+2+1=9마리이다. 따라서 이 말들을 모아 마지막 11번째 경주를 해서 3등까지 말을 선택하면 이 말들이 전체 2, 3, 4등이 된다. 1등은 이미 정해졌으므로 가장 빠른 4마리를 알 수 있다.


::기출문항2::

등차 수열, 공차, 등차수열의 합

정수로 구성된 등차수열에서 연속된 n개의 항을 선택해, 각 항의 숫자 하나를 한 장의 카드에 각각 적었다. 이렇게 마련한 n 장의 카드를 가방에 쑤셔 넣고 집에 와 확인해보니, 도중에 한 장을 분실하고 (n-1) 장의 카드만 남아 있음을 알게 되었다. 여러분은 이제 분실한 카드에 적힌 수가 무엇인지 알아내야 한다. 아래 질문에 대한 답을 차례대로 생각해보자. 여기서 n은 4 이상이라고 가정한다. 카드는 특별한 순서 없이 뒤죽박죽 섞여 있음에 주의하자.

가. 만약, 등차수열이 1, 2, 3, 4, ... 로 공차가 1이고, 1부터 차례대로 n개의 항을 골라 카드에 적었 다면, 분실한 카드에 적힌 수가 무엇인지 어떻게 재빨리 알아낼 수 있을까?

나. 만약, 등차수열의 공차와 몇 번째 항부터 시작해 n개의 항을 골랐는지 전혀 기억이 나지 않는다고 할 때, 분실한 카드에 적힌 수가 무엇인지 재빨리 알아낼 수 있을까? (다행히도, n 값은 기억하고 있다.)

[채점기준]

a. 문항 가에 대해선 방법 1과 방법 2(정해)의 답변 내용에 따라 아래 표와 같이 평가한다.

b. 문항 나에 대해선 정해와 대응 질문에 대한 답변의 내용에 따라 아래 표와 같이 평가한다.

c. 문항 가와 나의 해법은 예시 답안에 자세히 설명되어 있다.

[예시답안]

가. 등차수열 1, 2, ..., n 중에서 한 장을 분실한 경우:

(1) 방법 1: 카드를 크기 순서로 나열한 후, 이웃한 카드의 숫자 차이가 2가 되는 경우에 그 사이의 카드가 분실됨을 알 수 있다.

· [대응 질문] 더 간단한 방법은 없나? 방법 2를 유도.

(2) 방법 2 (정해): 크기 순서로 나열하지 않고 단순히 (n-1)장의 카드에 적힌 수를 모두 더한다. 이 값을 S라 한다. 1+2+...+n = n(n+1)/2 값을 T라 한다. 그러면 빠진 수는 T – S가 됨을 알 수 있다.

나. 등차수열의 공차와 첫째항을 모르는 경우:

(1) 정해: 빠진 수를 알아내기 불가능한 경우도 있다.

· 가장 첫 항을 분실하거나 또는 가장 마지막 항을 분실한 경우라면, 둘 중에 어느 경우에 해당하는지 구별할 수가 없기 때문이다.

(2) [정해 대응 질문] 만약, 분실한 카드가 첫째항도 마지막 항도 아니라면?

· 방법 1: 크기 순서로 나열해서 빠진 수를 알 수 있다. 세 개의 연속된 수를 차례대로 검사하면서 중간에 빠진 수가 있는지 검사하면 된다. 즉, 연속된 세 수 a, b, c 사이에 빠진 수가 없다면, 등차수열의 성질에 따라 a+c = 2b가 성립해야 한다.

· 방법 2 (정해): 위의 가 번의 방법 2와 유사하게 추리하는 것이다. (n-1)장의 카드에 적힌 수를 모두 더한다. 그 합을 S라 하자. 등차수열의 첫째항이 a이고, 마지막 항이 b라면, 이 두 값은 카드에서 가장 작은 수와 가장 큰 수이므로 카드의 값을 서로 비교해서 알 수 있다. n개의 등차수열 항의 합은 T = (a+b)n/2이다. 그래서 T - S가 빠진 카드의 값이다.

02.2094.1885

평일 09:00 ~ 22:00
주말(토,일) 10:00~18:00