Chapter 13. 속도를 높이는 재귀 알고리즘

♧ Self-study/<누구나 자료구조와 알고리즘>

Chapter 13. 속도를 높이는 재귀 알고리즘

Grit_0913 2024. 9. 11. 19:07

Chapter 13. 속도를 높이는 재귀 알고리즘

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 분할
2. 퀵 정렬
3. 퀵 정렬의 효율성
4. 퀵 셀렉트
5. 다른 알고리즘의 핵심 역할을 하는 정렬
6. 연습 문제 정리

대부분의 컴퓨터 언어는 퀵 정렬(Quicksort)을 내장 정렬 함수로 사용한다.
- 버블 정렬, 선택 정렬, 삽입 정렬 등 많은 알고리즘을 배웠으나 실질적으로 배열 정렬에는 사용하지 않는다.
퀵 정렬이 내장 정렬 함수로 사용되는 이유는 퀵 정렬의 평균 빅 오가 가장 효율적인 시간 복잡도이기 때문이다.
- 최악의 경우에 해당하는 빅 오는 삽입 정렬, 그리고 선택 정렬과 유사하다.
퀵 정렬은 분할(partitioning)이라는 개념에 기반한다.

1. 분할

분할은 일종의 정렬방식이다.
- 분할은 첫 번째로 배열 내에서 임의의 수(원소)를 선택한다. 이때 선택된 수는 피벗(pivot)이라 한다.
- 그 다음 피벗보다 작은 수는 비벗의 왼쪽에, 큰 수는 오른쪽에 배치되도록 정렬한다.
분할의 수행
- step 1 : 두 개의 포인터를 사용한다.
  - 왼쪽 포인터는 배열의 가장 왼쪽 값에서 시작한다.
  - 오른쪽 포인터는 피벗을 제외한 배열의 가장 오른쪽 값에서 시작한다.
- step 2 : 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기며 피벗과 비교한다.
  - 'Left pointer >= pivot'인 값에 도달하면 멈춘다.
- step 3 : 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기며 피벗과 비교한다.
  - 'Right pointer <= pivot'인 값에 도달하면 멈춘다.
  - 혹은 배열의 첫 번째 값(index = 0)에 도달하면 멈춘다.
- step 4 : 오른쪽 포인터가 멈춘 경우 다음 중 하나를 수행한다.
  - 왼쪽 포인터와 오른쪽 포인터가 동일한 셀인 경우 포인터가 가리키는 셀의 값과 피벗의 값을 교환한다.
  - 이외의 모든 경우에는 왼쪽 포인터와 오른쪽 포인터의 값을 교환한 뒤 step 1 ~ step 3의 과정을 반복한다.
분할이 완료된 시점에서 배열이 정렬되는 것은 아니다. 그러나 피벗 자체는 올바른 위치에 위치하게 된다. (피벗 왼쪽은 모두 피벗 보다 작거나 같고, 오른쪽 값은 피벗 보다 크거나 같다).
교재의 분할 코드 python 변환

