32. 정렬된 N개의 데이터를 처리하는 데 O(Nlog2N)의 시간이 소요되는 정렬 알고리즘은?
❶ 합병정렬 ② 버블정렬
③ 선택정렬 ④ 삽입정렬
이 문제는 O(N log N) 시간 복잡도를 갖는 정렬 알고리즘을 묻고 있습니다.
각각의 정렬 알고리즘에 대해 시간 복잡도를 알아보겠습니다:
① 합병정렬 (Merge Sort)
- 시간 복잡도: 합병정렬은 분할 정복 방식의 알고리즘으로, 주어진 배열을 반으로 나누어 각각 정렬한 후 병합하는 방식입니다.
- 시간 복잡도는 **O(N log N)**입니다.
- 설명: 배열을 반으로 나누는 데 O(log N)의 시간이 걸리고, 나눈 배열을 합치는데 O(N)의 시간이 걸리므로 총 시간 복잡도는 **O(N log N)**입니다.
- 결론: 합병정렬은 O(N log N)의 시간 복잡도를 가집니다.
② 버블정렬 (Bubble Sort)
- 시간 복잡도: 버블정렬은 인접한 두 원소를 비교하고 교환하는 방식으로 정렬합니다.
- 시간 복잡도는 **O(N²)**입니다.
- 설명: 매번 비교하고 교환하는 작업이 최악의 경우 O(N)번씩 이루어지기 때문에 총 시간 복잡도는 **O(N²)**입니다.
- 결론: 버블정렬은 **O(N²)**의 시간 복잡도를 가집니다.
③ 선택정렬 (Selection Sort)
- 시간 복잡도: 선택정렬은 배열에서 가장 작은 값을 찾아 맨 앞의 값과 교환하는 방식입니다.
- 시간 복잡도는 **O(N²)**입니다.
- 설명: 선택정렬은 전체 배열에서 최소값을 찾는데 O(N) 시간이 걸리고, 이를 반복하므로 총 시간 복잡도는 **O(N²)**입니다.
- 결론: 선택정렬은 **O(N²)**의 시간 복잡도를 가집니다.
④ 삽입정렬 (Insertion Sort)
- 시간 복잡도: 삽입정렬은 배열을 순차적으로 탐색하며 각 원소를 이미 정렬된 부분에 적절한 위치에 삽입하는 방식입니다.
- 시간 복잡도는 **O(N²)**입니다.
- 설명: 최악의 경우 각 원소를 삽입할 때 O(N) 시간이 걸리며, 이를 N번 반복하므로 총 시간 복잡도는 **O(N²)**입니다.
- 결론: 삽입정렬은 **O(N²)**의 시간 복잡도를 가집니다.
결론
O(N log N) 시간 복잡도를 가지는 정렬 알고리즘은 **합병정렬 (Merge Sort)**입니다.
따라서 정답은 ① 합병정렬입니다.
'기출문제 > 정보처리기사' 카테고리의 다른 글
2021년 2회 정보처리기사 기출문제 34번 (0) | 2025.03.22 |
---|---|
2021년 2회 정보처리기사 기출문제 33번 (0) | 2025.03.22 |
2021년 2회 정보처리기사 기출문제 31번 (0) | 2025.03.22 |
2021년 2회 정보처리기사 기출문제 30번 (0) | 2025.03.22 |
2021년 2회 정보처리기사 기출문제 29번 (0) | 2025.03.22 |