학습개요
지난 시간에 배운 기본적인 형태의 정렬 알고리즘에 비해서 향상된 성능을 가진 퀵 정렬과 합병 정렬에 대해서 학습한다. 그리고 저장된 데이터에 대해서 원하는 데이터를 찾는 탐색의 다양한 방법들의 개념, 동작, 그리고 특징을 살펴본다.
학습목표
- 퀵 정렬과 합병 정렬의 개념, 동작, 그리고 특징을 이해할 수 있다.
- 순차 탐색과 이진 탐색의 개념, 동작, 그리고 특징을 이해할 수 있다.
- 이진 탐색 트리의 개념, 연산(탐색, 삽입, 삭제), 그리고 성능을 이해할 수 있다.
연습문제
- 퀵 정렬에 대한 설명으로 틀린 것은?
- 항상 동일한 크기의 두 부분배열로 분할된다.
- 분할정복 방법을 적용하였다.
- 최악의 시간 복잡도는 O(n2)이다.
- 최선 수행 시간은 O(nlogn)이다.
정답 : 1① → 합병 정렬에 대한 설명이다. 퀵 정렬은 피벗이라는 특정 데이터를 기준으로 분할하기 때문에 왼쪽과 오른쪽 부분배열의 크기가 일정하지 않다.
- 주어진 데이터에 대해 퀵 정렬의 분할 과정을 한 번 적용한 후의 왼쪽 부분배열의 첫 번째 데이터는?(단, 배열의 첫 번째 원소를 피벗으로 사용한다.)
35 26 15 77 10 61 11 59 17 48 19 40 - 10
- 11
- 15
- 17
정답 : 2❒ 주어진 데이터에 대해서 두 부분배열로 분할하는 과정은 다음과 같다.
- 합병 정렬 알고리즘의 합병(merge) 과정에 입력으로 주어지는 두 부분배열 X, Y는 어떠한 상태이어야 하는가?
- X의 모든 원소는 Y의 최소 원소보다 작은 값이어야 한다.
- X의 모든 원소는 Y의 최대 원소보다 큰 값이어야 한다.
- X, Y 각각 제 순서로 정렬되어 있어야 한다.
- X는 제 순서, Y는 역순으로 정렬되어 있어야 한다.
정답 : 3❒ 동일한 크기로 분할된 두 부분배열이 각각 정렬된 상태로 합병 과정의 입력으로 주어지면, 각 부분배열의 원소를 앞에서부터 하나씩 서로 비교해서 작은 값을 우선 취해서 정렬된 부분에 포함시키는 방식으로 합병이 이루어진다.
- 순차 탐색과 이진 탐색에 대한 설명으로 올바른 것은?
- 이진 탐색에서는 빈번한 데이터의 삽입과 삭제의 처리가 효율적이다.
- 순차 탐색의 최악의 수행 시간은 O(logn)이다.
- 이진 탐색은 데이터가 정렬되지 않은 경우에 적합하다.
- 순차 탐색은 정렬된 리스트에 적용할 수 있다.
정답 : 4① 이진 탐색에서는 삽입/삭제 시 정렬 상태를 유지하기 위해 데이터의 이동이 발생하므로, 삽입/삭제가 빈번한 응용에는 부적합하다.
② 순차 탐색과 이진 탐색의 성능은 각각 O(n)과 O(logn)이다.
③ 순차 탐색은 데이터가 정렬되지 않은 경우에 적합하다.
④ 순차 탐색은 모든 리스트에 적용 가능하므로, 정렬된 리스트에도 적용할 수 있다.
- 이진 탐색 트리에서 노드 30의 후속자 노드의 키값은?
- 7
- 15
- 22
- 35
정답 : 4❒ 어떤 노드의 바로 다음 키값을 갖는 노드를 후속자(successor) 노드라고 한다.
- 이진 탐색 트리의 탐색 과정에 대한 최악의 시간 복잡도와 평균 시간 복잡도가 올바르게 짝지어진 것은?
- O(n) – O(logn)
- O(nlogn) – O(n)
- O(n) – O(n)
- O(nlogn) – O(logn)
정답 : 1❒ 이진 탐색 트리의 평균 탐색 시간은 O(logn)이지만, 이미 정렬된 순서로 데이터가 입력되어 경사 트리를 형성하는 경우에는 최악의 시간 복잡도 O(n)을 갖는다.
정리하기
- 정렬 알고리즘: 퀵 정렬과 합병 정렬
- 퀵 정렬 → 특정 데이터를 기준으로 주어진 입력 배열을 두 개의 부분배열로 분할하고, 각 부분배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용하는 방법 → 피벗이 제자리를 잡도록 정렬하는 방식
- 분할정복을 적용한 알고리즘
- 피벗 → 두 개의 부분배열로 분할할 때 기준이 되는 데이터 → 보통 배열의 첫 번째 원소를 피벗으로 지정
- 분할 과정 → 퀵 정렬의 가장 핵심 부분 → 피벗을 중심으로 두 부분배열로 분할하는 과정 → O(n)
- 최선의 수행 시간 → 피벗을 중심으로 동일한 크기의 두 개의 부분배열로 분할되는 경우 → O(nlogn)
- 최악의 수행 시간 → 피벗 하나만 제자리를 잡고, 나머지 모든 데이터가 하나의 부분배열로 분할되는 경우 → 피벗이 배열에서 항상 최대값이나 최소값이 되는 경우 → 입력 데이터가 이미 정렬되어 있고, 배열의 맨 왼쪽 원소를 피벗으로 사용하는 경우 → O(n2)
- 평균 수행 시간 → O(nlogn) → 피벗 선택의 임의성만 확보되면 최악의 수행 시간이 아닌 평균 수행 시간이 보장됨
.
- 합병 정렬 → 동일한 크기의 두 개의 부분배열로 분할하고, 각 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 리스트를 형성하는 방식
- 분할정복을 적용한 알고리즘
- 합병 과정 → 정렬된 두 부분배열을 입력으로 받아 하나의 정렬된 배열로 만드는 과정
- 최선/평균/최악 수행 시간 → O(nlogn)
.
- 퀵 정렬 → 특정 데이터를 기준으로 주어진 입력 배열을 두 개의 부분배열로 분할하고, 각 부분배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용하는 방법 → 피벗이 제자리를 잡도록 정렬하는 방식
- 순차 탐색과 이진 탐색
- 순차 탐색 → 리스트 형태로 주어진 데이터를 처음부터 하나씩 차례대로 비교하여 원하는 값을 가진 데이터를 찾는 방법
- 모든 리스트(배열, 연결 리스트)에 적용 가능, 특히 데이터가 정렬되지 않은 경우에 적합
- O(n)
.
- 이진 탐색 → 정렬된 입력 배열에 대해서 주어진 데이터를 절반씩 줄여가면서 원하는 데이터를 찾는 방법
- 분할정복을 적용한 알고리즘
- 주어진 배열의 가운데 데이터의 값과 탐색키를 비교 →
① ‘탐색키 = 배열의 가운데 값’이면 탐색 성공,
② ‘탐색키 < 배열의 가운데 값’이면 주어진 배열의 전반부를 탐색 범위로 재지정 한 후 이진 탐색을 순환 호출,
③ ‘탐색키 > 배열의 가운데 값’이면 주어진 배열의 후반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출 → 탐색을 한 번 수행할 때마다 탐색 대상이 되는 원소의개수가 절반씩 감소 - O(logn)
- 빈번한 삽입/삭제가 있는 응용에는 부적합 → 정렬 상태 유지를 위한 데이터 이동으로 인해 오버헤드 발생
.
- 순차 탐색 → 리스트 형태로 주어진 데이터를 처음부터 하나씩 차례대로 비교하여 원하는 값을 가진 데이터를 찾는 방법
- 이진 탐색 트리
- 이진 탐색 트리 → 각 노드 x의 왼쪽 서브트리의 모든 키값은 x의 키값보다 작고, 오른쪽 서브트리의 모든 키값은 x의 키값보다 크다는 조건을 만족시키는 이진 트리
- 탐색 연산 → 루트 노드로부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 원하는 키값을 갖는 원소를 찾음
- 삽입 연산 → 삽입할 원소를 탐색한 후, 탐색이 실패한 지점의 왼쪽/오른쪽 자식 노드를 생성하여 추가
- 삭제 연산 → 삭제되는 자식 노드의 개수에 따라 3가지 경우로 구분해서 처리
- 자식 노드가 없는 경우 → 남은 노드의 위치 조절이 불필요
- 자식 노드가 하나인 경우 → 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다.
- 자식 노드가 두 개 모두 있는 경우: 후속자 노드(어떤 노드의 바로 다음 키값을 갖는 노드)를 삭제되는 노드의 위치로 올리고, 후속자 노드의 자식 노드의 개수에 따라 다시 삭제 연산을 처리
- 성능
- 평균 탐색 시간 → O(logn) → 리프 노드를 제외한 모든 노드의 차수가 2인 경우
- 최악 탐색 시간 → O(n) → 경사 이진 트리, 즉 리프 노드를 제외한 모든 노드의 차수가 1인 경우