최진실

Sejong Univ. DataScience woowacourse

3 분 소요

Coding Test 4

이코테 4

1. 선택 정렬

  • 동작 예시
    [Step 0] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 ‘7’과 바꾼다.
    1-1

    [Step 1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 앞의 ‘5’과 바꾼다.
    1-2

    [Step 2] 처리되지 않은 데이터 중 가장 작은 ‘2’을 선택해 앞의 ‘9’과 바꾼다.
    1-3

    [Step 3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 앞의 ‘7’과 바꾼다.
    1-4

    [Step 4] 마지막 원소까지 반복
    1-5

    시간 복잡도 O(N^2) 공간 복잡도 O(N)

    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)) :
    min_index = i
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_Index] = array[min_index], array[i]

print(array)

2. 삽입 정렬

  • 동작 예시
    [Step 0] 첫 번째 데이터 ‘7’은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 ‘5’가 어떤 위치로 들어갈지 판단, ‘7’의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재
    2-1

    [Step 1] 이어서 ‘9’가 어떤 위치로 들어갈지 판단
    2-2

    [Step 2] 이어서 ‘0’이 어떤 위치로 들어갈지 판단
    2-3

    [Step 3] 이어서 ‘3’이 어떤 위치로 들어갈지 판단
    2-4

    시간 복잡도 O(N^2) 공간 복잡도 O(N)

    array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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

print(array)

3. 퀵 정렬

  • 동작 예시
    [Step 0] 첫번째 값이 pivot. 왼쪽에서부터 첫번째 값보다 큰 데이터를 선택하므로 ‘7’이 선택, 오른쪽에서부터 첫번째 값보다 작은 데이터를 선택하므로 ‘4’가 선택됨. 이 두 데이터의 위치를 서로 변경
    3-1

    [Step 1] 여전히 첫번째 값이 pivot. 왼쪽에서부터 첫번째 값보다 큰 데이터를 선택하므로 ‘9’이 선택, 오른쪽에서부터 첫번째 값보다 작은 데이터를 선택하므로 ‘2’가 선택됨. 이 두 데이터의 위치를 서로 변경
    3-2

    [Step 2] 여전히 첫번째 값이 pivot. 왼쪽에서부터 첫번째 값보다 큰 데이터를 선택하므로 ‘6’이 선택, 오른쪽에서부터 첫번째 값보다 작은 데이터를 선택하므로 ‘1’가 선택됨. 이 두 데이터의 위치를 서로 변경. 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경
    3-3

    [Step 3] 왼쪽에 있는 데이터는 모두 피벗보다 작고, 오른쪽에 있는 데이터는 모두 피벗보다 큼 -> 이 작업이 '분할' 3-5

    [Step 4] 왼쪽에 대해 퀵 정렬, 오른쪽에 대해 퀵 정렬 -> 재귀 3-6
    3-7

    시간 복잡도 O(NlogN) 3-8
    공간 복잡도 O(N)

    array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end) :
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while(left <= right) :
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right):
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

    array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array) :
    if len(array) <= 1:
        return array
    pivot = [0]
    tail = array[1:]

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

    return quick_sort(left_side) + quick_sort(right_side)

print(quick_sort(array))

4. 계수 정렬

  • 동작 예시
    [Step 0] 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트 생성 4-1

    [Step 1] 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴 4-2

    [Step 2] 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록됨 4-3

    [Step 3] 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복하여 출력 4-4

    시간 복잡도 O(N+K) 공간 복잡도 O(N+K)

    array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array)+1)

for i in range(len(array)) :
    count[array[i]] += 1

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

정렬 알고리즘 비교

정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징
선택 정렬 O(N^2) O(N) 아이디어 매우 간단
삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠름
퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합, 빠른 편
계수 정렬 O(N+K) O(N+K) 데이터 크기가 한정되어 있는 경우에 가능, 매우 빠름

문제-두 배열의 원소 교체

:grey_question: A와 B 배열이 있고 N개의 원소로 구성되어 있습니다. 최대 K번의 바꿔치기를 하여 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

for i in range(k) :
    if a[i] < b[i] :
        a[i], b[i] = b[i], a[i]
    else :
        break

print(sum(a))

:grey_exclamation: 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체

카테고리:

업데이트:

댓글남기기

참고