class SortableArray:
    def __init__(self, array):
        self._array = array

    def partition(self, left_pointer, right_pointer):
        # 항상 가장 오른쪽에 있는 값을 피벗으로 선택한다.
        # 나중에 사용할 수 있도록 피벗의 인덱스를 저장한다.
        pivot_index = right_pointer
        
        # 피벗 값을 저장해 둔다.
        pivot = self._array[pivot_index]
        
        # 피벗 바로 왼쪽에서 오른쪽 포인터를 시작시킨다.
        right_pointer -= 1
        
        while True:
            # 피벗보다 크거나 같은 값을 가리킬 때까지
            # 왼쪽 포인터를 오른쪽으로 옮긴다.
            while self._array[left_pointer] < pivot:
                left_pointer += 1
            
            # 피벗보다 작거나 같은 값을 가리킬 때까지
            # 오른쪽 포인터를 왼쪽으로 옮긴다.
            while self._array[right_pointer] > pivot:
                right_pointer -= 1
            
            # 이제 왼쪽 포인터와 오른쪽 포인터 모두 이동을 멈췄다.
            # 왼쪽 포인터가 오른쪽 포인터에 도달했으니 넘어섰는지 확인한다.
            # 그렇다면 로프를 빠져 나가 이후 코드에서 피벗을 교환한다.
            if left_pointer >= right_pointer:
                break
            
            # 왼쪽 포인터가 오른쪽 포인터보다 앞에 있으면
            # 왼쪽 포인터와 오른쪽 포인터의 값을 교환한다.
            else:
                self._array[left_pointer], self._array[right_pointer] = \
                    self._array[right_pointer], self._array[left_pointer]
                
                # 다음 번 왼쪽 포인터와 오른쪽 포인터의 이동을 위해
                # 왼쪽 포인터를 오른쪽으로 옮긴다.
                left_pointer += 1
        
        # 분할의 마지막 단계로 왼쪽 포인터의 값과 피벗을 교환한다.
        self._array[left_pointer], self._array[pivot_index] = \
            self._array[pivot_index], self._array[left_pointer]
        
        # 이어지는 예제에 나올 quicksort 메서드를 위해 left_pointer를 반환한다.
        return left_pointer

2. 퀵 정렬

퀵 정렬 알고리즘은 분할과 재귀로 이루어진다.
퀵 정렬의 수행
- step 1 : 배열을 분할한다. (즉 피벗은 올바른 위치에 위치된다).
- step 2 : 피벗을 중심으로 왼쪽과 오른쪽 영역을 하위 배열로 여긴다.
- step 3 : 각 하위 배열(왼쪽 + 오른쪽)에 분할을 수행한다.
- step 4 : step 1 ~ step 3의 과정을 전체 배열에 반복한다.
- step 5 : 하위 배열의 원소의 수가 0 혹은 1이 되는 경우 정렬이 완료된다. (기저 조건이기도 하다).
교재의 퀵 정렬 코드 구현 및 분할 클래스(SortableArray)에 추가 코드 python 변환

class SortableArray:
    def __init__(self, array):
        self._array = array

    def partition(self, left_pointer, right_pointer):
        # 항상 가장 오른쪽에 있는 값을 피벗으로 선택한다.
        # 나중에 사용할 수 있도록 피벗의 인덱스를 저장한다.
        pivot_index = right_pointer
        
        # 피벗 값을 저장해 둔다.
        pivot = self._array[pivot_index]
        
        # 피벗 바로 왼쪽에서 오른쪽 포인터를 시작시킨다.
        right_pointer -= 1
        
        while True:
            # 피벗보다 크거나 같은 값을 가리킬 때까지
            # 왼쪽 포인터를 오른쪽으로 옮긴다.
            while self._array[left_pointer] < pivot:
                left_pointer += 1
            
            # 피벗보다 작거나 같은 값을 가리킬 때까지
            # 오른쪽 포인터를 왼쪽으로 옮긴다.
            while self._array[right_pointer] > pivot:
                right_pointer -= 1
            
            # 이제 왼쪽 포인터와 오른쪽 포인터 모두 이동을 멈췄다.
            # 왼쪽 포인터가 오른쪽 포인터에 도달했으니 넘어섰는지 확인한다.
            # 그렇다면 로프를 빠져 나가 이후 코드에서 피벗을 교환한다.
            if left_pointer >= right_pointer:
                break
            
            # 왼쪽 포인터가 오른쪽 포인터보다 앞에 있으면
            # 왼쪽 포인터와 오른쪽 포인터의 값을 교환한다.
            else:
                self._array[left_pointer], self._array[right_pointer] = \
                    self._array[right_pointer], self._array[left_pointer]
                
                # 다음 번 왼쪽 포인터와 오른쪽 포인터의 이동을 위해
                # 왼쪽 포인터를 오른쪽으로 옮긴다.
                left_pointer += 1
        
        # 분할의 마지막 단계로 왼쪽 포인터의 값과 피벗을 교환한다.
        self._array[left_pointer], self._array[pivot_index] = \
            self._array[pivot_index], self._array[left_pointer]
        
        # 이어지는 예제에 나올 quicksort 메서드를 위해 left_pointer를 반환한다.
        return left_pointer
    
    # 퀵 정렬 추가-----------------------------------------------------------
    def quicksort(self, left_index, right_index):
        # 기저 조건: 하위 배열에 원소가 0개 또는 1개일 때
        if right_index - left_index <= 0:
            return
    
        # 범위 내 원소들을 분할하고 피벗의 인덱스를 가져온다.
        pivot_index = self.partition(left_index, right_index)
    
        # 피벗 왼쪽에 대해 quicksort 메서드를 재귀적으로 호출한다.
        self.quicksort(left_index, pivot_index - 1)
    
        # 피벗 오른쪽에 대해 quicksort 메서드를 재귀적으로 호출한다.
        self.quicksort(pivot_index + 1, right_index)

