정렬
0. 정렬을 왜 배워야 할까요?
메일 보관함의 시간순, 가장 가까운 거리 순등 많은 곳에서 정렬을 쓰고 있습니다. 이걸 조금 더 효율적으로 구현하기 위해 배우게 되는 것입니다.
1. 버블 정렬에 대해 설명해보세요.
서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 0번부터 n-1번의 인덱스까지 모두 접근하면서 인접한 값들의 대소 비교도 해야하므로 총
O(N^2)의 시간 복잡도가 걸립니다.
2. 선택 소트에 대해 설명해보세요.
정렬되지 않은 배열에서 최솟값을 선택해 정렬되지 않은 배열의 첫번째 인덱스에 넣어주는 알고리즘입니다. 0번부터 n-1번의 인덱스까지 모두 접근하면서 인덱스의 값들을 비교하면서 최소값을 넣어주는 작업도 해야하므로 총
O(N^2)의 시간 복잡도가 걸립니다.
3. 삽입 소트에 대해 설명해보세요.
2번째 원소부터 시작해서 그 왼쪽의 원소들과 비교 후 삽입할 위치를 지정한 후에 원소들을 뒤로 옮기고 해당 위치에 자료를 삽입하는 알고리즘입니다. 1번부터 n-1번까지의 모든 원소들을 탐색하면서 왼쪽의 원소들과 비교하며 자리 교대를 하기 때문에 총
O(N^2)의 시간 복잡도가 걸립니다.
4. 삽입 소트의 성능을 개선해보세요.
최적화를 통해 부분적으로 정렬된 배열에 대해서 성능을 개선할 수 있습니다. 새롭게 정렬해야하는 값보다 작은 숫자를 만나는 최초의 순간까지만 내부 반복문을 수행하면 됩니다. 이렇게 했을 때 완전히 정렬되어 있는 경우
O(N)까지 시간 복잡도를 향상시킬 수 있습니다.
5. 퀵 정렬에 대해 설명해보세요.
매우 빠른 속도를 자랑하는 분할 정복 알고리즘 중 하나로 머지소트와 달리 리스트를 비균등하게 분할합니다. 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬을 합니다. 총 시간복잡도는
O(NlogN)이 소요가 됩니다. 하지만, 최악의 경우O(N^2)의 시간이 소요됩니다.
6. 퀵 정렬의 시간 복잡도에 대해 설명해보세요.
피봇을 기준으로 파티셔닝을 진행할 때
O(N)의 시간이 소요되고, 중앙값을 피봇으로 설정했다면 절반씩 배열이 1이 될 때까지 logN번을 쪼개게 됩니다. 그래서 총 시간복잡도는O(NlogN)이 소요가 됩니다. 하지만, 최악의 경우 피봇을 최소, 최대 값으로 설정을 했다면O(N^2)의 시간이 소요됩니다.
7. 머지 소트에 대해 설명해보세요.
주어진 배열을 크기가 1인 배열이 될 때까지 분할하고 다시 합병하면서 정렬을 진행하는 알고리즘입니다. 이때 합병할 때는 2개의 리스트를 서로 비교하면서 더 작은 값을 새로운 리스트로 옮기면서 진행합니다. 시간 복잡도는
O(NlogN)이 걸립니다.
8. 머지 소트의 시간 복잡도에 대해 설명해보세요.
분할하는 과정에서는 함수 호출만 진행되므로 신경쓰지 않아도 됩니다. 정렬된 2개의 배열을 합치는 과정에서 양쪽 배열의 길이를 합친만큼 비교 연산을 하게 되고, 이때
O(N)의 시간이 소요됩니다. 또 배열을 합치는 과정은 배열을 계속 반으로 나눈 만큼 합쳐야 하므로 logN번을 수행해야합니다. 따라서, 총 시간 복잡도는O(NlogN)이 걸리게 됩니다.
9. 퀵 소트와 머지 소트의 차이점에 대해 설명해보세요.
퀵 소트는 피봇을 이용해서 정렬하면서 영역을 쪼갠다면, 머지 소트는 영역을 쪼갤 수 있을만큼 쪼갠 뒤에 정렬을 진행합니다.
10. 힙 소트에 대해 설명해보세요.
주어진 데이터를 힙 자료구조로 만들어 최대값 또는 최소값부터 하나씩 꺼내서 정렬하는 알고리즘입니다. 가장 유용한 경우는 전체를 정렬하는게 아니라 가장 큰 값 또는 가장 작은 값 몇개를 필요로 하는 경우입니다. 시간 복잡도는
O(NlogN)이 걸립니다.
11. 힙 소트의 시간 복잡도에 대해 설명해보세요.
하나의 노드를 삽입하거나 삭제했을 때 힙 규칙을 유지하도록 바꾸는 작업은
O(logN)의 시간이 걸리게 됩니다. 이진 트리의 높이만큼 반복하기 때문입니다. 힙 정렬은 최악의 경우 N개의 자료를 삽입/삭제 해야합니다. 따라서 총 시간 복잡도는O(NlogN)의 시간이 걸립니다.
12. 최대 힙의 삽입 과정에 대해 설명해보세요.
힙에 새로운 자료가 들어오게 되면 힙의 마지막 노드에 이어서 삽입합니다. 새로운 노드가 부모 노드보다 크게 된다면 자리 교대(swap)를 하는 방법을 반복해서 힙의 성질을 만족할 때까지 합니다.
13. 최대 힙의 삭제 과정에 대해 설명해보세요.
최대 힙에서 최댓값은 루트 노드이므로 먼저 루트 노드를 삭제합니다. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옵니다. 삽입 노드와 자식 노드를 비교하며 자식 노드 중 더 큰 값과 교환을 반복해 힙의 성질을 만족할 때까지 합니다.
