EDOC 2023-2 4주차 과제

04-3. 삽입 정렬

 

018. ATM (백준 11399번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))

for i in range(1, n):
    value = data[i]
    for j in range(i-1, -1, -1):
        if(data[j] > value):
            data[j+1] = data[j]
        else:
            data[j+1] = value
            break
        if(j==0):
            data[0] = value

sum = 0
for i in range(0, n):
    sum += (n-i) * data[i]

print(sum)

 

저번에 풀었던 문제지만 삽입 정렬로 다시 풀었다. (정답)

 

---

04-4. 퀵 정렬

 

019. K번째 수 (백준 11004번)

 

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

 

from sys import stdin
import sys

sys.setrecursionlimit(10**8)

n, k = map(int, stdin.readline().split())
data = list(map(int, stdin.readline().split()))

def swap(i, j):
    global data
    temp = data[i]
    data[i] = data[j]
    data[j] = temp

def quickSort(s, e):
    global data

    if s >= e:
        return

    m = (s + e) // 2
    swap(s, m)
    pivot = data[s]
    i = s + 1
    j = e

    while i <= j:
        while i <= e and data[i] < pivot:
            i += 1
        while j >= s and data[j] > pivot:
            j -= 1
        if i < j:
            swap(i, j)
            i += 1
            j -= 1
    
    data[s] = data[j]
    data[j] = pivot

    quickSort(s, j-1)
    quickSort(j+1, e)

quickSort(0, n-1)
print(data[k-1])

 

퀵 정렬 구현이 그렇게 직관적이지는 않아서 이해하는 데에 꽤 오래 걸렸다 ㅠㅠ. 그렇게 겨우겨우 코드를 완성했는데,,!! 시간 초과..... (오답) 아마 퀵 정렬이 피벗값 선택에 따라 최악의 경우 시간 복잡도가 n^2 이라서 그런 것 같다. 그래서 결국 이 문제는 파이썬 내장 함수 sort()를 사용해서 풀었고(정답), 내가 작성한 퀵 정렬이 제대로 정렬되는지는 수 정렬하기 (백준 2750번) 문제에 제출해봄으로써 확인했다.

 

---

04-5. 병합 정렬

 

020. 수 정렬하기 2 (백준 2751번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = []
tmp = [0] * n
for i in range(n):
    data.append(int(stdin.readline()))

def mergeSort(s, e):
    if e - s < 1:
        return

    m = (s + e) // 2
    mergeSort(s, m)
    mergeSort(m+1, e)

    for i in range(s, e+1):
        tmp[i] = data[i]

    k = s
    index1 = s
    index2 = m+1

    while index1 <= m and index2 <= e:
        if tmp[index1] > tmp[index2]:
            data[k] = tmp[index2]
            index2 += 1
            k += 1
        else:
            data[k] = tmp[index1]
            index1 += 1
            k += 1
    
    while index1 <= m:
        data[k] = tmp[index1]
        index1 += 1
        k += 1
    while index2 <= e:
        data[k] = tmp[index2]
        index2 += 1
        k += 1

mergeSort(0, n-1)

for i in data:
    print(i)

 

이것도 풀었던 문제지만 병합 정렬로 다시 풀었다. (정답)

 

---

 

021. 버블 소트 (백준 1517번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
tmp = [0] * n
result = 0

def mergeSort(s, e):
    global result

    if e - s < 1:
        return

    m = (s + e) // 2
    mergeSort(s, m)
    mergeSort(m+1, e)

    for i in range(s, e+1):
        tmp[i] = data[i]

    k = s
    index1 = s
    index2 = m+1

    while index1 <= m and index2 <= e:
        if tmp[index1] > tmp[index2]:
            data[k] = tmp[index2]
            index2 += 1
            k += 1
            result += m - index1 + 1
        else:
            data[k] = tmp[index1]
            index1 += 1
            k += 1
    
    while index1 <= m:
        data[k] = tmp[index1]
        index1 += 1
        k += 1
    while index2 <= e:
        data[k] = tmp[index2]
        index2 += 1
        k += 1

mergeSort(0, n-1)

print(result)

 

플래티넘 문제라서 쫄았는데, 병합 정렬을 사용하는 문제고 변화한 인덱스만큼 swap이 일어났다는 아이디어만 떠올리면 그 후는 간단한 문제였다. 물론 그 아이디어는 책이 떠올려줬다.. ^__^ 암튼 (정답).

 

---

04-6 기수 정렬

 

022. 수 정렬하기 3 (백준 10989번)

 

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

 

from sys import stdin

n = int(stdin.readline())
count = [0] * 10000

for i in range(0, n):
    num = int(stdin.readline())
    count[num-1] += 1

for i in range(0, 10000):
    for j in range(0, count[i]):
        print(i+1)

 

이것도 전에 풀었던 문제인데, 내 이전 풀이랑 책에 있는 풀이가 거의 완전 똑같아서 신기했다. (정답) 참고로 이 문제는 기수 정렬 아니고 계수 정렬!