[코딩테스트] 정렬 알고리즘 비교 및 기초 예제

앞의 포스팅에서 네 가지의 정렬 알고리즘을 다뤘다.

상세한 내용이 필요하다면 먼저 아래 두 포스팅을 보고 오는 것을 추천한다.

 

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(1) 선택 정렬과 삽입 정렬

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(2) 퀵 정렬 계수 정렬

 

1. 선택 정렬

평균 시간 복잡도 O(N²)

공간 복잡도 O(N)

매우 간단하고 구현이 쉽다.

 

2. 삽입 정렬

평균 시간 복잡도 O(N²)

공간 복잡도 O(N)

일반적으로 선택정렬보다 좀 더 빠르다. 데이터가 거의 정렬되어 있다면 O(N)으로 가장 빠르다.

 

3. 퀵 정렬

평균 시간 복잡도 O(NlogN)

공간 복잡도 O(N)

대부분 가장 적합하며, 충분히 빠르다.

그러나 구현 방식에 따라 최악의 경우에는 O(N²)의 시간 복잡도를 가지므로 유의하자.

 

4. 계수 정렬

평균 시간 복잡도 O(N+K)

공간 복잡도 O(N+K)

데이터의 크기가 한정되어 있는 경우에만 사용 가능하지만, 조건만 만족한다면 매우 빠르게 동작한다.

 

 

*표준 정렬 라이브러리에는 최악의 경우에도 O(NlogN)을 보장할 수 있게 설계되어 있다.

그래서 별도로 정렬 함수 구현을 요구하지 않는다면, 기본 정렬 라이브러리를 사용하는 것을 추천한다.

 

 

실제로 구현 시간을 비교해보니, 1만개의 배열을 정렬하는 데

선택 정렬은 약 10초,

하이브리드 정렬 알고리즘을 이용하는 파이썬 기본 정렬 라이브러리 sort는 0.001초로

확연한 속도 차이를 보였다.

 

 

문제 1. 두 배열의 원소 교체

N개의 자연수를 원소로 가지는 두 개의 배열 A와 B가 있다.

배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 바꿔치기 연산이라고 하자.

최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.

N,K, 배열A, 배열B가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라.

 

풀이

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

1. 배열A와 B가 주어지면 A를 오름차순, B를 내림차순 정렬한다.

2. 이후에 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때만 교체한다.

3. 두 배열의 원소가 최대 100,000개까지 입력될 수 있다면, 최악의 경우 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.

 

# 문제 1 풀어보기 ; 두 배열의 원소 교체
N,K = map(int, input().split(' '))
A=list(map(int,input().split(' ')))
B=list(map(int,input().split(' ')))
    
A.sort()
B.sort(reverse=True)
          
for i in range(0,K):
    if A[i]<B[i]:
        A[i],B[i]=B[i],A[i]

    else: #A의 원소가 B의 원소보다 크거나 같다면 바로 반복문 탈출
        break

#원소 합 구하기(1)
AA = int(0)
for i in range(len(A)):    
    AA = AA+int(A[i])

print(AA)

#원소 합 구하기(2)
print(sum(A)) #나는 원소들을 더하는 방식을 구현했는데, 실제로는 이렇게만 해도 구해진다.

 

 

 

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(2) 퀵 정렬 계수 정렬

2023.01.24 - [Data Science] - [코딩테스트] 정렬 알고리즘(1) 선택 정렬과 삽입 정렬

2023.01.24 - [Data Science] - [코딩테스트] DFS BFS 문제 풀이 실습

2023.01.23 - [Data Science] - [코딩 테스트] DFS BFS 개념 - 스택 큐 자료구조 재귀함수 기초

2022.12.24 - [Data Science] - [코딩테스트] 구현, 시뮬레이션과 완전 탐색

2022.12.23 - [Data Science] - [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

 

 

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
*내용에 대한 모든 저작권은 해당 영상의 원저작자에게 있습니다.