해당 포스트는 "관계 중심의 사고법 쉽게 배우는 알고리즘 - 문병로, 한빛아카데미" 를 기반으로 작성되었습니다.
기본개념
정렬 알고리즘에 대한 기본적인 개념은 정리되어 있는 포스팅이 상당히 많아서 해당 내용은 포스팅 하지 않기로 정했습니다.
다만, 처음으로 정렬알고리즘의 개념을 익히신다면,
상단의 사이트를 들어가시면 여러가지 정렬 알고리즘을 시각화해서 보여주고 있습니다. 참고 하신다면 금방 익히실수 있을거라고 생각합니다.
나동빈 저자님이 본인의 책에 정리한 내용을 기반으로 강의한 자료도 있으니 참고 부탁드립니다.
책에 등장하는 알고리즘을 cpp로 구현해놓은 깃레포입니다. (42서울 과제들도 다른 레포에 저장하고 있으니 팔로우 하고 참조해도 좋습니다!)
이번 포스팅에서 진짜로 제가 포스팅하고 싶었던 것은 연습문제 풀이입니다. 깊게 생각해볼 내용이 있어서 공유하고 같이 고민하고 하나하나 해결해나갔으면 합니다.
연습문제
01 원소들이 다음 순서로 배열에 저장되어 있다. [12, 70, 30, 20, 55, 25]
선택정렬
가장 큰 원소를 먼저 찾고 찾은 원소를 정렬되지 않은 배열의 끝으로 보낸다.
[12, (70), 30, 20, 55, 25]
[12, 25, 30, 20, 55, 70] (20 <=> 70)
버블정렬
두개를 비교해서 가장 큰 원소를 뒤로 계속해서 한칸씩 보낸다.
[12, (70), 30, 20, 55, 25]
[12, 30, (70), 20, 55, 25]
[12, 30, 20, (70), 55, 25]
...
[12, 30, 20, 55, 25, (70)]
삽입정렬
맨앞에서 부터 정렬을하고 정렬된 부분의 배열에 알맞게 원소를 끼워넣는다.
[12, \ 70, 30, 20, 55, 25]
[12, 70 \, 30, 20, 55, 25]
[12, 30, 70 \, 20, 55, 25]
02 원소들이 다음 순서로 배열에 저장되어 있다. [12, 70, 30, 20, 55, 25, 40, 50]
병합정렬
[12, 70, 30, 20, 55, 25, 40, 50]
[12, 70, 20, 30, 25, 30, 40, 50]
[12, 20, 30, 70, 25, 30, 40, 50]
[12, 20, 25, 30, 30, 40, 50, 70]
힙정렬
힙 구조화 ->
[12, 25, 20, 30, 55, 40, 50, 70]
이후에 힙 정렬 ->
루트를 계속해서 pop을 진행 한 후에 힙 구조화를 진행.
03 퀵정렬을 이용해라
[12, 70, 30, 20, 55, 25, 40, 50]
50을 기준으로 작은 원소는 왼편에 큰 원소를 오른편으로 넣는다.
[12, 30, 20, 25, 40, 50, 70, 55]
40을 기준으로 왼쪽 배열 내에서 같은 작업을 반복한다.
[12, 30, 20, 25, 40, 50, 70, 55]
55을 기준으로 오른쪽 배열내에서 같은 작업을 반복한다.
[12, 30, 20, 25, 40, 50, 55, 77]
25를 기준으로 왼쪽 배열내에서 같은 작업을 반복한다.
[12, 20, 25, 30, 40, 50, 55, 77]
04 n개의 원소가 정렬되지 않은 상태로 배열에 저장되어 있다. 이를 대상으로 다음 작업들을 수행 할 때 소요되는 시간으 O-표기법으로 밝히시오.
(1) 가장 큰 원소 찾기
O(n) => 무조건 한번은 배열에 있는 원소들을 한번씩 훑어 봐야한다.
(2) 가장 큰 원소와 작은 원소를 동시에 찾기
O(n) => 찾는다는 계산은 상수의 계산이므로 (1)번과 같은 값을 갖는다.
(3) 힙으로 바꾸기
O(n) => 언뜻 본다면 O(log(n))같지만 그렇지 않고 n값을 갖는다.
05-06 n개의 원소가 정렬되지 않은 상태로 배열에 저장되어 있다. 이를 대상으로 다음 정렬 작업을 수행할 때 최악의 경우 소요되는 시간을 O-표기법으로 밝히시오.
해당 사진이 조금더 설명이 쉬워 첨부한다.
07 [알고리즘 4-3]의 삽입 정렬에서 2는 A[1]부터 A[i-1]까지 정렬되어 있는 상태에서 A[i]가 들어갈 자리를 찾는다. 이를 위해 A[i-1]부터 시작해 왼쪽으로 차례로 훑어 나간다. 이렇게 하면 평균적으로 i-1/2 번의 비교가 필요하다. A[1 ... i-1]이 이미 정렬되어 있으므로 이진 탐색을 이용하면 i-1/2 대신 log(i - 1)번의 비교로 자리를 찾을 수 있다. 이렇게 하면 삽입 정렬의 수행 시간이 절약될 것 같지만 그렇지가 않다. 이유가 무엇인가?
실제로는 서치타임이 줄어들기때문에 전체적인 시간은 줄어 들겠지만 스왑하는 시간이 여전히 O(n)이기 때문에 결국, 워스트케이스에서 시간은 변하지 않는다.
08 배열 A[1...n]이 임의의 정렬 알고리즘의 입력으로 들어온다. 이때 배열이 이미 정렬되어 있는 상태이면 다음 중 어떤 정렬 알고리즘이 가장 효율적이겠는가
삽입 정렬 : 비교나 스왑이 필요가 없어져서 O(n)으로 계산된다.
버블 정렬 : 플래그를 사용한다면 같은 효과를 얻을 수 있다.
09 여섯 가지의 정렬 알고리즘들은 일반적인 시간 복잡도 관점에서 볼 때 세 그룹으로 나눌 수 있다. 어떻게 나누겠는가?
퀵정렬 | 병합정렬 힙정렬 | 선택정렬 삽입정렬 버블정렬
10 배열 A[1...n]이 임의의 정렬 알고리즘의 입력으로 들어온다. 이때 배열이 이미 반대로 정렬되어 있는 상태이면 다음의 각 정렬 알고리즘의 수행 시간은 어떻게 되겠는가?
선택 정렬 : O(n^2)
버블 정렬 : O(n^2)
삽입 정렬 : O(n^2)
병합 정렬 : O(nlogn)
퀵 정렬 : O(n^2)
힙 정렬 : O(nlogn)
11 10억 개의 실수 원소를 정렬하려 하는데 그중 10개 정도만 제외하면 정렬된 상태다. 이 사실을 안다면 정렬 알고리즘 중 어느 알고리즘을 선택하고 싶은가? 그 이유도 설명하시오.
한꺼번에 정렬을 할려고 한다면 무리라고 생각하며 나눠서 정렬해야한다. 나눠서 정렬하면 대부분의 부분이 정렬되어 있기 떄문에 삽입 정렬이나 버블 정렬을 사용해서 O(n)의 빠르기로 정렬된 부분을 스킵해나가고 싶다.
12 다음은 병합정렬의 변형 알고리즘이다. 이 알고리즘의 점근적 수행시간을 O-표기로 밝히고 증명하시오. 문제의 크기가 항상 한치의 오차도 없이 2:3으로 정확하게 나누어지지 않는다는 점도 고려해야한다. 이 부분이 어려워 문제의 크기가 항상 2:3으로 나누어진다. 가정하고 증명을 하면 70% 정도만 푸는셈이다.
Mergesort(A[], p, r)
{
if (p < r)
{
q = p + floor(2*(r-p)/5);
Mergesort(A, p, q);
Mergesort(A, q+1, r);
Merge(A, p, q, r) // Mergesort는 git repo에 있는 코드와 같다. (일반적인 병합정렬)
}
}
JavaScript
복사
70% 해법 ⇒ n = 2^k라는 대전제가 깔린다. 일반적인 알고리즘의 속도계산 문제에서 등장하는 가정이다.
T(n) ≤ T(2n/5) + T(3n/5) + cn(merge ⇒ 계산속도)
≤ T((2n/5) * (2/5)) + T((2n/5) * (3/5)) + T((3n/5) * (2/5)) + T((3n/5) * (3/5)) + cn
≤ 2T((2n/5) * (2/5) * (2/5)) + 2T((2n/5) * (3/5) * (3/5)) + 2T((3n/5) * (2/5) * (2/5)) + 2T((3n/5) * (3/5) * (3/5)) + cn
≤ 0(nlogn)
일반적이 해법을 찾아보고 싶습니다!
13 병합 정렬에서 둘로 나누는 대신 16개로 나누어도 정렬은 된다. 즉, 최상위 레벨에서 병합정렬을 16번 부른 다음 병합을 한다. 이 경우의 알고리즘을 기술하고 (너무 자세할 필요는 없고 상식적인 수준으로 기술) 점근적 복잡도를 분석하시오. 병합부분을 효율적으로 하는 자료구조(본문에서 다룬 자료구조 중 답이 있음)와 방법도 기술에 포함시키시오(병합은 점근적 시간뿐만 아니라 숨은 상수 인자도 가능하면 작은 방법으로 할 것).
14 다음은 문제 풀이를 목적으로 만든 꽤 부자연스러운 알고리즘이다. 이 알고리즘은 정렬을 제대로 하는가? 정렬이 되든 안되든 이 알고리즘이 종료되기까지 소요되는 점근적 시간을 분석하시오.
sort(A[], p , q)
{
if (p < q) then {
if (p < q + 20)
then selectionSort(A, p, q);
else{
r = (p - q + 1) / 3;
sort(A, p, p + r + 4);
sort(A, p + r, q);
merge(A, p, r, q);
}
}
}
JavaScript
복사
15 다음은 본문에서 사용한 배열 A[p ... r]을 대상으로 하는 퀵 정렬의 분할 알고리즘이다. 이 알고리즘은 배열의 맨 마지막 원소 A[r]을 기준원소로 삼는다. 이 알고리즘을 배열의 맨 첫 원소 A[p]를 기준원소로 삼는 알고리즘으로 바꾸어보시오. 단순히 A[p]와 A[r]을 자리 바꾼 다음 아래의 알고리즘을 수행하는 방식은 문제로서 별 의미가 없다. 즉, 원소들을 계속 A[p]와 비교하는 방식으로 수행해야 한다.
partition(A[], p, r)
{
x = A[r]; i = p - 1;
for j = p to r - 1
if (A[j] <= x) then {i++; swap(A[i], A[j]);}
swap(A[i + 1], A[r]);
return (i + 1);
}
JavaScript
복사
16 다음은 퀵 정렬을 조금 변형한 것이다. 물음에 답하시오.
int Asort(A[], p, r)
{
if (p >= r) then return 1;
else
{
(q, t) = partition(A, p, r);
return (t + Asort(A, p, q - 1) + Asort(A, q + 1, r));
}
}
(int, int) partition(A[], p, r)
{
A[p ... r] 을 본문에서처럼 분할한다. (quicksort 분할, 깃 참고)
q = 기준원소의 위치
return (q, 0);
}
JavaScript
복사
1 Asort() 의 평균 리턴 값을 O-표기로 최대한 엄밀하게 나타내시오.
2 1의 답은 퀵 정렬 알고리즘과 어떤 관련이 있는가?
17 다음은 퀵 정렬을 조금 변형한 것이다. 물음에 답하시오.
int Bsort(A[], p, r)
{
if (p >= r) then return 1;
else
{
(q, t) = partition(A, p, r);
return (t + Bsort(A, p, q - 1) + Bsort(A, q + 1, r));
}
}
(int, int) partition(A[], p, r)
{
A[p ... r] 을 본문에서처럼 분할한다. (quicksort 분할, 깃 참고)
q = 기준원소의 위치
return (q, r - p + 1);
}
JavaScript
복사
1 Bsort() 의 평균 리턴 값을 O-표기로 최대한 엄밀하게 나타내시오.
2 1의 답은 퀵 정렬 알고리즘과 어떤 관련이 있는가?
18 "힙 정렬의 수행 시간은 O(nlogn)이다"는 말에 대해 OX로 답하시오. 대답이 O이면 이유를 간단히 설명하고, X이면 반례를 들어보시오.
19 높이가 k인 꽉 찬 이진 트리에 자연수의 집합 {1, 2, 3, ..., 2^k - 1}을 키 값으로 한 번씩 넣어 힙(최소힙)을 만들려고 한다(노드가 하나만 있는 트리의 높이를 1 이라 하자). 이 집합의 모든 원소를 한 번씩 사용해 만들 수 있는 서로 다른 힙의 총수를 T(k)라고 할 때, T(k)의 점화식을 도출 하시오.
20 배열 A[1 ... n]에 저장된 힙(최소힙)에서 한 노드의 값이 바뀌어 힙성질이 깨졌다. 힙성질을 만족하도록 수선하는 알고리즘을 만들어보시오. 반드시 재귀적 알고리즘으로 만들어야 한다. heapRepair()가 재귀 함수가 되도록 해도 좋고, heapRepair() 내부의 함수가 재귀 함수가 되도록 해도좋다. 어떤 노드 값을 확인하기 위해 배열 A[]를 참조할 때는 해당 원소의 색인을 반드시 명확히 해야 한다. 즉, A[i], A[i/2 - 1]과 같은 구체적인 형태여야 하고, A[r]의 오른쪽 자식, A[r]의 형제, A[r]의 형제, A[r]의 부모 등의 표현은 사용하지 않아야 한다(이 문제에 한정된 요구 사항).
21 [알고리즘 4-9]의 기수 정렬이 안정성을 유지하는 정렬이 아니면 어떻게 되는가?
22 이 장에서 소개한 다음 정렬 알고리즘들은 안정성을 유지하는 정렬인가?
선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬, 힙 정렬, 기수 정렬, 계수 정렬
