[동빈나]이코테 2021 강의 몰아보기(7)(2021.1.6)

본 내용은 해당 강의 토대로 작성

정렬 알고리즘

• 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 문제 상황에 따라 정렬 알고리즘이 공식처럼 사용

1. 선택 정렬

• 처리되지 않은 데이터 중 가장 작은 데이터를 선택 후 맨 앞에 있는 데이터와 바꾸는 것을 반복
• 이중 반복문으로 구현

선택 정렬 동작 예시

1. 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 가장 앞의 데이터와 바꾼다.
2. 이러한 동작을 반복한다.

선택 정렬 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)): 0 ~ 9
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]: # 선형 탐색
            min_index = j # 작은 값을 넣어주기
    array[i], array[min_index] = array[min_index], array[i] # 바꾸기

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 출력

선택 정렬 시간 복잡도

• N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.
• N + (N - 1) + (N - 2) + … + 2
• 빅오 표기법으로는 O(N²)

2. 삽입 정렬

• 처리 되지 않은 데이터를 적절한 위치에 삽입
• 구현난이도가 높지만, 더 효율적으로 동작한다.

삽입 정렬 동작 예시

1. 첫 번째 데이터는 그 자체로 정렬이 되어있다고 판단하고 다음 데이터가 첫 번재 데이터의 어느 위치로 들어갈지 결정한다.
2. 이러한 동작을 반복한다.

삽입 정렬 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복
        if array[j] < array[j - 1]: # 한 칸 씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 멈춤
            break
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 출력

삽입 정렬의 시간 복잡도

• O(N²)
• 현재 리스트의 데이터가 거의 정렬 되어 있으면, 매우 빠르게 동작
  • 최선 O(N)

3. 퀵 정렬

• 기준 데이터를 설정 후 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
• 일반적인 상황에서 가장 많이 사용
• 병합 정렬과 함께 대부분 프로그래밍 언어의 정렬 라이브러리의 근간
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정

퀵 정렬 동작 예시

1. 피벗의 값을 기준으로 왼쪽에서부터 피벗보다 큰 값을, 오른쪽에서부터 피벗보다 작은 값을 각각 고른다.
2. 선택된 두 값의 위치를 바꿔준다.
3. 반복한다.
4. 왼쪽이 작은 값, 오른쪽이 큰 값이 선택되면(위치가 엇갈림) 피벗과 작은 데이터의 위치를 서로 변경한다.
5. 피벗 값이 중간으로 가게 되고 피벗을 기준으로 데이터 묶음이 나뉜다.(분할)
6. 왼쪽 데이터 묶음과 오른쪽 데이터 묶음 각각 정렬을 수행한다.(재귀적)
7. 이러한 과정을 반복하면 전체 데이터에 대해 정렬 완료

퀵 정렬의 시간 복잡도

• 퀵 정렬이 빠른 이유
  • 이상적인 경우, 분할이 절반씩 일어나 O(NlogN) 시간 복잡도를 가진다.
• 최악의 경우 O(N²)의 시간 복잡도를 가진다.
  • 피벗값에 의존하여 편향된 분할이 발생 가능
  • 이미 정렬된 배열에 대해서 수행할 때

퀵 정렬 소스코드

일반적인 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

python의 장점을 살린 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

4. 계수 정렬

• 특정 조건에서 사용할 수 있다
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
• 매우 빠르게 동작
• 수행 시간 O(N + K)보장

계수 정렬 동작 예시

1. 가장 작은 데이터부터 큰 데이터까지 범위가 모두 담길 수 있도록 리스트 생성
2. 데이터를 확인하며 값과 동일한 인덱스의 데이터를 증가시킨다.
3. 결과 확인 시에는 리스트의 처음부터 하나씩 값만큼 반복하여 인덱스를 출력한다.

계수 정렬 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array)+ 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=" ") # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력 0 0 1 1 2 2 3 4 5 5 5 6 7 8 9 9

계수 정렬의 시간 복잡도

• O(N + K)

• 때에 따라서 심각한 비효율성을 초래

  • 0과 999,999인 경우

• 동일한 값을 가지는 데이터가 여래 개 등장할 때 효과적으로 사용

5. 정렬 알고리즘 비교

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N2)	O(N)	아이디어가 간단
삽입 정렬	O(N2)	O(N)	데이터가 거의 정렬되었을 때, 가장 빠르다.
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합, 충분히 빠르다.
계수 정렬	O(N + K)	O(N + K)	데이터의 크기가 한정되어 있는 경우에만 사용한다. 매우 빠르다.

• 표준 정렬 라이브러리는 O(NlogN)을 보장
  • sort 함수

6. 정렬 기초 문제 풀이

<문제> 두 배열의 원소 교체

문제 설명

두 개의 배열 A, B는 N개의 자연수 원소로 구성되어있다. 배열 A,B 각각의 원소 하나씩 골라서 바꾸는 최대 K번의 바꿔치기 연산을 수행한다. 이 때, 배열 A의 모든 원소의 합이 최댓값을 출력하라.

문제 조건

• 풀이 시간 : 15분
• 시간 제한 : 2초
• 메모리 제한 : 128MB
• 입력 조건 :
  • 첫 번째 줄에 N, K가 공백을 기준으로 구분되어 입력
  • 두 번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력
  • 세 번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력
• 출력 조건 :
  • 최대 K번의 바꿔치기 연산을 수행 후 만들 수 있는 배열 A의 모든 원소 합의 최댓값 출력

문제 해결 아이디어

• 배열 A의 가장 작은 원소와 배열 B의 가장 큰 원소를 교체한다.
• A에 대해 오름차순 정렬, B에 대해 내림차순 정렬한다.
• 인덱스를 차례대로 확인하며, A원소가 B원소보다 작을 때 교체 수행
• O(NlogN)을 보장하는 알고리즘 사용

답안 예시

n, k = map(int, input().split()) # n, k 입력 받기
a = list(map(int, input().split())) # 배열 A의 모든 원소 받기
b = list(map(int, input().split())) # 배열 B의 모든 원소 받기

a.sort() # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
    # A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
        # 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        break

print(sum(a)) # 배열 A의 모든 원소의 합을 출력