한국어
메뉴

자료 구조와 알고리즘

서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을 찾는다. 목표 값은 반드시 배열 안에 있고 어느 위치에 있을 확률도 같을 때, 비교 횟수의 평균은 얼마인가?

  1. A약 7회
  2. B50.5회
  3. C100회
정답과 해설 보기

정답: B. 50.5회

목표 값이 k번째에 있으면 비교는 k회이므로, 평균은 (1 + 2 + … + 100) / 100 = 50.5회, 일반적으로는 (n + 1)/2회입니다. 최선의 경우(맨 앞에 있음)는 1회, 최악의 경우(맨 끝에 있음)는 100회이며, 평균도 최악도 n에 비례하므로 시간 복잡도는 O(n)입니다. 약 7회는 log₂ 100 ≈ 6.6에 해당하는 이진 탐색의 횟수로, 데이터가 정렬되어 있지 않으면 사용할 수 없습니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?
  2. 빈 스택에 대해 push 1, push 2, pop, push 3, push 4, pop, pop의 순서로 조작했다. pop으로 꺼낸 값을 차례로 나열한 것은?
  3. 빈 큐에 A, B, C의 순서로 원소를 넣고 하나를 꺼낸 뒤, D를 넣고 하나를 꺼내고, E를 넣고 하나를 꺼냈다. 꺼낸 원소를 차례로 나열한 것은?
  4. 역폴란드 표기법(후위 표기법)으로 쓴 식 '3 4 + 2 * 5 −'를, 수가 오면 스택에 쌓고 연산자가 오면 두 값을 꺼내 계산하여 결과를 쌓는 방법으로 평가했다. 결과는 얼마인가? 여기서 연산자의 왼쪽 값은 먼저 쌓인 쪽의 값으로 한다.
  5. 해시 테이블에서 충돌(collision)에 대한 설명으로 올바른 것은?