10989. 수 정렬하기 3

10
5
2
3
1
4
2
3
5
1
7

1
1
2
2
3
3
4
5
5
7

1. 카운팅 정렬 소개

이제 소개할 카운팅 정렬은 매애우 간단하고 빠른 알고리즘이다. 간단하고 빠른 만큼 제한적이고, 메모리를 많이 소비한다.

쉬운 버블 / 삽입 정렬은 O(n ^ 2) 이었고, 병합 / 힙 정렬은 O(n * log n) 이었다.

카운팅 정렬은 O(n) 으로 선형시간이다!

카운팅 정렬은 말 그대로 숫자가 몇 번이나 나오는지 세는 알고리즘이다. 소개하기도 뭐한 매우 간단한 알고리즘인데,

필요한 배열은 숫자가 몇 번 나오는지 기록할 배열이다. 위의 문제에선 등장할 수가 10,000 보다 작거나 같은 자연수로 제한되어 있기 때문에 만칸의 배열만 준비하면 된다.

따라서 카운팅 정렬은 정렬할 원소들의 범위를 알고 있는 상황에서만 쓸 수 있다.

또한 그 범위는 메모리에 올릴 수 있을 정도여야한다.

[1, 100, 2, 1, 50] 이라면 백 칸짜리 배열이 필요하겠다.

이제 정렬한 결과를 출력하는데는 두 가지 방법이 있다.

첫째로는 걍 백 칸짜리 배열을 앞에서 부터 보면서 기록된 갯수만큼 출력하는 것이다.

인덱스 1을 보고 기록된 숫자가 2 이므로 1을 두 번 출력한다.

이 경우에 메모리 사용량은 숫자 등장 범위에 영향을 받는다.

두번째 방법으로는 백 칸짜리 기록용 배열을 누적합으로 바꿔주는 것이다.

-> 누적합[1] = 2 / 누적합[2] = 3 / ... / 누적합[50] = 4 / ... / 누적합[100] = 5

이제 기록용 배열은 해당 숫자가 정렬된 배열의 어떤 범위에 존재해야 하는지 나타낸다.

즉, 누적합[1] = 2 이므로, 배열의 앞에서 부터 두칸을 차지한다는 뜻이고,

바로 뒤의 누적합[2]는 3이니까 세번째 칸을 차지한다는 뜻이다.

누적합[3] [4] ... [49] 는 연속해서 3이므로 정렬결과용 배열에 들어가지 않는다.

또한 이 방법은 입력순서를 기억해야한다. 마지막 입력은 50 이었고 누적합[50] = 4 였으므로,

50은 정렬용 배열 네번째 칸에 들어간다. 누적합[50] = 3으로 줄어든다.

50의 전 입력은 1이었다. 누적합[1] = 2 이므로 1은 정렬용 배열 두번째 칸에 들어간다. 누적합[1] = 1로 줄어든다.

이 방법은 따라서 입력의 갯수에 비례해서 연산을 하고, 메모리도 차지한다.

두 방법중에 알맞은 방법을 쓰기로 하자.

위의 문제에선 숫자 등장범위가 10,000 이고 입력은 10,000,000 개 이니까 첫번째 방법을 쓰기로 했다.

2. 코드

3. 시간 복잡도

일단 입력이 n개 들어오므로 입력엔 O(n)이 걸린다. 출력도 결국엔 n개를 출력해야 하므로 O(n)이다.

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

5
5
4
3
2
1

1
2
3
4
5

1. 힙 정렬 heap sort 소개

O(n * log n)의 시간복잡도를 가지는 또 다른 정렬 알고리즘을 알아보자 

힙 정렬은 말 그래도 힙 자료구조를 사용한 정렬방법이다.

따라서 이해하기 위해선 힙이 무엇인지부터 알아야 한다!

1-1) 힙 자료구조 소개

우선 힙은 완전이진트리다. 

이진트리라 함은 한 노드가 최대 두 개의 자식노드를 가진다는 뜻이고,

완전이진트리라 함은 마지막 level = depth 를 제외하고 모든 레벨은 노드가 가득 차있으며, 마지막 레벨은 노드가 왼쪽부터 채워져 있다는 뜻이다.

힙의 강점은 부모-자식 간에 대소관계가 전부 적용되어 있다는 것이다. 단 형제들 끼리는 적용하지 않는다.

(최대힙이라면) 따라서 루트노드는 가장 큰 노드가 될 것이다.

따라서 이러한 힙(최대 힙)을 유지한다면 O(1)에 가장 큰 수를 찾을 수 있다.

우선순위 큐도 비슷한 자료구조로 구현되어 있다고 한다.

