정렬 알고리즘
정렬
데이터를 특정한 기준에 따라 순서대로 정렬
선택 정렬
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
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] # 스와프
삽입 정렬
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i 부터 1까지 1씩 감소하며 반복
if array[j] < array[j-1]: # 한칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 첫번째 데이터를 기준으로
- 왼쪽에서 기준 보다 작은 수 선택
- 오른쪽에서 기준 보다 큰 수 선택
- 선택된 수 서로 위치 변경
- 2~3 반복하며 범위가 겹칠때 작은 수와 기준 위치 변경 ( 분할 )
- 바뀐 기준을 기준으로 왼쪽 묶음과 오른쪽 묶음으로 나눠 1~5를 재귀적으로 반복
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # pivot는 첫번째 원소
left = start + 1
right = end
while(left <= right):
# pivot보다 큰 데이터를 찾을 때까지 반복
while(left <= end and array[left] <= array[pivot]):
left += 1
# pivot보다 작은 데이터를 찾을때까지 반복
while(right > start and array[right] >= array[pivot]):
right -= 1
if(left > right): # 엇갈렸다면 작은 데이터와 pivot을 교체
array[right], array[pivot] = array[pivot], array[right]
else:
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right -1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) -1)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
# 리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0] # 피벗은 첫번째 원소
tail = array[1:] # 피벗을 제외한 리스트
left_side = [ x for x in tail if x <= pivot ] # 분할된 왼쪽 부분
right_side = [ x for x in tail if x > pivot ] # 분할된 오른쪽 부분
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고 전체 리스트 반환
return quick_sort(left_side) + [ pivot ] + quick_sort(right_side)
print(quick_sort(array))
계수 정렬
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 0, 3, 1, 6, 2, 4, 8]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array)+1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
연습문제
두 배열의 원소 교체
- 동빈이는 두개의 배열 A와 B를 가지고 있습니다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수입니다.
- 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말합니다
- 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것입니다.
- N, K, 그리고 배열 A, B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하세요
- 예를 들어 N = 5, K = 3
- 배열 A = [1, 2, 5, 4, 3]
- 배열 B = [5, 5, 6, 6, 5]
- 이 경우 다음과 같이 3번의 연산 수행할 수 있습니다.
- 연산 1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
- 연산 2) 배열 A의 원소 '2'과 배열 B의 원소 '6'을 바꾸기
- 연산 3) 배열 A의 원소 '3'과 배열 B의 원소 '5'을 바꾸기
- 세 번의 연산 이후 배열 A와 B는 다음과 같이 구성될 것입니다.
- 배열 A = [6, 6, 5, 4, 5]
- 배열 B = [3, 5, 1, 2, 5]
- 이때 배열 A의 모든 원소 합은 26이 되며 이보다 더 합을 크게 만들 수 없습니다.
입력조건
- 첫번째 줄에 N, K가 공백을 기준으로 구분되어 입력 ( 1 ≤ N ≤ 100,000 , 0 ≤ K ≤ N )
- 두번째 줄에 배열 A의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10,000,000보다 작은 자연수 입니다.
- 세번째 줄에 배열 B의 원소들이 공백을 기준으로 구분되어 입력됩니다. 모든 원소는 10,000,000보다 작은 자연수 입니다.
출력조건
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력합니다.
입력예시
5 3
1 2 5 4 3
5 5 6 6 5
출력예시
26
문제 풀이
핵심아이디어
매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체
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: # A의 원소가 B의 원소보다 크거나 같을때 반복문을 탈출
break
print(sum(a)) # 배열 A의 모든 원소의 합 출력
참고
[한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)