[Algorithm] 25강 : 정렬 알고리즘 복잡도 비교 및 기본 문제

 

정렬 알고리즘 비교하기

 

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

대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다.

 

 

 

 

<문제> 두 배열의 원소 교체

 

 

 

핵심아이디어는 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체하는 것이다.

이것은 A가 B보다 작을 때만 가능하다.

 

 

 

소스코드 구현

 

n, k = map(int, imput().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))

 

 

---

www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

이 자료는 동빈 나 님의 이코 테 유튜브 영상을 보고 정리한 자료입니다.