4. 정렬

1. 선택 정렬 (Selection Sort)

- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸고 ....

=> 정렬되지 않은 부분에서 가장 작은 것을 선택해서 정렬되지 않은 부분의 가장 앞의 원소와 바꾸는 것

- 시간 복잡도 : O(N^2)

def selectionSort(array):
    for start_index in range(len(array)):
        minimum_index = start_index
        for now_index in range(start_index+1, len(array)):
            if array[now_index] < array[minimum_index]:
                minimum_index = now_index

        array[start_index], array[minimum_index] = array[minimum_index], array[start_index]

    return array

 

2. 삽입 정렬 (Insertion Sort)

- 앞의 정렬되어 있는 부분 중 맞는 위치에 '삽입'하면서 정렬하는 것

- 시간 복잡도 : 평균적으로 O(N^2), 이미 정렬이 되어있는 최적의 경우는 O(N)

def insertionSort(array):
    for i in range(1,len(array)):
        for j in range(i,0,-1):
            if array[j]<array[j-1]: #한 칸씩 왼쪽으로 이동
                array[j],array[j-1] = array[j-1],array[j]
            else: #자기보다 작은 데이터를 만나면 멈추기
                break

 

3. 퀵 정렬

- 피벗(기준)을 잡고, 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾아서 위치를 서로 교환해준다. 왼쪽에서 오른쪽으로 증가하는 인덱스와 오른쪽에서 왼쪽으로 감소하는 인덱스가 서로 만날 때 까지 이를 반복하자.
=> 두 인덱스가 서로 엇갈리게 되면, 작은 데이터와 피벗의 위치를 변경해준다.

=> 이 후, 피벗보다 작은 쪽과 피벗보다 큰 쪽에서 위의 과정을 반복해준다.

=> 피벗보다 작은 쪽, 피벗보다 큰 쪽으로 나눈 리스트의 길이가 1이 되면 종료한다.

- 시간 복잡도 : O(NlogN), 이미 데이터가 정렬되어 있는 최악의 경우 O(N^2)

def quickSort(array, start, end):
    if start>=end:
        return

    pivot = array[start]
    pivot_index = start

    left_index = start+1
    right_index = end
    
    while left_index<=right_index:
        while left_index<=end and array[left_index] <= pivot:
            left_index += 1

        while right_index>start and array[right_index]>=pivot:
            right_index -= 1

        if left_index<=right_index:
            array[left_index],array[right_index] = array[right_index], array[left_index]
        else:
            array[right_index],array[pivot_index] = array[pivot_index], array[right_index]

    quickSort(array,start,right_index-1)
    quickSort(array,right_index+1, end)

* 파이썬의 장점을 살린 버전 (시간 면에서는 조금 비효율적이다)

def quickSort(array):
    if len(array)<=1:
        return array

    pivot = array[0]
    tail = array[1:]

    left_side = [i for i in tail if i<=pivot]
    right_side = [i for i in tail if i>pivot]

    return quickSort(left_side) + [pivot] + quickSort(right_side)

 

4. 계수 정렬(Count Sort)

- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

=> 데이터의 크기 범위가 제한되어 정수 형태로 표현할수 있을 때만 사용할 수 있다. (실수형 데이터는 사용하기 어려움)

=> 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다.

=> 왜? : 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에

 

- 동일한 수가 여러번 나올 때 유리한 정렬이다.

- 시간 복잡도 : O(데이터의 개수 + 데이터 중 최댓값), 사용할 수 있다면 굉장히 빠르다

- 공간 복잡도 : O(데이터의 개수 + 데이터 중 최댓값)

- 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

def countSort(array):
    minimum = min(array)
    maximum = max(array)

    count = [0] * (maximum - minimum + 1)

    for i in array:
        count[i-minimum] += 1

    for i in range(len(count)):
        for j in range(count[i]):
            print(minimum+i,end = ' ')

 

5. 파이썬의 정렬 라이브러리

(1) sorted() 함수

- 일반적으로는 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN)을 보장한다.

- 리스트, 딕셔너리 자료형 등을 입력하면 정렬된 결과를 리스트 자료형으로 리턴한다.

 

(2) 리스트의 내장 함수인 sort()

- 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

 

(3) sorted(), sort() 함수의 key 매개변수

- 정렬 기준인 key 매개변수를 줄 수 있다.

