홈 [Algorithm] 코딩테스트 알고리즘 08 - 정렬
포스트
취소

[Algorithm] 코딩테스트 알고리즘 08 - 정렬

게시 2022-05-19 업데이트 2022-10-16
By 19tak

본 포스팅은 “이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)을 바탕으로 공부한 내용을 정리한 것입니다.

  1. 서론
    • 코딩 테스트에서 정렬 알고리즘이 사용되는 경우의 3가지 유형
  2. 실전 문제 1
    • 위에서 아래로
  3. 실전 문제 2
    • 성적이 낮은 순서로 학생 출력하기
  4. 실전 문제 3
    • 두 배열의 원소 교체

1. 서론

코딩테스트 공부를 진행하면서 효율성 검사에서 자주 실패를 겪으며 시간복잡도에 대해 생각을 많이 하게 되었다.

그 중에서도 가장 적용이 많이 되는 부분이 정렬 파트라고 생각한다.

  1. 선택 정렬의 시간 복잡도는 O(N^2)
  2. 삽입 정렬의 시간 복잡도는 O(N^2)
    • 단, 거의 정렬이 되어있는 상태 (최선의 경우) O(N)의 시간 복잡도를 가진다.
    • 특정 상황에서는 타 알고리즘보다 유리하다.
  3. 퀵 정렬의 시간 복잡도는 O(NlogN)
    • 단, 최악의 경우 O(N^2)으로, 이미 데이터가 정렬되어 있는 경우에는 삽입 정렬을 사용하자.
  4. 계수 정렬의 시간 복잡도는 O(N+K)
    • 위의 세 정렬 알고리즘 (비교기반)과는 다르게 별도의 리스트를 선언하고 새로 정보를 담는다.

위의 내용들을 바탕으로 코딩테스트를 위해서 무엇을 위주로 공부하는게 좋을지를 자주 고민 중이다.

파이썬의 기본 정렬 라이브러의 sorted() 함수의 시간 복잡도는 O(NlogN)을 보장한다고 한다.

코딩 테스트에서 정렬 알고리즘이 사용되는 경우의 3가지 유형

  1. 정렬 라이브러리로 풀 수 있는 문제
    • 단순히 정렬 기법을 알고 있는지
  2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
    • 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를
  3. 더 빠른 정렬이 필요한 문제
    • 계수 정렬 등의 다른 정렬 알고리즘을 이용,, 등

2. 실전 문제 1

파이썬 기본 정렬 라이브러리 이용 문제

위에서 아래로

수열을 내림차순으로 정렬하는 프로그램을 만드시오.

  • 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1 <= N <= 500)
  • 둘째 줄부터 N+1 번째 줄까지 N개의 수가 입력된다. 1 ~ 10만 이하의 자연수.
  • 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 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 = ' ')

3. 실전 문제 2

계수 정렬 이용 문제 + 튜플 정렬

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

각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력.

  • 첫째 줄에 학생의 수 N이 입력 (1 <= N <= 100000)
  • 둘째 줄부터 N+1 줄에는 학생의 이름을 나타내는 문자열 A와 학생성적 B가 공백으로.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# N을 입력받기
n = int(input())

# N명의 학생 정보를 입력받아 리스트에 저장
array = []
for i in range(n):
    input_data = input().split()
    # 이름은 무자열 그대로, 점수는 정수형으로 변환하여 저장
    array.append(input_data[0], int(input_data[1]))

# 키(Key)를 이용하여, 점수를 기준으로 정렬
array = sorted(array, key=lambda student: student[1])

# 정렬이 수행된 결과를 출력
for student in array:
    print(student[0], end=' ')

4. 실전 문제 3

O(NlogN)을 보장하는 정렬 알고리즘을 사용

두 배열의 원소 교체

두 개의 배열 A와 B는 N개의 자연수 원소로 구성되어 있다.

최대 K번의 바꿔치기 연산을 수행할 수 있다. 서로의 배열에서 원소 하나씩을 골라서 바꾸는 것이다.

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

  • 첫째 줄에 N, K가 공백으로 구분되어 입력. (1 <= N <= 100000, 0 <= K <= N)
  • 둘째, 셋째 줄에 A와 B의 원소들이 공백으로 구분되어 입력. 천만 이하의 자연수.
  • 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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 파이썬” - (한빛미디어, 나동빈 지음)

Study, Algorithm
Python Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기