21.12.08 TIL

알고리즘 문제 풀기 with Python

정렬

데이터를 순서대로 나열하는 방법

정렬을 통해 이진 탐색을 가능하게 하거나 데이터를 조금 더 효율적으로 탐색할 수 있게 한다.

버블 정렬 : 두 수를 연속적으로 비교해가면서 가장 큰 수부터 오른쪽으로 보내도록 정렬

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    for i in range(len(array)-1):
        for j in range(len(array)-i-1):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]  
    return

bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간 복잡도 O(N^2)

선택 정렬 : 최솟값을 찾아서 제일 앞으로 보내기 반복

input = [4, 6, 2, 9, 1]

def selection_sort(array):
    for i in range(len(array)-1):
        min_index = i
        for j in range(i, len(array)):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index],  array[i]
    return


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간 복잡도 O(N^2)

삽입 정렬 : 정렬된 상태를 유지하면서 새로운 원소를 추가하면서 정렬하는 방식

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    for i in range(1, len(array)):
        for j in range(-i, 0):
            if array[-j] < array[-j-1]:
                array[-j], array[-j-1] = array[-j-1], array[-j]
            else:
                break
    return


insertion_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간 복잡도 O(N^2)
불필요한 순회를 안할 수 있으므로 버블 정렬이나 선택 정렬보다 효율적이다.

병합 정렬 : 배열의 앞 부분과 뒷 부분의 두 그룹으로 나누어 각각 정렬한 후(분할 정복) 병합을 반복

병합

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0

    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] <= array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        for i in range(array2_index, len(array2)):
            result.append(array2[i])
    else:
        for i in range(array1_index, len(array1)):
            result.append(array1[i])

    return result


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

병합 정렬

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid]) # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음에
    return merge(left_array, right_array) # 합치면서 정렬하면 됩니다!


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0

    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] <= array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        for i in range(array2_index, len(array2)):
            result.append(array2[i])
    else:
        for i in range(array1_index, len(array1)):
            result.append(array1[i])

    return result


print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge_sort([6, 5, 9, 40, -1, -7, 11, 10]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge_sort([-1, 10, 3, 100, 40, 2, 78, 5]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge_sort([-1, 6, 0, 10, -1, 9, 1]))

시간 복잡도 O(NlogN)

---

연습문제

shop_prices = [30000, 2000, 1500000]
user_coupons = [20, 40]


def get_max_discounted_price(prices, coupons):
    prices.sort(reverse=True)
    coupons.sort(reverse=True)
    sum = 0
    for i in range(len(prices)):
        if i < len(coupons):
            sum += prices[i] * (100-coupons[i]) / 100
        else:
            sum += prices[i]
    return sum


print(get_max_discounted_price(shop_prices, user_coupons))  # 926000 이 나와야 합니다.