✅ 사전학습
선택 정렬
데이터가 무작위로 여러 개 있을 때, 이 중 가작 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 알고리즘.
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) :
if array[j] > array[j-1] :
array[j], array[j-1] = array[j-1], array[j]
else :
break퀵 정렬
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end) :
if start >= end : #원소가 1개인 경우 종료
return
pivot = start #피벗은 첫 번째 원소
left = start + 1
right = end
while left <= right :
#피벗보다 큰 데이터 찾을 때까지 반복
while left <= end and array[left] <= array[pivot] :
left += 1
#피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and array[right] >= array[pivot] :
right -= 1
if left > right : #엇갈렸다면 작은 right -= 1 데이터와 피벗을 교체
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)위에서 아래로
📝 문제
하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.
입력조건
- 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1≤N≤500)
- 둘째 줄부터 N+1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1이상 100,000 이하의 자연수이다.
💡 정답
# N을 입력받기
n = int(input())
# N개의 정수를 입력받아 리스트에 저장
array = []
for i in range(n) :
array.append(int(input()))
# 파이썬 기본 정렬 라이브러리를 이용하여 정렬 수행
array = sorted(array, reverse = True)
for i in array :
print(i, end='')두 배열의 원소 교체
📝 문제
동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.
N, K 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
입력조건
- 첫째 줄에 N, K가 공백으로 구분되어 입력된다. (1≤N≤100,000, 0≤K≤N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 뭔소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
⭐ 문제 해설
기본 아이디어는 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다. 단, 배열 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()
b.sort(reverse=True)
for i in range(k):
if a[i] < b[i] :
a[i], bpi] = b[i], a[i]
else :
break
print(sum(a))