[이코테 2021] 10. 정렬 알고리즘 비교 및 기초 문제 풀이

🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.

정렬 알고리즘 비교하기

• 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 $O(NlogN)$을 보장하도록 설계되어 있다.
• 퀵 정렬의 경우, 구현 방식에 따라 최악의 경우 시간 복잡도가 $O(N^2)$이 나올 수 있다.

선택 정렬과 기본 정렬 라이브러리 수행 시간 비교

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
	# 1부터 100 사이의 랜덤한 정수
    array.append(randint(1,100))
    
# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
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]
    
# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("선택 정렬 성능 측정:", end_time - start_time)

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
	# 1부터 100 사이의 랜덤한 정수
    array.append(randint(1,100))

# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

# 측정 종료
end_time = time.time()
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time)

[실행 결과]

선택 정렬 성능 측정: 35.841460943222046
기본 정렬 라이브러리 성능 측정: 0.0013387203216552734

[문제1] 두 배열의 원소 교체: 문제 설명

• 동빈이는 두 개의 배열 A와 B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수입니다.
• 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다.
• 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 합니다.
• N,K 그리고 배열 A와 B의 정보가 주어졌을 떄, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하세요.
  

n, k = map(int, input().split())  # N과 K를 입력 받기
a = list(map(int, input().split()))  # 배열 A의 모든 원소를 입력 받기
b = list(map(int, input().split()))  # 배열 B의 모든 원소를 입력 받기

a.sort()  # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True)  # 배열 B는 내림차순 정렬 수행

# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
	# A의 원소가 B의 원소보다 작은 경우
    if a[i] < b[i]:
    	# 두 원소를 교체
        a[i], b[i] = b[i], a[i]
    else:
    	break

print(sum(a))  # 배열 A의 모든 원소의 합을 출력

[정렬 함수 정리]