2018년 3회 정보처리기사 기출문제 1번

1. Linear Search의 평균 검색 회수는?

   ① n-1            ❷ (n＋1)/2

   ③ n               ④ n/2

 

300x250

 

 

이 문제는 Linear Search(선형 탐색) 알고리즘의 평균 검색 회수를 묻고 있습니다.

---

✅ 정답

❷ (n + 1) / 2

---

✅ 해설

✔ Linear Search란?

• 선형 탐색은 배열 또는 리스트의 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 알고리즘입니다.
• 최악의 경우: 마지막 요소 또는 없음 → n번 비교
• 최선의 경우: 첫 번째 요소에서 발견 → 1번 비교

---

✔ 평균 검색 회수 계산

• 탐색 대상이 n개 있다고 가정하면,
• 찾는 값이 리스트 내에 있을 확률이 동일하다고 가정할 때,
• 각 요소를 찾는 데 필요한 비교 횟수의 평균은:

1+2+3+⋯+nn=n(n+1)/2n=n+12\frac{1 + 2 + 3 + \cdots + n}{n} = \frac{n(n + 1)/2}{n} = \frac{n + 1}{2}

→ 따라서, 평균적으로 (n + 1) / 2 번의 비교가 필요합니다.

---

✔ 보기별 해설

보기 계산 설명

① n - 1	평균 아님, 최악의 경우에서 1을 뺀 것	❌
❷ (n + 1) / 2	✔ 평균 검색 횟수	✅
③ n	최악의 경우	❌
④ n / 2	근사치지만 정확하지 않음	❌

---

✅ 결론

Linear Search의 평균 검색 회수는 (n + 1) / 2이므로, 정답은
👉 ❷ (n + 1) / 2 입니다.