A :선택 정렬은 array의 모든 원소들 중 가장 작은 것을 index 0으로 보내고, index가 1보다 큰 것들 중 가장 작은 값을 index 1로 보낸다. 그 뒤 index 2에도 마찬가지로 실행한다. 가장 작은 데이터를 앞으로 보내는 과정을 N번 반복하는 것이다. 선택 정렬은 N + N-1 + N-2 + ... 2번 연산을 진행하는데, 근사치로 N(N-1)/2번 연산을 실행하므로 O(N^2)회 연산을 수행한다. 때문에 알고리즘 문제풀이에 사용하기에는 느린 편이다. Line 8에서 파이썬의 swap이 나타난다. 다른 언어들과 달리, 파이썬에서는 line 8처럼 쓰면 두 값이 바뀐다.
[6-2] Q : 삽입 정렬(Insertion Sort)을 구현해라.
A :삽입 정렬은 index 1부터 시작해서 왼쪽으로 가며 앞서 나온 숫자들 중 들어가기 적합한 위치를 찾아 삽입한다. 이 때, 자신보다 작은 수를 발견하면 더이상 탐색을 진행하지 않는데(line 7), 이는 삽입 정렬을 실행하고 있는 index(i) 앞에 있는 숫자들은 이미 정렬된 상태라는 것을 가정하기 때문이다. 위 코드는 line 5,6에서 숫자를 한 칸씩 계속 왼쪽으로 옮기다 적절한 자리를 찾으면 그만두는 방식이다. swap을 계속해서 진행해 비효율적으로 보여 넣어야 할 index를 찾고, 그 위치로 array[i]를 한 번만 삽입하면 되지 않을까? 하고 구현을 시도해 보았지만, 그렇게 되면 삽입되는 위치부터 i-1번 index까지 있는 수들을 index를 1씩 증가시켜야 한다. 하지만 이를 구현하려면 어차피 한 번만 swap하는 것이 불가하므로, line 6처럼 반복해 swap해준다. 삽입 정렬의 시간복잡도는 O(N^2)다. line 3,4에서 반복문이 두 번 중첩되어 사용되기 때문이다. 하지만 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 삽입 정렬은 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간복잡도를 가진다. 퀵 정렬과 비교했을 때, 보통은 퀵 정렬이 효율적이나 거의 정렬되어 있는 상태로 입력이 주어진다면 삽입 정렬을 이용하는 것이 빠를 수 있다.
[6-3] Q : 퀵 정렬(Quick Sort)을 구현해라.
A :퀵 정렬(Quick Sort)은 pivot을 중심으로 pivot보다 작은 수는 pivot의 왼쪽에, 큰 수는 pivot의 오른쪽에 모은다. pivot은 주어진 블록(array)의 첫 원소로 설정하며, start는 두번째 원소부터 시작해서 오른쪽으로, end는 블록의 끝에서 부터 시작해서 앞쪽으로 이동한다. 그 과정에서 start(left)와 end(right)가 엇갈릴때까지 수행을 계속한다(line 10). line 11에서 left를 키워가며 pivot보다 작은 수를 찾고, line 13에서 right를 줄여가며 pivot보다 큰 right을 찾는다. 그렇게 찾은 left와 right을 가지고, line 18에서 left<=right라면, 즉, 아직 엇갈리지 않았다면, right와 left에 해당하는 원소를 바꿔준다. 하지만 만약 left>right라면, 즉 엇갈렸다면(line 16), right과 pivot을 바꿔준다. 그렇게 하면 pivot의 왼쪽에는 pivot보다 작은 수들만 위치하게 되고, pivot의 오른쪽에는 큰 수들만 위치하게 된다. left와 right이 엇갈릴때까지 확인했기 때문에 모든 수들에 대해 확인한 것이므로 그렇게 된다. 그리고 line 22,23에서는 pivot을 제외한 왼쪽블록과 오른쪽 블록에 대해 quick_sort 함수를 재귀해준다. 작은 array블록을 입력하는 형식이 아니라, start와 end 범위를 적어주는 방식이다. 이 때, line 22,23에는 right를 기준으로 -1,+1이 들어가는데, 이는 line 17에서 right의 위치에 pivot이였던 원소가 들어가기 때문에 array[right]에는 pivot이 위치하기 때문이다. 때문에 pivot을 제외한 왼쪽 블록과 오른쪽 블록을 재귀해준다. 그리고 line 4에서 블록의 길이가 1이라면 재귀를 멈춘다. 오른쪽 실행 결과를 보면, line 1에서 첫 원소는 7이고, 이것이 pivot이 된다. 실행 결과 첫줄에는 7을 중심으로 왼쪽에는 7보다 작은 수가, 오른쪽에는 7보다 큰 수가 위치해 있다. 그 다음 네 줄은 7을 기준으로 왼쪽 블록에 대해서 연속해 line 21이 실행된 결과이다. 7을 기준으로 오른쪽 블록에 대해서는 마지막 두 줄의 실행결과에서 line 21이 실행된 것을 확인할 수 있다. 실행결과 둘째 줄에서는 pivot 2를 중심으로 정렬이 된 것을 확인할 수 있다.
퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도를 가진다. 만약 이상적으로 분할이 절반으로 일어난다면, 그 분할은 logN 단계에 걸쳐 일어나기 때문이다(8->4/4->2/2/2/2->1/...1, log8 = 3단계). 하지만 최악의 경우는 시간복잡도가 O(N^2)다. 앞서 다룬 정렬 방식들은 이미 데이터가 정렬되어 있는 경우에서는 빠르게 동작한다고 말했는데, 퀵 소트는 그렇지 않다. 오히려 이미 데이터가 정렬되어 있는 경우 느리게 동작한다. 1234의 경우 234가 모두 1보다 크므로 블록이 효율적으로 배분되지 않기 때문이다.
위 코드보다 이 코드를 사용하면 파이썬의 장점을 활용해 더 간단하게 퀵 정렬을 구현할 수 있다. 하지만 이 코드는 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 약간 비효율적이다.
[6-4] Q : 계수 정렬(Count Sort)을 구현해라.
A : 계수 정렬은 특정 조건이 부합할때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)의 수행시한을 보장한다. 하지만 계수 정렬은 가장 큰 데이터와 가장 작은 데이터의 차이가 작고, 정수형으로 제공되어 있을 때 사용하기 적절하다. 예를 들어, 0~100점 사이의 점수분포 정리가 있다. 계수 정렬에서는 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에 가장 큰 데이터와 가장 작은 데이터의 차이가 크면 안된다. 적절한 상황에 잘 사옹하면 계수 정렬은 매우 효율적인 알고리즘이지만, 상황을 잘 보고 사용해야 한다. 예를 들어, 데이터가 0과 999,999만 있다고 하면, 이 때도 리스트의 크기가 100만개가 되도록 선언하므로 공간 복잡도 면과 시간 복잡도 면 모두에서 비효율적이다. 계수 정렬 알고리즘은 동일한 값을 데이터가 여러 개 등장할 때 적합하다. 만약 0~100 점의 점수분포라면, 길이가 101인 리스트를 선언하고, 모든 원소를 0으로 초기화한다. 그리고 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스를 1씩 증가시킨다. 그리고 각 원소들을 하나씩 출력하면 정렬이 끝난다.
[6-5] Q : 파이썬의 내장 함수를 이용해 정렬해라.
A :파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 병합 정렬을 기반으로 만들어졌는데, 일반적으로는 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN)의 시간복잡도를 보장한다. sorted() 함수는 리스트, 집합, 딕셔너리 자료형을 입력받을 수 있는데, 반환되는 결과는 리스트 자료형이다. line 3같이 리스트 객체의 내장 함수인 .sort()를 이용할 수 도 있다.
정렬 라이브러리는 이미 잘 작성된 함수이므로 문제에서 별도의 요구가 없으면 기본 정렬 라이브러리를 이용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 이용한다.
[6-6] Q : key 매개변수를 이용해 정렬해라.
A :key 값으로는 하나의 함수가 들어가야 하며, 이는 정렬 기준이 된다. line 2같이 리스트의 데이터가 튜플로 구성되어 있다고 할 때, 각 데이터의 두 번째 원소를 기준으로 설정하는 경우 위 처럼 코드를 작성할 수 있다. Line 4에서 setting 함수를 정의하고, 그 함수의 이름을 key에 적어준다. setting 함수에는 array의 원소인 각 튜플이 들어가고, 튜플(data)의 두번째 원소인 data[1]을 기준으로 sorted 함수가 작동한다.
[6-7] Q : 수열을 내림차순으로 정렬하는 프로그램을 만들어라. 첫 줄에 수열에 속해있는 수의 개수 N이 주어진다. 둘째 줄부터 N+1번째 줄까지 N개의 수가 입력된다. 결과를 공백을 두고 출력해라.
A :내림차순(큰 수부터 작은 수로)으로 정렬하면 list.sort(reverse=True)를 사용한다. 만약 sorted() 함수를 사용한다면 sorted(list,reverse=True)로 써줄 수 있다.
[6-8] Q : N명의 학생 정보가 있다(1~100,000). 각 학생의 정보는 학생의 이름과 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 이름을 출력하는 프로그램을 작성해라. 첫 줄에 학생의 수 N이 입력되고, 둘째 줄부터 N+1번째 줄까지 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백을 두고 입력된다. 모든 학생의 이름을 성적이 낮은 순서대로 출력해라.
A :Line 4에서 A와 B를 다르게 입력받았는데, 그 대신 input_data = input().split(), array.append(input_data[0], int(input_data[1]))을 해줄 수 있다. 또한 jumsoo 함수를 정의해 key로 사용할 수 있지만, 함수를 별도로 정의하지 않고도 array = sorted(array, key=lambda student: student[1])으로 써줄 수 있다. 이것은 람다 함수를 이용한 방법으로, 별도의 함수를 정의해주지 않아도 된다.
[6-9] Q : 두 배열 A,B가 있다. 이들은 각각 N개의 원소로 구성되어 있으며, 원소는 모두 자연수다. 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 이는 A와 B의 원소 하나를 바꾸는 것을 말한다. 최종 목표는 A의 모든 원소의 합이 최대가 되도록 하는 것이다. N,K,A,B가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행해 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력해라. 첫째 줄에 N,K가 공백을 두고 입력된다(1~N~100,000, 0~K~N). 둘째 줄에 A의 원소들이 공백을 두고 입력되고, 셋째 줄에 B의 원소들이 공백을 두고 입력된다.
A : A,B를 정렬시켜두고 A에서 가장 작은 원소가 B에서 가장 큰 원소보다 크다면 교체를 중단하면 된다. 때문에 A는 오름차순으로, B는 내림차순으로 정렬해 두고, 앞부터 차례로 비교해가며 교체를 진행해 나간다. A는 i가 커짐에 따라 작았던 숫자가 커지고, B는 컸던 숫자가 작아지기 때문에, 두 수에 교차가 일어난다. 이 때 line 11에서 break된다. 처음에는 line 5와 line 6를 line 8의 for 문 안에 넣어서 매 번 정렬하고, A[0]이 B[0]보다 크다면 break 하도록 작성해 주었지만, 이는 K번동안 계속 정렬을 진행하기에 시간 낭비가 매우 심하다.