교재의 퀵 정렬 테스트 코드 python 변환. (그대로 실행하면 결과를 확인할 수 있다).

array = [0, 5, 2, 1, 6, 3]
sortable_array = SortableArray(array)
sortable_array.quicksort(0, len(array) - 1)
print(sortable_array._array)

3. 퀵 정렬의 효율성

퀵 정렬의 분할에 필요한 단계는 다음 두 가지이다.
- 비교 : 각 포인터의 값과 피벗의 값을 비교한다.
  - 한 번의 분할에서는 오른쪽 포인터와 왼쪽 포인터가 만날 때까지 피벗과 비교를 한다. 따라서 최악의 경우 전체 $N$ 번 비교를 하게 된다.
- 교환 : 필요 시 포인터의 값을 교환한다.
  - 한 번의 분할에서 교환은 두 개의 값을 대상으로 수행된다. 따라서 최악의 경우 $N\over 2$ 번의 교환이 수행된다.
  - 최악의 경우가 아닌 일반적인 경우를 가정하면 $N\over 4$ 번의 교환이 수행된다.
퀵 정렬의 전체 단계를 고려하면 비교($N$) + 교환($N\over 4$) = $1.25N$이 된다. 빅 오로 표현하면 $O(N)$이 된다.
퀵 정렬의 평균적인 빅 오는 약 $O(NlogN)$이 된다. (p277 참고).
- $logN$ : 크기가 $N$인 배열을 크기가 1이 될 때까지 하위 배열로 나누는 것을 반복하면 logN 번이 걸린다.
- $N$ : 하위 배열의 원소의 수를 모두 합하면 $N$이 된다.
퀵 정렬은 최악의 경우(오름차순 혹은 내림차순 정렬된 경우) 각 분할마다 교환은 1 번 수행되지만 비교 단계가 너무 많아지기에 비효율적이다.
- 피벗이 한 셀씩 이동하기에 $N$ 개의 원소의 경우 $N + (N-1) + (N-2) + ... + 1 = {N^2\over 2}$가 된다. 빅 오는 $O(N^2)$ 이다.
퀵 정렬이 내장함수로 사용되는 이유는 평균적으로 가장 효율적인 알고리즘이기 때문이다.

4. 퀵 셀렉트

