객관식1번 / 2점
최댓값을 찾을 때의 비교 횟수
원문 발췌: 1강 연습문제 22번
A는 숫자 n개가 든 리스트이며 n≥1이다. 다음 Python 코드를 한 번 실행한다. A[i] > largest를 검사하는 횟수만 셀 때, 총 몇 번 검사하는가?
def get_largest(A):
largest = A[0]
for i in range(1, len(A)):
if A[i] > largest:
largest = A[i]
return largest
객관식2번 / 2점
합병 정렬의 병합 조건
원문 발췌: 4강 연습문제 2번
합병 정렬의 분할 뒤 반드시 필요한 전제는?
단답형3번 / 2점
네 자리 자물쇠의 전체 후보 수
원문 발췌: 2강 연습문제 62번
0~9로 이루어진 4자리 자물쇠를 0000부터 순서대로 모두 시도할 때, 마지막까지 갔다면 총 몇 회 시도한 것인지 쓰시오.
원문처럼 값·식 또는 한두 문장으로 답합니다. 별도의 설명 없이 정답만 써도 2점입니다.
서술형4번 / 4점
유클리드 알고리즘 추적
원문 발췌: 3강 연습문제 77번
최대공약수를 구하는 유클리드 알고리즘은 b가 0이 아닐 동안 (a,b)를 (b,a%b)로 동시에 바꾼다. %는 a를 b로 나눈 나머지이며, b=0이면 a를 반환한다.
(18,12)에서 시작한다. 시작 쌍부터 종료할 때까지의 (a,b)를 순서대로 쓰고, 최종 최대공약수를 쓰시오.
순서대로 쓴 세 쌍에 각 1점, 최종 최대공약수에 1점입니다. 풀이 과정은 쌍의 변화로 보여 주면 됩니다.
코딩형5번 / 4점
첫 등장 위치 찾기
원문 발췌: 3강 연습문제 91번
길이 n인 정수 배열 a와 정수 x가 주어진다. x가 처음 등장하는 인덱스(0부터)를 반환하고 없으면 −1을 반환하는 first_index를 작성하시오.
0≤n≤1000이며 원소와 x는 C의 int 범위이다. 배열은 바꾸지 않는다.
Python: first_index(a,x) / C: int first_index(const int a[],int n,int x)
Python 또는 C 하나로 함수와 시간 복잡도를 작성하시오. 기본 정수 연산은 O(1)로 센다.
함수만 작성합니다. 입력 읽기·출력·main은 필요 없습니다. 아래 예제는 원문 계약을 확인하기 위한 실행 예제입니다.
공개 예제| 배열 a | 찾는 값 x | 반환값 |
|---|
| [8, 3, 8] | 8 | 0 |
| [8, 3, 8] | 7 | −1 |
| [] | 8 | −1 |
코드는 이 브라우저에서 실행합니다.
실행 결과가 여기에 표시됩니다. 첫 실행은 실행 환경을 내려받아 시간이 걸릴 수 있습니다.
코드 검토 3점 + 시간 복잡도 1점입니다. Codex가 제출한 코드를 읽고 평가합니다.