1-2) 힙 자료구조 구성하기

힙은 트리로 되어있지만, 완전이진트리라는 점에서 배열로 구현할 수 있다.

루트노드를 인덱스 0으로 잡을시, 부모 노드의 인덱스가 x라면, 왼쪽 자식의 인덱스는 (x * 2 + 1),

오른쪽 자식의 인덱스는 (x * 2 + 2) 이다.

루트노드를 인덱스 1으로 잡을시, 부모 노드의 인덱스가 x라면, 왼쪽 자식의 인덱스는 x * 2, 

오른쪽 자식의 인덱스는 (x * 2 + 1) 이다.

이제 전체 배열을 힙으로 만들어 보자!

힙으로 만드는데는 부모노드를 조지는 방법이 효과적이다.

간단히 노드 세 개의 이진트리를 생각해보면,

루트 노드가 3이고, 두 자식 노드가 모두 3보다 크다면 어찌되었건 부모 노드를 아무 자식과 스왑해주면 끝이다.

그래서 작은 부분 부분 힙을 만들어주면서 확장시키는 방법을 쓴다.

코드로 보면 이해가 빠르당

x를 부모 노드로 잡고 힙이 될 조건(부모가 제일 큼)을 만족할 때 까지 밑으로 조져버린다.

함수를 배열 맨 뒤에서 부터 호출해주면 되는데,

시간을 절약하기 위해선 리프 노드에 대해선 호출할 필요가 없다는 점을 기억하자.

1-3) 힙 정렬하기

이제 힙을 완성했으니 정렬에 써먹어 보자.

힙의 장점 : 최대값을 O(1)에 알 수 있다 / 를 활용하는 것이다.

오름차순이라면 배열의 최대값은 배열 맨 뒤에 있어야 한다. O(1)에 알 수 있다. 힙에서 베껴온다.

그럼 그 다음으로 큰 수는 어떻게 알 수 있을까? 

일단 다음으로 큰 수는 루트(부모)의 두 자식 중에 한 놈이다.

하지만 우리의 목표는 계속 힙 구조를 유지하면서 장점을 써먹는 것이므로, 루트를 잃어버린 힙을 재구성해야 한다.

재구성은 간단하다. 위에서 했던 down_heap()을 활용한다.

루트를 힙의 누군가로 새롭게 대체하고 밑으로 조져버리면, 루트의 두 자식 중에 큰 놈이 위로 올라올 것이고, 대체자는 본연의 자리를 찾아갈 것이므로 힙이 새롭게 재구성되는 것이다.

루트를 새로 채울 놈은 누구를 써야 하는가? 만만한건 제일 마지막에 있는 리프 노드다.

그림으로 확인해보자.

2. 코드

3. 시간복잡도

힙 정렬 알고리즘은 간단히 쓰면 다음의 단계를 거친다.

1) 주어진 배열로 힙을 만든다.

2) 루트노드를 새로운 배열로 옮기고, 힙의 말단으로 루트를 대체한뒤, 다운힙 시킨다.

1번의 과정은 얼마나 걸릴까?

우선 힙을 만드는데 down_heap을 썼던 점을 기억하자.

down_heap은 결국엔 이진트리의 높이만큼 수행될 것이다 -> O(log n)

또한 배열의 맨 뒤 부터 밑으로 조져버린다는 점에 의해 -> O(n * log n) 안에 수행된다.

2번 과정도 동일하다. O(1)에 루트노드에 접근할 수 있으며, 다운 힙은 O(log n) 안에 수행된다. 이를 n개에 대해 연산한다.

따라서 O(n * log n) 임을 알 수 있다.

2751. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

5
5
4
3
2
1

1
2
3
4
5

1. 병합 정렬 merge sort 소개

앞선 두 개의 정렬 알고리즘은 어찌됐건 O(n ^ 2)의 시간복잡도를 가진다.

위의 문제를 보면 최악의 경우 백만 칸의 배열을 정렬해야 한다.

백만의 제곱으로는 시간 제한내에 들어오지 못한다.

그러면 더 빠른 알고리즘을 알아햐 하니까, 병합 정렬에 대해 알아보려고 한다.

우선 병합 정렬은 분할 정복이다. 즉 문제를 쪼개어서 부분 문제로 만들어 해결하자는 뜻으로, 결국 재귀적인 패러다임이다.

때문에 하위 문제는 상위 문제보다 적용 범위가 작아야 하고, 범위가 작아지는 한계인 탈출지점이 있어야 한다.

분할 정복은 다음 세 부분으로 나눌 수 있다.

1) 분할 : 원래의 문제를 분할하여 같은 문제 유형의 더 작은 하위 문제들로 나눈다.