퀵 셀렉트(Quickselect)는 퀵 정렬과 이진 검색의 하이브리드라 볼 수 있다.
- 만약 전체를 정렬할 필요 없이 n 번째로 작은 값을 찾는 문제의 경우 굳이 모든 값을 정렬할 필요가 없다. 즉, 퀵 정렬이 비효율적이며 이와 같은 경우에 퀵 셀렉트를 활용할 수 있다.
왜 퀵 셀렉트가 효율적인가?
- n 번째로 작은 값을 찾을 때에는 1 회 분할을 수행한 뒤 피벗의 왼쪽 하위 배열만 분할하면 된다. (오른쪽은 피벗보다 크기에 의미가 없다).
- 따라서 기존의 퀵 정렬보다 효율적으로 작동하며 전체 배열을 정렬하지 않고도 원하는 값을 찾을 수 있다.
퀵 셀릭트의 평균적인 빅 오는 $O(N)$ 이다.
- 각 분할마다 하위 배열에서 해당 배열의 원소의 수(N)만큼 단계가 필요하다.
- 일반적으로 한 쪽의 하위 배엶나 분할하면 되기 때문에 각 분할 단계는 $N\over 2$가 된다.
- 따라서 퀵 셀렉트의 총 단계는 $N + {N\over 2} + {N\over 4} + {N\over 8} + ... + 2 = 2N$ 이다. 빅 오는 $O(N)$이 된다.
교재의 퀵 셀렉트 코드 구현 및 적용 python 변환. (분할 클래스 SortableArray에 연결하여 사용).

class SortableArray:
    def __init__(self, array):
        self._array = array

    def partition(self, left_pointer, right_pointer):
        pivot_index = right_pointer
        pivot = self._array[pivot_index]
        right_pointer -= 1
        
        while True:
            while self._array[left_pointer] < pivot:
                left_pointer += 1
            
            while self._array[right_pointer] > pivot:
                right_pointer -= 1
            
            if left_pointer >= right_pointer:
                break
            
            self._array[left_pointer], self._array[right_pointer] = \
                self._array[right_pointer], self._array[left_pointer]
            
            left_pointer += 1
        
        self._array[left_pointer], self._array[pivot_index] = \
            self._array[pivot_index], self._array[left_pointer]
        
        return left_pointer

# 퀵 셀렉트 추가--------------------------------------------------------------
    def quickselect(self, kth_lowest_value, left_index, right_index):
        # 기저 조건이면, 즉 하위 배열에 셀이 하나면 찾고 있던 값을 찾은 것이다.
        if right_index - left_index <= 0:
            return self._array[left_index]
        
        # 배열을 분할하고 피벗의 위치를 가져온다.
        pivot_index = self.partition(left_index, right_index)
        
        # 찾고 있는 값이 피벗 왼쪽에 있으면
        if kth_lowest_value < pivot_index:
            # 피벗 왼쪽의 하위 배열에 대해
            # 재귀적으로 퀵 셀렉트를 수행한다.
            return self.quickselect(kth_lowest_value, left_index, pivot_index - 1)
        # 찾고 있는 값이 피벗 오른쪽에 있으면
        elif kth_lowest_value > pivot_index:
            # 피벗 오른쪽의 하위 배열에 대해
            # 재귀적으로 퀵 셀렉트를 수행한다.
            return self.quickselect(kth_lowest_value, pivot_index + 1, right_index)
        else: # kth_lowest_value == pivot_index
            # 분할 후 피벗의 인덱스가 k번째 작은 값의 인덱스와 같으면
            # 찾고 있던 값을 찾은 것이다. 
            return self._array[pivot_index]

교재의 테스트 코드 python 변환. (그대로 수행하여 결과를 확인할 수 있다).

array = [0, 50, 20, 10, 60, 30]
sortable_array = SortableArray(array)
result = sortable_array.quickselect(1, 0, len(array) - 1)
print(result)

5. 다른 알고리즘의 핵심 역할을 하는 정렬

교재에서 등장한 병합 정렬(Merge sort) 링크
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

중복 체크 알고리즘을 예로 들면 일반적으로 $O(N^2)$가 필요하다.
- 그러나 배열을 먼저 정렬한 뒤 중복 검사를 수행하면 빅 오는 $O(NlogN)$이 된다.
- $NlogN$(퀵 정렬) + $N$(중복검사) = $O(NlogN)$ (최고차항만 남기 때문).
위처럼 알고리즘을 개선할 수 있으며 항상 퀵 정렬 $O(NlogN)$이 기준이 된다.

