정렬

버블 정렬

버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다. 시간 복잡도는 O(n²)으로 다른 정렬 알고리즘보다 속도가 느린 편이다. 아래와 같이 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.

루프를 한 번 돌때 n의 시간 복잡도가 든다. 루프를 한 번 돌 때마다 정렬 데이터가 1개씩 나오므로 n번을 돌아야 모든 데이터를 정렬할 수 있다. 따라서 버블 정렬의 시간 복잡도는 O(n²)이 된다.
주의할 점은, 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다.

선택 정렬

선택 정렬은 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 핵심이다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n²)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다.

최솟값을 찾기 위해 루프를 한 번 돌 때 n번 탐색한다. 두번째에는 n-1, 세번째는 n-2, ... , 마지막은 1번 탐색한다. 루프를 한 번 돌 때마다 정렬 데이터가 1개씩 나오므로 n번을 돌아야 모든 데이터를 정렬할 수 있다. 따라서 선택 정렬의 시간 복잡도는 O(n²)이 된다.

삽입 정렬

삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 합입시켜 정렬하는 방식이다. 시간 복잡도는 O(n²)으로 느린 편이지만 구현하기 쉽다. 삽입 정렬은 첫 번째 데이터는 이미 정렬된 상태라고 가정하고, 두 번째 데이터부터 시작한다.

적절한 삽입 위치를 탐색하는 부분에서 이진 탐색(binary search)등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.

퀵 정렬

퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간 복잡도는 O(nlogn)이며 최악의 경우에는 시간 복잡도가 O(n²)이 된다.

퀵 정렬 과정
임의의 기준값(pivot)을 정하고 기준값을 제외한 데이터 중 양 끝에 start, end 포인터를 지정한다. start의 값이 pivot보다 작으면 start 포인터를 오른쪽으로 한 칸 이동한다. end의 값이 pivot보다 크면 end 포인터를 왼쪽으로 한 칸 이동한다. start의 값이 pivot보다 크고, end의 값이 pivot보다 작으면 start와 end의 값을 swap하고 start 포인터는 오른쪽, end 포인터는 왼쪽으로 한 칸 이동한다. start와 end가 만날때까지 이를 반복한다.
start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot을 비교 후, pivot이 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.
분리 집합에서 각각 다시 pivot을 선정한 후 분리 집합이 1개 이하가 될때까지 위 과정을 반복한다.

병합 정렬

병합 정렬은 분할 정복방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도는 O(nlogn)이다.

데이터를 가장 작은 단위로 분할 하기 위해서는 logn번의 단계가 필요하고 각 단계에서 n번의 연산으로 데이터를 병합하기 때문에 병합 정렬의 시간 복잡도는 O(nlogn)이다.
위의 그림을 예로 들면, 8개의 데이터를 가장 작은 데이터 집합으로 분할하기 위해 (log₂8=3)3번의 단계가 필요하고 각 단계에서 8번의 연산으로 데이터를 병합하기 때문에 총 연산량은 8 * log₂8 = 24 이지만, 시간 복잡도는 일반적으로 O(nlogn)으로 표현된다.

2개의 그룹을 병합하는 과정
투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 한 칸 이동시킨다. 이 방식은 여러 문제에서 응용하므로 반드시 숙지하는 것이 좋다.

두 집합 중 앞 집합의 데이터가 모두 작은 값으로 저장이 되었다면, 뒷 집합 내에서의 데이터 정렬은 이미 이뤄진 상태이기 때문에 뒷 집합은 정렬된 데이터 뒷부분에 그대로 삽입되면 된다.

기수 정렬

기수 정렬은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다.
기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.

기수 정렬은 1의 자릿수 기준으로 숫자를 n번 분류한 후, 10의 자릿수 기준으로 다시 n번 분류하는 과정을 k번 반복한다. 따라서 O(kN)의 시간 복잡도를 가진다.

[백준] 버블 소트 : 1517

문제

예제

풀이

시간 제한이 1초로 되어 있기 때문에 시간 복잡도가 O(n²)인 버블 정렬을 사용하여 풀 수 없다. 이 문제는 시간 복잡도가 O(nlogn)인 병합 정렬을 사용하여 풀어야 한다.
또한, 해당 값 앞에 해당 값보다 큰 수가 나오면 swap이 일어나므로 해당 값보다 큰 데이터가 몇 개 있는지가 swap하는 횟수와 같다.

import sys
input = sys.stdin.readline
result = 0

n = int(input())
a = list(map(int, input().split()))
a.insert(0,0) # 인덱스 1부터 시작하도록 추가
tmp = [0] * int(n+1) # 0을 추가하므로써 발생하는 배열 크기 오류 수정

# s: 시작값, m: 중간값, e: 마지막값
def merge_sort(s, e):
    global result
    if s >= e: # 재귀 함수 종료 조건 추가
        return
    
    m = (s + e) // 2 # 중간값 계산
    merge_sort(s, m)
    merge_sort(m+1, e)
    
    # 병합 과정
    for i in range(s, e+1): 
        tmp[i] = a[i]
        
    k = s # 병합한 결과를 저장할 인덱스
    index1 = s
    index2 = m+1
    
    while index1 <= m and index2 <= e:
        if tmp[index1] > tmp[index2]: # 역순 개수 세기
            a[k] = tmp[index2] # 작은 값을 먼저 배치
            result += index2 - k # 역순 횟수 카운트
            k  += 1
            index2 += 1
        else:
            a[k] = tmp[index1]
            k += 1
            index1 += 1
    
    # 남은 요소 처리
    while index1 <= m:
        a[k] = tmp[index1]
        k += 1
        index1 += 1
    while index2 <= e:
        a[k] = tmp[index2]
        k += 1
        index2 += 1
        
merge_sort(1, n)
print(result)

[백준] ATM 인출 시간 계산하기 : 11399

문제

예제

나의 풀이

sorted를 사용해서 아주 쉽게 풀었는데 아래처럼 삽입 정렬을 활용해서 풀어봐야 할 것 같다.

n = int(input())
p = list(map(int, input().split()))

time = sorted(p)
amt = 0
for i in range(len(time)):
    amt += sum(time[:i+1])
    
print(amt)

다른 풀이

아래는 삽입 정렬과 합 배열을 이용한 풀이이다. ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 그리디 방식을 활용한다.

n = int(input())
a = list(map(int, input().split()))
s = [0] * n

# 삽입 정렬
for i in range(1, n):
    insert_point = i
    insert_value = a[i]
    for j in range(i-1, -1, -1):
        if a[j] < a[i]:
            insert_point = j+1 # 작은 자리보다 한 칸 뒤에 위치해야 하므로
            break
        if j == 0:
            insert_point = 0
            
    for j in range(i, insert_point, -1):
        a[j] = a[j-1]
    a[insert_point] = insert_value
    
s[0] = a[0]

for i in range(1, n):
    s[i] = s[i-1] + a[i]
    
sum = 0
for i in range(0, n):
    sum += s[i]
    
print(sum)