꼭 알아야하는 코딩 테스트 유형: 9) #Sorting

• 오늘은 코딩 테스트에서 중요한 유형 중 하나인 'Sorting(정렬)'에 대해 이야기해보려 합니다. 정렬 알고리즘은 주어진 데이터를 일정한 순서대로 배열하는 알고리즘입니다.

 

정렬이란?

 

• 정렬은 데이터를 일정한 순서로 재배치하는 작업을 의미합니다. 주어진 데이터를 크기, 알파벳 순서 등의 기준에 따라 오름차순(ascending order)이나 내림차순(descending order)으로 정리할 수 있습니다.
• 일반적으로 사용되는 몇 가지 정렬 알고리즘과 관련된 개념들을 소개하겠습니다.

 

1. 버블 정렬(Bubble Sort): 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하는 방식으로 동작합니다. 반복적인 비교와 교환을 통해 가장 큰 원소가 마지막으로 이동하게 됩니다.
2. 선택 정렬(Selection Sort): 주어진 리스트에서 최솟값을 찾아 맨 앞의 원소와 위치를 교환하는 과정을 반복하여 전체 리스트가 정렬될 때까지 진행합니다.
3. 삽입 정렬(Insertion Sort): 현재 위치에서 그 이전의 배열들과 비교하여 자신이 들어갈 위치를 찾아 삽입하는 방식으로 동작합니다.
4. 병합 정렬(Merge Sort): 분할 정복(divide and conquer) 방법을 사용하여 리스트를 반씩 나눈 후 병합하여 정렬하는 방식입니다.
5. 퀵 정렬(Quick Sort): 분할 정복(divide and conquer) 방법 중 하나로, pivot 값을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 처리하며 리스트 전체가 정렬될 때까지 반복합니다.
6. 힙(Heap)과 힙 정렬(Heap Sort): 완전 이진트리 형태인 힙 구조를 활용하여 원소들을 저장하고, 최대/최소값을 추출하여 배열에 저장함으로써 정렬을 수행합니다.
7. 표준 라이브러리의 정렬 함수: 대부분의 프로그래밍 언어에는 정렬을 위한 표준 라이브러리 함수가 제공됩니다. 이러한 함수들은 강력하고 최적화된 알고리즘을 사용하여 효율적으로 정렬 작업을 수행합니다.

 

정렬 문제 접근법

 

• 정렬은 코딩 테스트에서 다양한 문제 유형에 활용되며, 효율적인 정렬 알고리즘 선택과 구현 능력이 요구됩니다. 아래는 코딩 테스트에서 정렬 문제를 해결하기 위한 일반적인 접근 방법입니다.

 

1. 정렬 알고리즘 이해: 주어진 문제에 맞는 적절한 정렬 알고리즘을 선택하기 위해 각 알고리즘의 동작 원리와 시간 복잡도 등을 이해해야 합니다. 각 알고리즘의 장단점과 사용 시기를 파악하여 최적의 선택을 할 수 있습니다.
2. 기본 정렬 알고리즘 구현: 버블 소트, 선택 소트, 삽입 소트 등 기본적인 정렬 알고리즘들은 개념과 구현 방법을 익히기에 좋습니다. 이를 활용하여 기본적인 문제들을 해결하는 연습을 해보세요.
3. 표준 라이브러리 활용: 대부분의 프로그래밍 언어에는 내장된 정렬 함수가 있습니다. 해당 언어의 표준 라이브러리를 숙지하고, 주어진 데이터 타입과 조건에 맞게 내장된 함수를 사용하는 것이 좋습니다.
4. 특수한 조건 고려: 주어진 문제에서 추가로 고려해야 할 조건이 있는 경우, 비교 함수나 자체적인 데이터 구조 변경 등으로 조건을 반영할 수 있습니다.
5. 정확성과 성능 분석: 작성한 코드가 옳은 결과를 출력하는지 확인하며, 시간 및 공간 복잡도 분석을 수행하세요.

 

2470번: 두 용액

  문제  
 

• KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
• 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
• 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
• 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 n개의 서로 다른 용액의 특성값을 가지고 있습니다. 특성값은 절대값이 클수록 더 산성 또는 염기성이 강하게 나타나며, 두 용액을 혼합하여 0에 가장 가까운 값을 만들어 내는 문제입니다. 문제를 해결하기 위해서는 정렬을 이용해 용액의 특성값을 정리하고 그 중 0에 가장 가까운 값을 순차적으로 찾으면 됩니다.

n = int(input())
liquids = sorted(list(map(int, input().split())))

left, right = 0, n-1
ans = [liquids[left], liquids[right]]
min_diff = abs(liquids[left] + liquids[right])

while left < right:
    diff = liquids[left] + liquids[right]

    if abs(diff) < min_diff:
        min_diff = abs(diff)
        ans = [liquids[left], liquids[right]]

    if diff < 0: left += 1
    else: right -= 1

print(*ans)

• 먼저 입력 받은 용액의 특성값 리스트를 정렬합니다. 이후에 투 포인터 방식을 이용해 리스트의 왼쪽과 오른쪽에서부터 시작하여 두 용액의 합을 계산하면서 0에 가장 가까운 값을 찾습니다. 만약 합이 0보다 작다면 left 인덱스를 증가시켜 합을 늘리고, 합이 0보다 크면 right 인덱스를 감소시켜 합을 줄입니다.

 

1744번: 수 묶기

  문제  
 

• 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
• 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.
• 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
• 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 수열의 수를 두 개씩 묶어 곱한 값의 합을 최대로 만드는 문제입니다. 문제를 해결하기 위해서는 정렬을 이용해 수열을 정리하고 곱의 최대 값을 구하는 방법을 찾아야 합니다.

import sys; input=sys.stdin.readline

n = int(input())
pos, neg = [], []
res = 0

for _ in range(n):
    num = int(input())
    if num > 1: pos.append(num)
    elif num <= 0: neg.append(num)
    else: res += num  # 0 및 1은 묶지 않고 더해준다.

pos.sort(reverse=True)
neg.sort()

for i in range(0, len(pos), 2):
    if i + 1 < len(pos): res += pos[i] * pos[i + 1]
    else: res += pos[i]

for i in range(0, len(neg), 2):
    if i + 1 < len(neg): res += neg[i] * neg[i + 1]
    else: res += neg[i]

print(res)

• 먼저 양수와 음수를 분리해서 따로 저장합니다. 그리고 양수는 내림차순으로 정렬하고, 음수는 오름차순으로 정렬합니다. 그리고 두 수씩 묶어 곱을 구하고 결과에 더해줍니다.

 

• 정렬 알고리즘은 데이터를 특정 기준에 따라서 순서대로 나열하는 과정으로 이해할 수 있습니다. 코딩 테스트에서 정렬 문제를 접하게 되면 적절한 정렬 알고리즘을 선택하여 문제를 해결해야 합니다. 정렬 알고리즘을 잘 숙지하면, 다양한 문제 유형에 대해 빠르고 효율적으로 해결할 수 있을 것입니다.