2020년 1회,2회(통합) 정보처리기사 기출문제 21번

21. 정렬된 N개의 데이터를 처리하는데 O(Nlog2N)의 시간이 소요되는 정렬 알고리즘은?

    ① 선택정렬       ② 삽입정렬

    ③ 버블정렬       ❹ 합병정렬

 

 

이번 문제는 정렬 알고리즘에 관한 문제입니다. 주어진 **시간 복잡도 O(Nlog2N)**에 맞는 정렬 알고리즘을 찾아야 합니다. 각 정렬 알고리즘의 시간 복잡도를 분석하고, 그에 맞는 답을 도출해 보겠습니다.

---

✅ 문제

정렬된 N개의 데이터를 처리하는데 O(Nlog2N)의 시간이 소요되는 정렬 알고리즘은?

① 선택정렬
② 삽입정렬
③ 버블정렬
❹ 합병정렬

---

🔍 각 정렬 알고리즘 분석

1. 선택정렬 (Selection Sort)

• 시간 복잡도: O(N^2)
• 선택정렬은 데이터를 선택하여 위치를 바꾸는 방식으로, 각 단계마다 최소값을 찾아 교환합니다.
• 이 알고리즘은 **O(N^2)**의 시간이 소요됩니다.

따라서, ① 선택정렬은 **O(Nlog2N)**에 해당하지 않습니다.

2. 삽입정렬 (Insertion Sort)

• 시간 복잡도: 최선의 경우 O(N), 최악의 경우 O(N^2)
• 삽입정렬은 각 데이터를 적절한 위치에 삽입하면서 정렬을 진행합니다.
• 최선의 경우에는 이미 정렬된 데이터를 처리할 때 O(N)의 시간이 걸리지만, 최악의 경우에는 **O(N^2)**의 시간이 소요됩니다.

따라서, ② 삽입정렬도 **O(Nlog2N)**에 해당하지 않습니다.

3. 버블정렬 (Bubble Sort)

• 시간 복잡도: O(N^2)
• 버블정렬은 인접한 두 데이터를 비교하고 교환하면서 정렬을 진행합니다.
• 최악의 경우, 즉 데이터가 반대로 정렬되어 있을 경우 **O(N^2)**의 시간이 소요됩니다.

따라서, ③ 버블정렬 역시 **O(Nlog2N)**에 해당하지 않습니다.

4. 합병정렬 (Merge Sort)

• 시간 복잡도: O(Nlog2N)
• 합병정렬은 분할 정복 방식으로 작동합니다.
• 데이터를 두 부분으로 나누어 각각 정렬한 후, 두 부분을 합치는 방식으로 진행됩니다.
• 각 분할 단계에서 **O(logN)**의 시간이 걸리며, 각 단계에서 데이터를 비교하는데 **O(N)**의 시간이 걸리기 때문에 전체 시간 복잡도는 **O(Nlog2N)**입니다.

따라서, ❹ 합병정렬은 **O(Nlog2N)**에 정확히 맞는 정렬 알고리즘입니다.

---

🧠 선택지 분석

번호 정렬 알고리즘 시간 복잡도 적절성

①	선택정렬	O(N^2)	❌ 해당되지 않음
②	삽입정렬	최악: O(N^2), 최선: O(N)	❌ 해당되지 않음
③	버블정렬	O(N^2)	❌ 해당되지 않음
❹	합병정렬	O(Nlog2N)	✅ 맞는 알고리즘

---

📘 합병정렬(Merge Sort) 요약

• 시간 복잡도: O(Nlog2N)
• 특징:
  • 분할 정복 방식: 데이터를 절반으로 나누어 정렬한 후 합침
  • 안정적인 정렬 알고리즘: 데이터의 상대적인 순서를 유지
  • 비교 기반 정렬: 데이터를 비교하며 정렬
  • 공간 복잡도: 추가적인 배열이 필요하므로 **O(N)**의 공간 복잡도가 필요

---

🏁 결론 정리

항목 내용

문제 핵심	**O(Nlog2N)**의 시간 복잡도를 가지는 정렬 알고리즘은 무엇인가?
정답	✅ ❹ 합병정렬
이유	합병정렬은 **O(Nlog2N)**의 시간 복잡도를 가지는 분할 정복 방식의 정렬 알고리즘입니다.

---

🎯 암기 팁

💡 합병정렬의 특징

• 분할 정복: 데이터를 나누고, 각각 정렬 후 합침
• 시간 복잡도: O(Nlog2N)
• 안정성: 상대적인 데이터 순서를 유지하며 정렬
• 공간 복잡도: O(N) (추가 배열이 필요)

합병정렬은 시간 복잡도가 **O(Nlog2N)**로 효율적이며, 안정적인 정렬을 제공합니다.
 😊