array = [('바나나',2), ('사과',5), ('당근',3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)

print(result) #[('바나나', 2), ('당근', 3), ('사과', 5)]

 

<문제>

1. 위에서 아래로 

하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열을 내림차순으로 정렬하는 프로그램을 만들면된다.

 

<입력 조건>

• 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. 이때 범위는 1 <= N <= 500
• 둘째 줄부터 N + 1 번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하 자연수

<출력 조건>

• 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분해서 출력하면된다. 동일한 수는 순서상관없다.

입력 예시 3 15 27 12

출력 예시 27 25 12

(1) 직접 퀵정렬 구현해서 사용하기

import sys

def quickSort(array, start, end):
    if start>=end:
        return

    pivot = array[start]
    pivot_index = start

    left_index = start+1
    right_index = end
    
    while left_index<=right_index:
        while left_index<=end and array[left_index] <= pivot:
            left_index += 1

        while right_index>start and array[right_index]>=pivot:
            right_index -= 1

        if left_index<=right_index:
            array[left_index],array[right_index] = array[right_index], array[left_index]
        else:
            array[right_index],array[pivot_index] = array[pivot_index], array[right_index]

    quickSort(array,start,right_index-1)
    quickSort(array,right_index+1, end)

n = int(sys.stdin.readline().rstrip())

array = []
for _ in range(n):
    array.append(int(sys.stdin.readline().rstrip()))

quickSort(array, 0, len(array)-1)

for i in range(len(array)-1,-1,-1):
    print(array[i], end = ' ')

(2) 파이썬의 라이브러리 사용하기

import sys

n = int(sys.stdin.readline().rstrip())

array = []
for _ in range(n):
    array.append(int(sys.stdin.readline().rstrip()))

array.sort(reverse=True)

for i in array:
    print(i, end = ' ')

 

2. 성적이 낮은 순서대로 학생 출력하기

N명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다.

 

<입력 조건>

• 첫 번째 줄에 학생의 수 N이 입력된다. (1 <= N <= 100,000)
• 두 번째 줄 부터 N+1 번째 줄 까지 학생의 이름 그리고 성적이 공백으로 주어진다. 학생이름 길이는 100이하, 성적은 100이하 자연수로 주어진다.

<출력 조건>

• 모든 학생의 이름을 성적이 낮은 순으로 출력하면된다. 동일한 성적은 자유롭게 출력하면된다.

입력 예시 2 홍길동 96 이순신 78

출력 예시 이순신 홍길동

import sys

n = int(sys.stdin.readline().rstrip())

array = []
for i in range(n):
    inputs = list(sys.stdin.readline().rstrip().split())
    array.append([inputs[0],int(inputs[1])])

'''
def setting(data):
    return data[1]

array.sort(key = setting)
'''
array.sort(key = lambda student : student[1])

for i in array:
    print(i[0], end = ' ')

 

3. 두 배열의 원소 교체

동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다

동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다.

N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라.

예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자.

• 배열 A = [1, 2, 5, 4, 3]
• 배열 B = [5, 5, 6, 6, 5]

이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다

• 연산 1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
• 연산 2) 배열 A의 원소 '2'와 배열 B의 원소 '6'을 바꾸기
• 연산 3) 배열 A의 원소 '3'과 배열 B의 원소 '5'를 바꾸기

세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다

• 배열 A = [6, 6, 5, 4, 5]
• 배열 B = [3, 5, 1, 2, 5]

이때 배열 A의 모든 원소의 합은 26이 되며, 이보다 더 합을 크게 만들 수는 없다

 

<입력 조건>

• 첫 번째 줄: N, K 가 공백으로 구분되어 입력 (1 <= N <= 100,000, 0 <= K <= N)
• 두 번째 줄: 배열 A의 원소들이 공백으로 구분되어 입력 (원소 a < 10,000,000인 자연수)
• 세 번째 줄: 배열 B의 원소들이 공백으로 구분되어 입력 (원소 b < 10,000,000인 자연수)

<출력 조건>

• 최대 K번 바꿔치기 연산을 수행해서 가장 최대의 합을 갖는 A의 모든 원소 값의 합을 출력

입력 예시 5 3 1 2 5 4 3 5 5 6 6 5

출력 예시 26

import sys

n,k = map(int, sys.stdin.readline().rstrip().split())

array_a = list(map(int, sys.stdin.readline().rstrip().split()))
array_b = list(map(int, sys.stdin.readline().rstrip().split()))

array_a.sort()
array_b.sort(reverse=True)

for i in range(k):
    if array_a[i]<array_b[i]:
        array_a[i] = array_b[i]
    else:
        break

print(sum(array_a))

 

4. 국영수

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

10825번: 국영수

import sys

n = int(sys.stdin.readline().rstrip())

array = []
for _ in range(n):
    inputs = list(sys.stdin.readline().rstrip().split())
    array.append([inputs[0], int(inputs[1]), int(inputs[2]), int(inputs[3])])

array.sort(key = lambda x : (-x[1],x[2],-x[3],x[0]))

for i in array:
    print(i[0])

 

5. 안테나

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

18310번: 안테나

import sys

n = int(sys.stdin.readline().rstrip())

array = list(map(int,sys.stdin.readline().rstrip().split()))

array.sort()
if len(array)%2 == 0:
    print(array[len(array)//2-1])
else:
    print(array[len(array)//2])

 

 

6. 실패율

https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

def solution(N, stages):
    stages.sort()
    total = [0]*(N+2)
    failure = []
    for i in stages:
        total[i] += 1
    
    for i in range(N,0,-1):
        total[i] = total[i] + total[i+1]

    stages = list(set(stages))
    
    for i in range(N,0,-1):
        notfinished = total[i] - total[i+1]
        if total[i] == 0:
            failure.append([i,0])
        else:
            failure.append([i,notfinished/total[i]])
        
    failure.sort(key = lambda x : x[1])

    answer = [i[0] for i in failure]
    answer.reverse()
    return answer

 

7. 카드 정렬하기

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

1715번: 카드 정렬하기

import sys
import heapq

n = int(sys.stdin.readline().rstrip())

numbers = []

for _ in range(n):
    heapq.heappush(numbers, int(sys.stdin.readline().rstrip()))

total = 0
while len(numbers)>1:
    n1 = heapq.heappop(numbers)
    n2 = heapq.heappop(numbers)
    total += n1+n2
    heapq.heappush(numbers,n1+n2)

print(total)