04-5 병합 정렬
- 병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.
- 시간 복잡도는 O(nlogn)이다.
- 코딩 테스트의 정렬 관련 문제에 자주 등장한다.
- 2개의 그룹을 병합하는 원리는 꼭 숙지해두자.
[2개의 그룹을 병합하는 과정]
- 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.
- 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
📌 문제 020) 수 정렬하기 2
시간 제한 2초, 실버 V, 백준 2751번
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
5 # 수의 개수 5 4 3 2 1
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
1 2 3 4 5
1단계 문제 분석
- N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다.
- 병합 정렬로 수행하자.
- 원본 리스트 길이가 5이므로 먼저 2, 2, 1 길이로 나눈다.
- 나눈 그룹마다 병합 정렬을 한다.
- 각 그룹마다 index1, index2를 지정하여 비교하면서 정렬 용도로 선언한 tmp 배열에 병합 정렬을 한다.
- 현재는 그룹이 3개이므로 2, 3번째 그룹을 병합했다.
- 이어서 병합된 그룹 대상으로 정렬한다.
- index2의 경우 오른쪽으로 이동할 공간이 없으므로 index1만 이동하는 형태로 정렬한다.
- 마지막 정렬을 이어나간다.
2단계 슈도 코드
# 병합 정렬 구현
병합 정렬(s, e):
s(시작점), e(종료점), m(중간점)
# 재귀 함수 형태로 구현
병합 정렬(s, m)
병합 정렬(m+1, e)
for s~e:
tmp 리스트 저장
# 두 그룹을 병합하는 로직
index1 -> 앞쪽 그룹 시작점
index2 -> 뒤쪽 그룹 시작점
while index1 <= 중간점 and index2 <= 종료점:
양쪽 그룹의 index가 가리키는 값을 비교한 후 더 작은 수를 선택해 리스트에 저장하고
선택된 데이터의 index값을 오른쪽으로 한 칸 이동
반복문이 끝난 후 남아 있는 데이터 정리
N(정렬할 수 개수)
A(정렬할 리스트 선언)
tmp(정렬할 때 잠시 사용할 임시 리스트 선언)
for(N의 개수만큼):
A 리스트에 데이터 저장하기
병합 정렬 함수 수행
결괏값 출력3단계 코드 구현
import sys
input = sys.stdin.readline
print = sys.stdout.write
def merge_sort(s, e): # 병합 정렬 수행
if e - s < 1: return
m = int(s + (e - s) / 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]
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
N = int(input())
A = [0] * int(N+1)
tmp = [0] * int(N+1)
for i in range(1, N+1):
A[i] = int(input())
merge_sort(1, N)
for i in range(1, N+1):
print(str(A[i]) + '\n')📌 문제 021) 버블 정렬 프로그램 2
시간 제한 1초, 플래티넘, 백준 1517번
N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.
버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.
입력
첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.
3 # 수의 개수 3 2 1
출력
첫째 줄에 Swap 횟수를 출력한다.
3
1단계 문제 분석
- N의 최대 범위가 500,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다.
- 이 문제는 버블 정렬이 아닌 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 사용하자.
- 병합 정렬을 이해한 상태라면 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있다는 것을 떠올릴 수 있다.
- 병합 정렬은 동일하게 진행하지만, 정렬 과정에서 index가 이동한 거리를 result에 저장한다.
2단계 슈도 코드
# 병합 정렬 구현
병합 정렬(s, e):
s(시작점), e(종료점), m(중간점)
# 재귀 함수 형태로 구현
병합 정렬(s, m)
병합 정렬(m+1, e)
for s~e:
tmp 리스트 저장
# 두 그룹을 병합하는 로직
index1 -> 앞쪽 그룹 시작점
index2 -> 뒤쪽 그룹 시작점
while index1 <= 중간점 and index2 <= 종료점:
양쪽 그룹의 index가 가리키는 값을 비교한 후 더 작은 수를 선택해 리스트에 저장하고
선택된 데이터의 index값을 오른쪽으로 한 칸 이동
반복문이 끝난 후 남아 있는 데이터 정리
로직을 수행하면서 뒤쪽 데이터 값이 더 작아 선택될 때
swap이 일어난 것과 동일한 것이기 때문에
현재 남은 앞쪽 그룹 데이터의 개수만큼 결괏값에 더해 줌
N(정렬할 수 개수)
A(정렬할 리스트 선언)
tmp(정렬할 때 잠시 사용할 임시 리스트 선언)
A 리스트에 데이터 저장하기
병합 정렬 함수 수행
결괏값 출력3단계 코드 구현
import sys
input = sys.stdin.readline
result = 0
def merge_sort(s, e): # 병합 정렬 수행
global result
if e - s < 1: return
m = int(s + (e - s) / 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 = 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
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
tmp = [0] * int(N+1)
merge_sort(1, N)
print(result)04-6 기수 정렬
- 기수 정렬(radix sort)은 값을 비교하지 않는 특이한 정렬이다.
- 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.
- 시간 복잡도는 O(kn)으로, k는 데이터의 자릿수를 말한다.
- 예를 들어, 234, 123을 비교하면 4와 3, 3과 2, 2와 1만 비교한다.
[기수 정렬의 핵심 이론]
- 기수 정렬은 10개의 큐를 이용한다.
- 각 큐는 값의 자릿수를 대표한다.
- 시간 복잡도가 가장 짧은 정렬이다.
- 만약 코딩 테스트에서 정렬해야 하는 데이터 개수가 너무 많으면 기수 정렬 알고리즘을 활용해 보자.
- 원본 배열 16, 80, 18, 77, 03, 24, 88, 23이 있다.
- 일의 자릿수 기준으로 배열 원소를 큐에 집어 넣는다.
- 0번째 큐부터 9번째 큐까지 pop을 진행한다.
- 그 결과, 80, 03, 23, 24, 16, 77, 18, 88이 만들어 진다.
- 십의 자릿수를 기준으로 같은 과정을 진행한다.
- 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복한다.
📌 문제 022) 수 정렬하기 3
시간 제한 3초, 실버 V, 백준 10989번
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
10 5 2 3 1 4 2 3 5 1 7
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
1 1 2 2 3 3 4 5 5 7
1단계 문제 분석
- N의 최대 개수가 10,000,000으로 매우 크기 때문에 O(nlogn)보다 더 빠른 알고리즘이 필요하다.
- 문제에서 주어지는 숫자의 크기가 10,000보다 작다는 것을 바탕으로 기수 정렬과 함께 많이 사용하는 계수 정렬(counting sort)을 사용하여 문제를 해결해보자.
- 숫자 크기가 10,000보다 작기 때문에 10,001 크기의 리스트를 선언한다.
- 입력하는 수를 차례대로 받아 수의 값을 리스트의 인덱스 값으로 판단하고 해당 인덱스에 해당하는 값을 1 증가하여 준다.
- 리스트를 처음부터 끝까지 탐색하면서 값이 0이 아닐 경우 해당 값이 있는 index를 값만큼 반복하여 출력한다.
2단계 슈도 코드
N(정렬할 수 개수)
count(카운팅 정렬 리스트)
for N만큼 반복:
count 리스트에 현재 수에 해당하는 index의 값 1 증가
for i는 0~10000까지:
만약 count[i]의 값이 0이 아니면 # i가 기존 input에 있는 수
해당 값만큼 i를 반복하여 출력3단계 코드 구현
import sys
input = sys.stdin.readline
N = int(input())
count = [0] * 10001
for i in range(N):
count[int(input())] += 1
for i in range(10001):
if count[i] != 0:
for _ in range(count[i]): # 해당 index값 만큼 index를 반복하여 출력
print(i)
안녕하세요 :)