[SW Intermediate] List 2 - 정렬(sort)

List 2 - 정렬(Sort)

---

정렬(Sort)

[셀렉션 알고리즘]

 

1) 저장되어 있는 자료로 부터 K 번째로 큰 혹은 작은 원소를 찾는 방법이다. 

(최소 값, 최대 값 혹은 중간 값을 찾는 알고리즘)

2) 셀렉션 선택과정 

- 정렬 알고리즘을 이용하여 자료를 정렬

- 원하는 순서에 있는 원소를 가져오기

 

EX) k 번째로 작은 원소 찾는 알고리즘

1 번부터 k 번까지 작은 원소들을 찾아 List 앞쪽으로 이동시키고, List의 k번째를 반환한다.

k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다.

 

def select(list, k):
	for i in range(0,k):
    	min_index = i
        for j in range(i+1, len(list)):
        	if list[min_index] > list[j]:
            	min_index = j
         list[i], list[min_index] = list[min_index], list[i]
    return list[k-1]

 

[선택 알고리즘(셀렉션 알고리즘 방식)]

1) 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식

2) 셀렉션 알고리즘을 전체 자료에 적용한 것이다.

3) 정렬과정

- 주어진 리스트 중 최소값을 찾는다.

- 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.

- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.

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

 

def selection_sort(a):
	for i in range(0, len(a)-1):
    	min = i
        for j in range(i+1, len(a)):
        	if a[min] > a[j]:
            	min = j
         a[i], a[min] = a[min], a[i]

---

문1) 색칠하기

T = int(input())
for test_case in range(1, T + 1):
    matrix = [[0]*10 for _ in range(10)]
    n = int(input())
    color_matrix = [list(map(int, input().split())) for _ in range(n) ]

    st = 0
    purple_count = 0

    while st < len(color_matrix):
        y1,x1,y2,x2,color = color_matrix[st]
        for y in range(y1, y2+1):
            for x in range(x1, x2+1):
                matrix[y][x] += color
                if matrix[y][x] == 3:
                    purple_count += 1

        st+=1

    print(f'#{test_case} {purple_count}')

 

문2) 부분 집합의 합

from itertools import combinations

T = int(input())
for test_case in range(1, T + 1):
    num_list = [i for i in range(1,13)]
    n, k = map(int, input().split())
    partitions = combinations(num_list, n)
    k_count = 0
    for parti in partitions:
        if sum(parti) == k:
            k_count +=1

    print(f'#{test_case} {k_count}')

 

문3) 이진 탐색

def binary_search(p, target, steps):
    l = 1
    r = p

    while l <= r:
        mid = (l+r)//2
        if mid == target:
            return steps
        elif target < mid:
            r = mid
            steps += 1
        else:
            l = mid
            steps += 1



T = int(input())


for test_case in range(1, T + 1):
    p, a, b = map(int, input().split())

    a_search = binary_search(p,a,1)
    b_search = binary_search(p,b,1)

    if a_search > b_search:
        print(f'#{test_case} B')
    elif a_search < b_search:
        print(f'#{test_case} A')
    else:
        print(f'#{test_case} 0')

 

문4) 특별한 정렬

T = int(input())

for test_case in range(1, T + 1):
    n = int(input())
    not_sorted = list(map(int, input().split()))
    res_list = []

    for _ in range(len(not_sorted)):
        if len(not_sorted) == 0:
            break
        if len(res_list) == 10:
            break
        res_list.append(str(max(not_sorted)))
        res_list.append(str(min(not_sorted)))

        not_sorted.remove(max(not_sorted))
        not_sorted.remove(min(not_sorted))

    res_str = ' '.join(res_list)
    print(f'#{test_case} {res_str}')