2) 정복 : 하위 문제들을 재귀적으로 해결해야 한다. 충분히 하위 문제가 작아졌다면 탈출해야 한다.

3) 합치기 : 하위 문제들의 답을 합쳐 원래 문제를 해결한다.

도식화 하자면 다음과 같다.

이제 병합 정렬을 분할 정복해보자. 하위 문제를 잘 정의해야 한다.

당연히 원래의 문제는 수열을 정렬하는 것이다. 하위 문제는 수열의 일부분만 정렬하는 문제라고 정의하자.

폰 노이만은 병합 정렬을 만들 때 다음의 단계를 거치라고 했다.

1) 분할 : 수열을 반으로 쪼갠다.  [14, 7, 3, 12, 9, 11, 6, 2] ->  [14, 7, 3, 12] /  [9, 11, 6, 2]

2) 정복 : 쪼개진 수열 각각에 대해 정렬한다. [3, 7, 12, 14] /  [2, 6, 9, 11]

3) 결합 : 두 수열을 합쳐서 정렬한다 [2, 3, 6, 7, 9, 11, 12, 14]

하위 배열 [14, 7, 3, 12]은 어떻게 정렬할까? 마찬가지로 분할-정복-결합을 거쳐 [3, 7, 12, 14] 로 만든다.

다음은 위의 예시가 어떻게 재귀적으로 전개되는지 과정을 보여준다.

2. 코드

아마 병합단계를 구성하는게 가장 어려웠을 것이다.

단순히 두 배열을 합치고 지금까지 배운 삽입-정렬이나 거품-정렬을 쓸 수도 있지만

그리한다면 오히려 더 느린 알고리즘이 되어버린다.

이를 선형시간에 해결할 아이디어는, 우리가 문제를 재귀적으로 풀고 있었다는 점에서 떠올릴 수 있다.

우리가 합쳐서 정렬할 두 부분 배열의 특징은 무엇인가? 바로 이미 재귀적으로 정렬되어버린 배열이라는 점이다.

따라서 다음과 같은 방법을 쓸 수 있다.

4칸 부분 배열 두 개를 합쳐 8칸 짜리 배열을 만들어야 한다고 해보자.

첫칸에는 어떤 숫자가 와야 하는가? 8개 숫자 중에 가장 작은 수이다.(오름차순)

고맙게도 두 부분 배열의 맨 앞은 가장 작은 숫자의 두 후보이다. 따라서 두 배열의 맨 앞의 숫자 중에 작은 수를 가져다 쓰면 된다.

둘째 칸에는 어떤 숫자가 와야 하는가? 두번째로 작은 숫자이다.

후보는 두 배열의 맨 앞 숫자이다.(인덱스로는 1 / 0)이다. 두 숫자중 작은 수를 가져다 쓴다.

....

그래서 n칸 짜리 임시배열을 만들고, 채우고, 다시 원본 배열에 복사해주는 편이 편하다.

원본 배열만 써서 이를 구현하면(in-place) 번거롭고, 오래걸린다.

3. 시간 복잡도

결론적으로 병합-정렬의 시간복잡도는 O(n * log n)이다. 백만 개가 주어진다면, O(백만 * 6)이다.

어떻게 차수는 줄어들 수 있었을까? 재귀적으로 분석해보자.

결국 최종적으로 완성되는 배열은 두 부분 배열(이미 정렬된)을 합치면서 완성된다. 위에서 합치는 방법이 선형시간임을 보였으므로,

합치는데는 O(n)이다.

그러면 정렬된 두 부분배열을 만드는데는 얼마나 걸렸을까? 각각의 크기는 n/2 이므로 O(2 * (n / 2)) = O(n) 만큼 걸렸다.

그림으로 알아보자.

그림을 통해 알 수 있는 사실은 O(n)은 트리의 높이만큼 수행된다는 것이다.

트리의 높이는 얼마나 되는가? log n 이다. 따라서 시간복잡도는 O(n * log n)이다.

또한 생각할 점은 원래의 배열이 어찌되었건 간에 쪼개는 상황은 반복된다는 것이다.

따라서 최선의 경우(이미 정렬되어 있어도)에도 시간복잡도는 O(n * log n) 이다.

2750. 수 정렬하기

5
5
2
3
4
1

1
2
3
4
5

1. 거품 정렬 소개

삽입 정렬 다음으로 간단한 정렬 알고리즘을 소개하고자 한다.

마찬가지로 인간의 정렬 방법과 유사한 알고리즘이다. 삽입 정렬에선 가지고 있는 숫자 타일을 하나 내려놓고, 정렬하고 했다면,

