서강덕

코린이의 개발 성장기📝

정렬이란?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. ex) 오름차순, 내림차순…
다양한 정렬 알고리즘이 있지만 가장 많이 사용하는 4가지 정도만 설명한다.

  • 선택 정렬
  • 삽입 정렬
  • 퀵 정렬
  • 계수 정렬

시간 복잡도

  • 선택 정렬: O(N^2)
  • 삽입 정렬: O(N^2)
  • 퀵 정렬: O(NlogN)
  • 계수 정렬: O(N + K) * K는 데이터중 최대값

파이썬 라이브러리

파이썬에서 기본 정렬 라이브러리인 sorted()함수를 제공한다. 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데 시간 복잡도는 퀵 정렬과 동일한 O(NlogN)이다.

정렬 알고리즘 문제 유형

  1. 정렬 라이브러리로 풀 수 있는 문제: 정렬 기법을 알고 있는지 물어보는 문제로 라이브러리만 알고 있다면 풀 수 있다.
  2. 정렬 알고리즘의 원리에 대해서 물어보는 문제: 다양한 알고리즘의 원리를 알아야 풀 수 있다.
  3. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로 풀 수 없으며 계수 정렬 등의 다른 알고리즘을 이용하거나 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

예제

위에서 아래로

문제

하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오.

입력 조건

  • 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다.(1 <= N <= 500)
  • 둘째 줄부터 N + 1번째 줄까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다.

출력 조건

입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다.

해결방법

가장 기본적인 정렬 문제로 라이브러리를 사용하면 쉽게 풀 수 있다.

import sys

N = int(sys.stdin.readline())

array = []
for i in range(N):
    array.append(int(sys.stdin.readline()))

array.sort(reverse=True) # 내림차순

print(*array)

성적이 낮은 순서로 학생 출력하기

문제

N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.

입력 조건

  • 첫 번째 줄에 학생의 수 N이 입력된다.(1 <= N <= 100,000)
  • 두 번째 줄부터 N + 1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다.

    출력 조건

    모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다.

해결방법

마찬가지로 점수 순으로 정렬하여 이름을 출력하면 된다.

import sys

N = int(sys.stdin.readline())
array = []

for i in range(N):
    grade = sys.stdin.readline().strip().split()
    array.append([grade[0],grade[1]])

array.sort(key= lambda x : x[1]) # key값을 점수로 설정

for student in array:
    print(student[0], end=' ')

두 배열의 원소 교체

문제

동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다

동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다

동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다

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

예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자

  • 배열 A = [1, 2, 5, 4, 3]

  • 배열 B = [5, 5, 6, 6, 5] 이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다

  • 연산 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의 원소들이 공백으로 구분되어 입력 (원소 a < 10,000,000인 자연수)
  • 세 번째 줄: 배열 B의 원소들이 공백으로 구분되어 입력 (원소 b < 10,000,000인 자연수)

출력

최대 K번 바꿔치기 연산을 수행해서 가장 최대의 합을 갖는 A의 모든 원소 값의 합을 출력

해결방법

A는 오름차순 정렬, B는 내림차순 정렬후 첫 번째 인덱스부터 비교하면서 A의 원소가 B보다 작을 경우만 교체하면 된다.

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().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))

Comments