코틀린 코딩테스트 강좌, 버블 소트 프로그램 2

안녕하세요! 이번 강좌에서는 코틀린 언어를 사용하여 버블 소트(Bubble Sort) 알고리즘을 구현하는 방법에 대해 알아보겠습니다. 버블 소트는 정렬 알고리즘 중에서 가장 기초적인 알고리즘 중 하나이며, 이해하기 쉽기 때문에 코딩 테스트의 기초 문제로 자주 출제됩니다. 우리는 자세한 설명과 함께 문제를 풀어볼 것입니다.

문제 정의

주어진 정수 배열을 오름차순으로 정렬하는 프로그램을 작성하시오. 배열의 길이는 N (1 ≤ N ≤ 1000)이며, 각 원소는 M (-104 ≤ M ≤ 104)입니다.

예제

  • 입력: [64, 34, 25, 12, 22, 11, 90]
  • 출력: [11, 12, 22, 25, 34, 64, 90]

알고리즘 설명

버블 소트는 인접한 두 원소를 비교하여 순서가 잘못된 경우 서로 교환하는 방식으로 정렬하는 알고리즘입니다. 이 과정이 반복되면서 가장 큰 값이 배열의 제일 끝으로 이동하게 되므로 “버블”이라는 이름이 붙었습니다. 버블 소트의 평균 및 최악의 시간복잡도는 O(N2)입니다.

버블 소트 알고리즘

  1. 배열의 크기 N을 가져옵니다.
  2. 0부터 N-1까지 반복합니다.
  3. 배열의 첫 번째 인덱스부터 N-i-1까지 반복하며, 두 인덱스에 있는 값을 비교합니다.
  4. 만약 첫 번째 인덱스의 값이 두 번째 인덱스의 값보다 크면 두 값을 서로 교환합니다.
  5. 모든 반복이 끝난 후 배열은 정렬되어 있게 됩니다.

코틀린 구현

이제 알고리즘을 실제로 코틀린으로 구현해보겠습니다:


fun bubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n - 1) { 
        // 마지막 i개는 이미 정렬되었으므로, n-i-1까지 반복합니다.
        for (j in 0 until n - i - 1) {
            // 인접한 두 원소 비교
            if (arr[j] > arr[j + 1]) {
                // 교환
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

fun main() {
    val inputArray = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    val sortedArray = bubbleSort(inputArray)
    println("정렬된 배열: ${sortedArray.joinToString(", ")}")
}

설명

위의 코드는 기본적인 버블 소트 구현을 보여줍니다. 주요 함수 bubbleSort는 정수 배열을 입력받아 정렬된 배열을 반환합니다. 두 개의 중첩 루프를 사용하여 인접한 원소를 비교하고, 필요할 경우 교환하는 방식으로 동작합니다.

코드 동작 과정

코드를 실행하면 다음과 같은 결과를 출력합니다:

정렬된 배열: 11, 12, 22, 25, 34, 64, 90

복잡도 분석

버블 소트의 시간 복잡도는 O(N2)입니다. 이는 최악의 경우, 모든 원소를 비교해야 하기 때문입니다. 그러나 최적의 경우(이미 정렬된 배열)는 시간 복잡도가 O(N)으로 줄어듭니다. 공간 복잡도는 O(1)입니다.

버블 소트의 장단점

버블 소트의 장단점은 다음과 같습니다:

  • 장점:
    • 구현이 간단하다.
    • 최소한의 메모리를 소모한다.
    • 정렬을 수행하는 과정에서 배열이 이미 정렬되어 있는지를 검사할 수 있다.
  • 단점:
    • 시간 복잡도가 너무 높아 큰 데이터셋에서는 비효율적이다.
    • 다른 효율적인 정렬 알고리즘과 비교했을 때 성능이 떨어진다.

응용 문제

이제 위의 개념을 바탕으로 조금 더 응용된 문제를 해결해보겠습니다. 주어진 배열에서 중복된 원소를 제거하고 정렬하여 출력하세요.

문제 정의

정수 배열을 입력받아 중복된 원소를 제거하고 오름차순으로 정렬한 결과를 출력하는 프로그램을 작성하시오.

예제

  • 입력: [64, 34, 25, 25, 12, 22, 11, 90, 90]
  • 출력: [11, 12, 22, 25, 34, 64, 90]

코드 구현


fun removeDuplicatesAndSort(arr: IntArray): IntArray {
    return arr.distinct().toIntArray().let { bubbleSort(it) }
}

fun main() {
    val inputArray = intArrayOf(64, 34, 25, 25, 12, 22, 11, 90, 90)
    val resultArray = removeDuplicatesAndSort(inputArray)
    println("중복 제거 및 정렬된 배열: ${resultArray.joinToString(", ")}")
}

결과

위의 코드를 실행하면 다음과 같은 결과가 출력됩니다:

중복 제거 및 정렬된 배열: 11, 12, 22, 25, 34, 64, 90

마무리

이번 강좌에서는 버블 소트 알고리즘에 대해 자세히 알아보았고, 이를 통해 기본적인 정렬 문제와 중복 제거 문제를 해결했습니다. 비록 버블 소트는 간단하고 이해하기 쉬운 알고리즘이지만, 코딩 테스트에 나오는 다양한 정렬 알고리즘을 익히고 연습하면 더욱 효과적으로 문제를 해결할 수 있습니다. 다음 강좌에서는 더 효율적인 정렬 알고리즘에 대해 다루는 시간을 갖겠습니다. 감사합니다!