이번에는 가지고 있는 숫자 타일 중 가장 큰 수 부터 내려놓는 방법이다.

그러면 가장 큰 수는 어떻게 찾을까? 당연히 전체를 다 뒤져야 한다.

여러 방법이 있겠지만, 거품 정렬에선 이름 처럼 거품이 떠오르는 듯한 방법을 쓴다.

1) 맨 앞의 두 인자를 비교해서(인덱스 0과 1), 올바른 순서면 바꾸지 않고, 아니라면 서로 바꾼다. (swap)

2) 이번엔 다음 두 인자를(인덱스 1, 2) 마찬가지로 비교하고 스왑한다.

3) 배열의 마지막 두 인자 까지 2)를 수행한다.

다 수행했으면 배열의 상태는 어떠할까? 중간 인자들의 상태는 뒤죽박죽일지 몰라도 가장 마지막 숫자는 올바른 위치에 있다.

오름차순으로 정렬하기로 했다면, 배열 중 가장 큰수가 가장 맨 마지막에 있게 되는 것이다.

이제 제대로 박힌 마지막 인자를 제외하고 다시 처음부터 과정을 반복하면 된다.

그러면 뒤에서 부터 올바른 위치로 인자들이 채워지는 것이다.

애니메이션으로 확인해보자.

뒤에서 부터 한 점씩 채워지는 과정을 눈으로 확인할 수 있다.

2. 코드

3. 시간 복잡도

삽입 정렬과의 차별점은, 삽입 정렬이 for문 안이 while문으로 되어있다면, 거품 정렬은 for문으로 되어있다는 점이다.

따라서 삽입 정렬은 운이 좋다면 while문이 별로 돌지 않고 끝날 수 있지만,

거품 정렬은 그런거 없고 무조건 for문을 다 돌아야 한다.

또한 최악의 경우 마찬가지로 이중for문으로 인해 시간복잡도는 O(n ^ 2)이다.

2750. 수 정렬하기

5
5
2
3
4
1

1
2
3
4
5

1. 삽입정렬 소개

인간은 정렬을 어떻게 하는가? 누군가에게 숫자 타일을 여러개 주고 오름차순으로 바닥에 정렬하라고 한다면,

아마 다음과 같은 과정으로 정렬할 것이다.

{5, 3, 4, 1, 2}

1) 일단 헷갈리니까 하나를 내려놓는다.

-> {5}

2) 이제 다음 타일을 내려놓아야 하는데, 들고 있는게 내려놓은 타일보다 작다면 앞에 놓고, 아니면 뒤에 놓을 것이다.

즉 적당한 위치에 놓을 것이다.

-> {3, 5}

3) 2의 과정을 반복한다.

-> {3, 4, 5} -> {1, 3, 4, 5} -> {1, 2, 3, 4, 5}

삽입정렬은 우리의 정렬방법과 닮았다.

배열을 앞에서 부터 정렬하는데, 이미 정렬된 부분과 비교하여 현재 보고 있는 요소를 알맞은 부분에 삽입하는 정렬이다.

그러면 알맞은 부분에 삽입은 어떻게 해야할까?

현재 보고있는 부분을 제외하고 앞의 부분은 이미 정렬되어 있음을 기억해야 한다.

따라서 한 칸씩 돌아가는데, 맨 처음으로 돌아가거나 자신보다 작은 원소를 찾으면 그만 돌아가야 한다.

{1, 2, 4, 5} 까지 정렬했고 이제 3을 삽입하려고 할 때, 2를 보고 그만 돌아가는 것이다. -> {1, 2, 3, 4, 5}

돌아가는 중에는 3보다 큰 숫자라면 뒤로 한 칸씩 미뤄줘야 한다. 그래야 3이 들어갈 자리가 생긴다.

따라서 3의 현재 인덱스(4)와 숫자 3을 기억해야 한다. 5가 바로 뒤로 밀려오기 때문이다.

3보다 작은 첫 숫자 2(인덱스 : 1)를 발견했으면 이제 바로 뒷 칸(인덱스 : 2)에 삽입하면 끝이다.

gif로 확인해보자.

오른쪽으로 한 요소씩 진행하면서 계속 정렬하고 정렬하는 과정이 잘 보인다. 

2. 코드

3. 시간 복잡도

매번 정렬한다는 부분 알고리즘 때문에 딱 봐도 느린 알고리즘이다. 

결국 내림차순으로 되어있는 수열을 정렬한다면 (최악의 경우)

n + (n - 1) + (n - 2) + ... = n * (n - 1) / 2 번 걸릴 것이다.

따라서 O(n ^ 2) 의 시간복잡도를 가진다.