알고리즘 문제 해결 능력은 기술 면접에서 중요한 요소입니다. 이번 포스트에서는 ‘카드 정렬하기’라는 알고리즘 문제를 다루고, 문제 해결 과정을 단계별로 살펴보겠습니다. 이 문제는 실제 코딩 테스트에서 자주 등장하는 유형 중 하나로, 주어진 카드들을 특정한 방식으로 정렬하는 작업을 포함합니다. 이 글을 통해 문제에 대한 이해도를 높이고, 실전에서 응용할 수 있는 방법을 배워봅시다.
문제 정의
주어진 N개의 카드가 있습니다. 이 카드들은 각각의 숫자로 표시되어 있으며, 이 숫자들은 정수입니다. 우리의 목표는 이 카드들을 정렬하는 것입니다. 하지만 이 과정에서 특정한 규칙을 따라야 합니다.
함수 시그니처:
def card_sorting(cards: List[int]) -> List[int]:
pass
여기서 cards는 정수들로 이루어진 리스트이며, 정렬된 카드를 반환해야 합니다. 하지만 각 카드는 정해진 방법으로 정렬해야 합니다. 주의할 점은 카드 정렬을 수행하는 데 관련된 특정한 조건이 있을 수 있으며, 이러한 조건들을 효과적으로 처리해야 합니다.
문제 접근
이제 문제를 해결하기 위한 접근 방식을 살펴보겠습니다. 카드 정렬하기 문제는 다음과 같은 세부적인 규칙이 있다고 가정하겠습니다:
- 카드는 주어진 순서대로 나열되어 있으며, 각 카드에 대해 인접한 카드와 비교하여 정렬합니다.
- 정렬 과정에서 더 작은 숫자의 카드를 왼쪽으로 이동시킵니다.
- 각 카드의 숫자는 고유하며 중복되지 않습니다.
이제, 카드들을 정렬하기 위해 다양한 알고리즘을 사용할 수 있습니다. 일반적으로 사용되는 알고리즘은 다음과 같습니다:
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
- 퀵 정렬(Quick Sort)
- 병합 정렬(Merge Sort)
각각의 알고리즘에 대해서는 이론적인 설명도 필요하므로, 이들 각각에 대해 간단한 설명을 추가하겠습니다.
버블 정렬(Bubble Sort)
버블 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 두 요소를 비교하여 정렬하는 방식입니다. 리스트의 크기만큼 반복하며, 인접한 요소들을 비교한 후, 필요에 따라 서로 교환합니다. 최악의 경우 O(N²)의 시간 복잡도를 가집니다.
선택 정렬(Selection Sort)
선택 정렬은 주어진 리스트에서 가장 작은 값을 찾아서 정렬을 계속하는 방식입니다. 리스트의 크기만큼 반복하면서 매번 남은 요소 중에서 가장 작은 값을 찾아서 현재 위치에 정렬합니다. 이 또한 O(N²)의 시간 복잡도를 가집니다.
삽입 정렬(Insertion Sort)
삽입 정렬은 이미 정렬된 데이터에 새로운 요소를 삽입하는 방식입니다. 초기에는 첫 번째 요소가 정렬된 상태로 간주하고, 그 다음 요소부터 정렬된 위치에 삽입합니다. 일반적으로 O(N²)의 시간 복잡도를 가지나, 데이터가 거의 정렬되어 있을 경우 더 좋은 성능을 보입니다.
퀵 정렬(Quick Sort)
퀵 정렬은 분할 정복 알고리즘을 기반으로 하며, 하나의 피벗 요소를 선택하여 리스트를 피벗보다 작은 값과 큰 값을 기준으로 분할합니다. 그 후, 각 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다. 평균적으로 O(N log N)의 시간 복잡도를 가집니다.
병합 정렬(Merge Sort)
병합 정렬 또한 분할 정복 기법을 사용합니다. 리스트를 반으로 나누고, 각각의 리스트를 재귀적으로 정렬한 다음 두 리스트를 병합하여 정렬합니다. 역시 O(N log N)의 시간 복잡도를 가집니다.
문제 해결 – 카드 정렬하기 구현
이제 카드 정렬하기 문제를 해결하기 위한 파이썬 코드를 구현해 보겠습니다. 우리는 이 문제를 퀵 정렬를 사용하여 해결하도록 하겠습니다.
from typing import List
def quick_sort(cards: List[int]) -> List[int]:
if len(cards) <= 1:
return cards
pivot = cards[len(cards) // 2]
left = [x for x in cards if x < pivot]
middle = [x for x in cards if x == pivot]
right = [x for x in cards if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
def card_sorting(cards: List[int]) -> List[int]:
return quick_sort(cards)
테스트 케이스
코드가 구현되었으니, 다양한 테스트 케이스를 통해 올바르게 작동하는지 확인해보겠습니다.
if __name__ == "__main__":
test_cases = [
[3, 6, 8, 10, 1, 2, 1],
[5, 2, 9, 1, 5, 6],
[2, 7, 1, 8, 2, 3, 5]
]
for cards in test_cases:
sorted_cards = card_sorting(cards)
print(f"Original: {cards} -> Sorted: {sorted_cards}")
이 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:
Original: [3, 6, 8, 10, 1, 2, 1] -> Sorted: [1, 1, 2, 3, 6, 8, 10]
Original: [5, 2, 9, 1, 5, 6] -> Sorted: [1, 2, 5, 5, 6, 9]
Original: [2, 7, 1, 8, 2, 3, 5] -> Sorted: [1, 2, 2, 3, 5, 7, 8]
결론
이번 글에서는 ‘카드 정렬하기’ 문제를 해결하기 위해 다양한 정렬 알고리즘을 살펴보고, 그 중 퀵 정렬 알고리즘을 사용하여 문제를 해결했습니다. 파이썬을 이용한 구현 방법과 함께 적절한 테스트 케이스를 통해 코드의 정확성을 검증하였습니다. 이와 같은 문제를 통해 알고리즘적인 사고를 키우고, 코딩 테스트에서 좋은 성과를 거두기를 바랍니다. 계속해서 다양한 문제를 연습하고, 여러분의 실력을 키워나가세요!