6. 연습 문제 정리

1 번

def greatest_product_of_3(array):
    # 배열을 오름차순 정렬
    array.sort()
    
    # 오름차순 정렬된 배열의 마지막 세 개의 원소를 곱
    return array[-1] * array[-2] * array[-3]

2 번

def find_missing_number(array):
    # 배열을 오름차순 정렬
    array.sort()
    
    # 오름차순 정렬된 상태라면 
    # index와 정렬된 수는 동일해야 함. 
    # 하나의 숫자를 반환하는 문제이기 때문에 
    # index와 일치하지 않으면 해당 수만 제외되어 있는 것
    for i in range(len(array)):
        if array[i] != i:
            return i

    return len(array)

3 번

$O(N^2)$

def max(array):
    for i in range(len(array)):
        iIsGreatestNumber = True
        
        # 모든 원소를 하나씩 비교한다. O(N^2)
        # array[i]가 array[j]보다 크다는 것은
        # 해당 수가 모든 원소들 보다 크다는 것을 의미한다.
        for j in range(len(array)):
            if array[j] > array[i]:
                iIsGreatestNumber = False
        
        # iIsGreatestNumber가 True인 경우 array[i]를 반환
        if iIsGreatestNumber:
            return array[i]

$O(NlogN)$

def max(array):
    # python의 sort()를 통한 정렬은 
    # 정확히는 퀵 정렬은 아니지만
    # O(NlogN)이 걸린다.
    array.sort()
    return array[-1]

$O(N)$

def max(array):
    greatestNumberSoFar = array[0]
    
    # greatestNumberSoFar 변수에 값을 초기화하며(저장) 진행한다.
    # 따라서 한 번만 배열을 순회하면 최대값을 얻을 수 있다. O(N).
    for i in range(len(array)):
        if array[i] > greatestNumberSoFar:
            greatestNumberSoFar = array[i]
            
    return greatestNumberSoFar

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

Chapter 15. 이진 탐색 트리로 속도 향상 (2)	2024.09.17
Chapter 14. 노드 기반 자료 구조 (0)	2024.09.14
Chapter 12. 동적 프로그래밍 (0)	2024.09.10
Chapter 11. 재귀적으로 작성하는 법 (0)	2024.09.09
Chapter 10. 재귀를 사용한 재귀적 반복 (2)	2024.08.31

현재글Chapter 13. 속도를 높이는 재귀 알고리즘

Grit

Grit 입니다.

order by, 자료 구조 알고리즘 (ds & algo), concat, date_format, GROUP BY, date, 회귀분석 (regression), TIMESTAMPDIFF, 알고리즘, AVG, 프로그래머스 알고리즘, SUM, year, like, R, 머신러닝 (machine learning), Round, SQL 코딩테스트, 태블로 (Tableau), Limit, count, split(), INNER JOIN, Having, SELF JOIN, 통계 검정 (statistical test), subquery, CASE WHEN, 경영정보시각화, where,

Today :
Yesterday :

Grit

Chapter 13. 속도를 높이는 재귀 알고리즘

Chapter 13. 속도를 높이는 재귀 알고리즘

1. 분할

2. 퀵 정렬

3. 퀵 정렬의 효율성

4. 퀵 셀렉트

5. 다른 알고리즘의 핵심 역할을 하는 정렬

6. 연습 문제 정리

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

티스토리툴바

« 2025/06 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Chapter 13. 속도를 높이는 재귀 알고리즘

Chapter 13. 속도를 높이는 재귀 알고리즘

1. 분할

2. 퀵 정렬

3. 퀵 정렬의 효율성

4. 퀵 셀렉트

5. 다른 알고리즘의 핵심 역할을 하는 정렬

6. 연습 문제 정리

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

관련글

티스토리툴바